Optimization of Multimodal Discrete Network Design Problems Based on Super Networks

Abstract

In this paper, we investigate the multimodal discrete network design problem that simultaneously optimizes the car, bus, and rail transit network, in which inter-modal transfers are achieved by slow traffic modes including walking and bike-sharing. Specifically, a super network topology is presented to signify the modal interactions. Then, the generalized cost formulas of each type of links in the super network are defined. And based on the above formulas a bi-objective programming model is proposed to minimize the network operation cost and construction cost with traffic flow equilibrium constraints, investment constraints and expansion constraints. Moreover, a hybrid heuristic algorithm that combines the minimum cost flow algorithm and simulated annealing algorithm is presented to solve the proposed model. Finally, the effectiveness of the proposed model and algorithm is evaluated through two numerical tests: a simple test network and an actual multimodal transport network.

1. Introduction

With the acceleration of urbanization and the development of intelligent transportation systems (ITS), multimodal travel behavior has become the main form for residents. A single travel mode fails to meet the increasing travel demand. The coordinated development of a diversified comprehensive transportation system, which includes car, bus, and rail transit, has gradually become the focus of meeting people’s travel and restraining the rapid expansion of the number of cars. Therefore, the study of multimodal transportation is conductive to guide passengers’ multimodal travel behavior and relieve congestion.

A multimodal transportation system can be described as a complicated network composed of nodes and links. However, the coupling and interaction of the complicated network bring a new problem: networks in networks. For example, some nodes/links of the car network are also the nodes/links of the bus or rail transit network in a comprehensive urban transportation system and vice versa. To deal with the problem, we use the super network theory, which is an effective tool to deal with network hierarchies, to study the multimodal transportation network design problem. Next, a literature review on super network, discrete network design problem, bus network design problem, and multimodal network design problem is as follows.

1.1. The Super Network

Super network concept was first proposed in 1984 to describe the urban transportation network [1]. Then the super network was described as “above and beyond existing networks” [2]. The concept of the super network was improved to “networks in networks” as well [3]. At present, the super network theory is mainly used among two areas: traffic flow assignment and logistics supply chain [4,5,6,7,8]. For example, Daniele et al. used the super network method to achieve Wardrop equilibrium of traffic flow in the Banach space environment and applied variational inequality to define it [4]. Yamada et al. proposed a discrete network design problem model to optimize the supply chain efficiency of the freight network and applied the super network method to realize the equilibrium of the transportation network [5]. In 2015, they further studied the multimodal freight transport network design problem by using particle swarm optimization [6]. Feng et al. proposed a closed-loop supply chain supernetwork model including suppliers, manufacturers, retailers and consumers at demand market [7]. Chen et al. considered the demand change problem composed of four travel choices (travel generation, travel distribution, travel mode division, and traffic flow assignment) as a nonlinear mathematical model, and each combination model can be treated as an “extended” traffic flow assignment problem by using super network technology [8].

From the above analysis, the super network theory is appropriate and effective in the application of topology description and traffic flow assignment of the complex transportation system. Therefore, the super network is applied in this paper to set up a super network topology of multimodal transportation network including care, bus, rail transit, and slow travel modes (bicycle and walking).

1.2. The Discrete Network Design Problem

Generally, the network design problem (NDP) of urban transportation refers to an optimal investment decision problem. For clarity, the decision problem is to determine the expansion of certain links or adding of new links under certain investment constraints and the choices of traffic travelers, which makes the entire transportation network reach certain indicators. Currently, NDP is divided into two forms according to the different types of decision variables: continuous network design problem (CNDP) [9,10,11,12,13] and discrete network design problem (DNDP) [14,15,16,17,18,19,20]. The first one tends to improve the capacity of existing road sections, while the second one is to add new road sections to the existing network. The multimodal transportation network design problem in this paper is a discrete network design problem (DNDP).

For DNDP, LeBlanc presented a nonlinear mixed-integer programming model and proposed a branch and bound algorithm to solve the model, which optimized some sections of the urban road network to minimize the overall congestion [14]. Farfaresh et al. improved B & B algorithm based on LeBlanc [15]. Poorzahedy et al. transformed the bi-level programming model into a model and proposed a heuristic algorithm based on B & B to solve the model [16]. Gao et al. established a bi-level programming model, and used the support formula method to express the relationship between the expanded links and the added links, and designed an algorithm to solve the bi-level programming model. Considering the optimal number of lanes added for each candidate link in the network [17]. Wang et al. proposed a multi-level planning model with multiple capacity levels and solved the model by the method of system relaxation and user equilibrium reduction [18]. Wang and Liu developed a mixed-integer nonlinear model that decides whether a link is added to the network and developed a solution algorithm of global optimization method with linearization, external approximation, and range reduction technology [19]. Di et al. studied demand-originated reversible lane design plans for car network and presented a nonlinear bilevel mixed-integer programming model to find the optimal lane combination strategy. In addition, for solving the proposed model, they developed heuristic algorithms to obtain its approximate optimal solution [20].

1.3. The Bus Network Design Problem

For the bus NDP, the main study is to optimize the layout of bus routes, fare levels, and service frequencies, among which the layout of bus routes is the key and difficult. Wan and Lo established a mixed-integer linear programming model to design multiple bus routes simultaneously [21]. Baaj and Mahmasani [22] and Mauttone and Urquhart [23] used the shortest routes as bus routes, and improved them by single node insertion and paired node insertion. Yang et al. [24] and Yu et al. [25] directly generated bus routes using ant colony optimization algorithm. Yao et al. constructed candidate bus routes by deleting and modifying some existing links and applied a tabu search to determine the optimal route set [26]. Amirgholy et al. used a macroscopic approach to optimize the line spacing, stop spacing, headway, and fare of the transit system [27]. Chen and Liu proposed two continuum approximation (CA) models to optimize the design of the hybrid transit network with the objective formula of minimizing the related costs of passengers and operating agencies [28]. Based on the Internet of Things, Feng et al. studied the design of an intelligent bus positioning system to improve the means of bus dispatch and improve the efficiency of bus operations [29].

1.4. The Multimodal Network Design Problem

There are a few studies about the multimodal DNDP, which mainly focus on two aspects: one is how to optimize the bus network considering congestion interaction with other modes. The other one is how to optimize both the car network and the bus network.

For the first aspect, Wan and Lo studied transit network design problem in the multi-modal network and presented a systematic phase-wise methodology that considering both the effect of congestion and integration of modal transfers [30]. Moreover, they modeled inter-route and inter-modal transfers through the state augmented multimodal (SAM) network approach. Uchida et al. established a multimodal network design problem model to solve the problem of optimal frequency design for bus services. They applied sensitivity analysis to define linear approximation functions between the Probit SUE link flows and the design parameters, which are then used as constraints in the sub-problem of the NDP instead of the original stochastic user equilibrium (SUE) condition [31]. Li et al. considered the impact of bike-sharing on transfer, optimized the design problem of the bimodal transit network, and proposed a continuum model to optimize the bimodal transit system and shared bikes in a grid network at the same time [32].

For the second aspect, Gallo et al. optimized both car and bus networks by increasing the capacity of existing roads and the service frequency of bus routes, but the network topology remained unchanged and the added optimization was not considered [33]. Zhang et al. simultaneously optimized the auto network and bus network by establishing a single-level mathematical program with complementarity constraints and solved the model with an active-set algorithm, however, they only considered two transportation modes without considering the modal interactions [34].

Cai et al. reviewed the research status of cycling network planning and design in cold-climate cities in China and worldwide and summarized the relevant methods that can be used in China [35]. Liu et al. investigated the optimal network design problem of bike paths, which are on or adjacent to roadways but are physically separated from motorized traffic within the existing urban network. They proposed a mixed-integer nonlinear nonconvex model for the problem and solved the proposed model with a global optimization method and a matheuristic [36]. In addition, in this paper, based on the optimal scheme of the bike network design problem, we use the known bike routes and walking routes to connect car, bus, rail transit networks as a multimodal transportation network, then study the multimodal transportation DNDP.

In summary, we consider the interactions among various transportation modes and comprehensively optimize the multimodal DNDP of the car, bus, and rail transit, which is meaningful and innovative. The main contributions are listed as follows:

Firstly, the slow travel modes in the multimodal transportation network are considered in this paper, which is usually neglected in existing studies. Apart from walking, bike-sharing has become another popular transfer mode. Therefore, we take the bicycle and walking as transfer modes to describe the modal interactions of car, bus, and rail transit. Secondly, the car, bus, and rail transit network are simultaneously studied for the optimization of multimodal DNDP. Most studies only considered the car network and bus network. However, owing to the large capacity, fast speed, and high comfort of rail transit, it occupies a very important position in multimodal travel behavior. Therefore, it is necessary to consider rail transit into multimodal DNDP. Moreover, a multimodal super network topology is presented, which clearly expresses inter-modal transfers of car, bus, and rail transit networks, as well as inter-route transfers of the bus and rail transit network. Besides, a bi-objective programming model of multimodal DNDP is proposed to make decisions about expanding or adding links in the car, bus, or rail transit network. It aims to minimize the network operation cost and construction cost. Lastly, a hybrid heuristic algorithm based on the minimum cost flow algorithm and the simulated annealing algorithm is developed to efficiently and effectively solve the proposed model. The proposed algorithm in this paper and the branch and bound algorithm proposed by reference [14] are all suitable for solving combinatorial optimization problems. However, the branch and bound algorithm needs more branch operations and consumes more time. Compared with the algorithms proposed by references [18,19], they are improved based on the traditional DNDP model and solve the global optimal solution through the Mix Integer Linear Programming (MILP) solver. While we use mathematical planning methods and network flow theory to establish the multimodal DNDP model and apply heuristic algorithms to efficiently solve the optimal solution. They did not make use of the network structure of relevant problems. In addition, the MILP solver cannot solve the problem of a large number of integer variables to the optimal in a reasonable time, which thus hinders the computational efficiency.

The rest of the paper is organized as follows: In Section 2 a multimodal super network topology is presented. In Section 3 a bi-objective programming optimization model of multimodal DNDP is proposed. In Section 4 a hybrid heuristic algorithm to solve the proposed model is developed. In Section 5 two numerical tests are implemented to validate the proposed model and algorithm. Concluding remarks and possible future research directions are presented in the last section.

2. Multimodal Super Network Topology

2.1. Multimodal Network Representation

There are 5 kinds of transportation modes considered in this paper: car, bus, rail transit, bicycle, and walking. Multimodal transportation weighted directed graph $G=\left(V, A, W, K\right)$. is presented, in which some notations and definitions are shown in

Table 1. The notations and definitions of the multimodal transportation network.

Notations	Definitions
$K$	$\mathrm{Set} \mathrm{of} \mathrm{transportation} \mathrm{modes}. \mathrm{It} \mathrm{includes} \mathrm{car}, \mathrm{rail} \mathrm{transit}, \mathrm{and} \mathrm{bus}, \mathrm{which} \mathrm{are} \mathrm{indexed} \mathrm{by} c,r,\mathrm{and}p$$\mathrm{respectively}. \mathrm{Thus} \mathrm{for} \mathrm{any} \mathrm{mode} k\in K=\left\{c,r,p\right\}$.
$V$	$\mathrm{Set} \mathrm{of} \mathrm{nodes}, \mathrm{node} i\in V$. In a multimodal transportation network, nodes have multiple attributes, which can represent bus stations, rail transit stations, road intersections, and interchange hubs.
$A$	$\mathrm{Set} \mathrm{of} \mathrm{links}, \mathrm{link} \left(i,j\right)\in A. \mathrm{In} \mathrm{this} \mathrm{paper}, \mathrm{the} \mathrm{links} \mathrm{in} \mathrm{topological} \mathrm{networks} \mathrm{are} \mathrm{divided} \mathrm{into} \mathrm{four} \mathrm{types}: A^E$$(\mathrm{the} \mathrm{set} \mathrm{of} \mathrm{entering} \mathrm{links}), A^L$$(\mathrm{the} \mathrm{set} \mathrm{of} \mathrm{leaving} \mathrm{links}), A^D$$(\mathrm{the} \mathrm{set} \mathrm{of} \mathrm{driving} \mathrm{links}), A^T$$(\mathrm{the} \mathrm{set} \mathrm{of} \mathrm{transfer} \mathrm{links}). \mathrm{It} \mathrm{is} \mathrm{concluded} \mathrm{that} A=A^E{{\displaystyle \cup }}^{}{A}^L{{\displaystyle \cup }}^{}{A}^D{{\displaystyle \cup }}^{}{A}^T$.
$A^{E,k}$	Set of the entering links of transportation mode $k$. It means that passengers begin to enter the network.
$A^{L,k}$	Set of leaving links of transportation mode $k$. It indicates that passengers’ leave behavior from the network.
$A^{D,k}$	Set of driving links of transportation mode $k$. It expresses that transportation mode $k$ is driving in the network.
$A^{T,k}$	Set of links for transferring to transportation mode $k$. It includes the transfers between the same or different transportation modes.
$W$	Set of weights, weight $w_{ij}\in W$. The weight of links in the multimodal network has a variety of attributes, which can be represented as a generalized cost formula.

.

The relationship among the elements in the multimodal transportation super network studied in this paper is shown in Figure 1.

2.2. Procedure of Establishing a Multimodal Super Network Topology

In this section, we present a multimodal transportation network that meets two requirements: one expresses the transfer among car, bus and rail transit modes; the other one shows the internal transfer of bus or rail transit mode. As shown in Figure 2, a traveler departs from the origin $O$ to the destination $D$. The transfer relationship among the transportation modes are described as follows: Firstly, passengers on bus line 2 can transfer to rail transit line 1 by transfer node 3, which represents the inter-modal transfer between bus and rail transit. Secondly, node 6 is the transfer station between bus line 2 and bus line 3, which stands for the inter-route transfer in the bus network. Moreover, passengers can drive from node 7 to node 10 and transfer to rail transit line 2 through the transfer link (9,10), which indicates the inter-modal transfer between car and rail transit. Besides, by the transfer node 12 passengers can transfer from rail transit line 1 to rail transit line 2, which shows the inter-route transfer in the rail transit network. Finally, all transfer nodes 3 → 3′, 6 → 6′, and 12 → 12′ are achieved by walking; and transfer links (9,10) and (16,17) are achieved by bike-sharing. Next, based on the super network theory, the process of establishing a multimodal transportation super network topology is as described in the following section.

2.2.1. Bus Network

The bus network is illustrated in Figure 3, which includes three bus routes, namely bus line 1, bus line 2, and bus line 3, where the pink node 6 is the transfer station. The information of routes in the bus network is shown in

Table 2. The information of bus routes.

Line	Link	Transfer Node
1	(7,8) (8,9)	-
2	(1,2) (2,3) (3,4) (4,5) (5,6)	6
3	(6,15) (15,16)	6

.

The transfer node 6 in Figure 3 can be extended to nodes 6 and 6′ through super network expansion, so Figure 3 becomes the bus super network topology, which is shown in Figure 4.

2.2.2. Rail Transit Network

The rail transit network is shown in Figure 5, which contains two rail transit routes, namely rail transit line 1 and rail transit line 2, where the pink node 12 is the transfer station. The information of routes in the rail transit network is shown in

Table 3. The information of rail transit routes.

Line	Link	Transfer Node
1	(3,11) (11,12)	12
2	(10,12) (12,13) (13,14)	12

.

Like transfer node 6 discussed above, the transfer node 12 can be extended to nodes 12 and 12′ by super network expansion. As a result, the rail transit super network topology is as shown in Figure 6.

2.2.3. Car Network

The car network is shown in Figure 7. It contains three car routes, named car route 1, car route 2, and car route 3, respectively. The information of each route in the car network is shown in

Table 4. The information of car routes.

Line	Link	Transfer Node
1	(1,3) (3,6) (6,17)	3
2	(1,3) (3,12) (12,14)	3
3	(7,10) (10,12) (12,14)	12

.

In general, for car mode passengers or drivers needn’t transfer in one trip, so it is unnecessary to expand nodes in the car network, the car super network topology is shown in Figure 8.

In summary, by connecting the same nodes among different modes, a multimodal transportation super network topology (Figure 9) is obtained, of which three layers are bus, rail transit, and car network topology respectively. In Figure 9, the pink dotted links clearly illustrate the inter-modal transfers among bus, rail transit, and car, as well as the inter-route transfers of bus or rail transit.

3. Formulating the Multimodal Discrete Network Design Problem

In this section, firstly the generalized cost formulas of each type of links are defined. Then, a bi-objective programming optimization model of multimodal DNDP will be introduced.

3.1. The Generalized Cost Formula

Many factors affect the impedance of links in the multimodal networks. In this paper, the impact of travel time, monetary cost, and comfort are mainly considered. Among them, travel time includes walking time, driving time, and waiting time. Monetary cost can be divided into two types: mileage-based fare (such as the car mode) and route-based fare (such as the bus and rail transit mode).

The perception of comfort varies with the travel time due to different transportation modes. Besides, we reserve some time to prevent emergencies. Consequently, the generalized cost of links is mainly composed of travel time, monetary cost, and comfort loss, risk reserve time, which is specifically quantized as:

$$w_{ij}^k=\alpha T_{ij}^k+\beta P_{ij}^k+\gamma S_{ij}^k+\delta R_{ij}^k,\hspace{1em}\forall \left(i,j\right)\in A,k\in K$$

(1)

where $\mathsf{\alpha },\beta ,\gamma ,\delta$: the weight coefficients and we have $\alpha +\beta +\gamma +\delta =1$, $T$: the travel time cost, $P$: the corresponding time cost converted from currency conversion, $S$: the corresponding time cost converted from the loss of comfort and $R$: the reserved time for risk.

3.2. The Generalized Cost Formulas of Entering Links and Leaving Links

(1) Travel time

In the actual transportation system, entering links $A^{E,k}$,$\forall k\in \left\{r,p\right\}$ indicate the process of reaching the stations, which mainly include walking time and waiting time; entering links $A^{E,k}$, $k=\left\{c\right\}$ express the process of reaching the parking lot, which mostly includes walking time. Therefore, it can be concluded that the travel time of the entering links mainly consists of walking time and waiting time. Consequently, the travel time of the entering link can be formulated as:

$$T_{ij}^{E,k}=t_{walk,ij}^{E,k}+t_{wait,ij}^{E,k},\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in A^{E,k},k\in K,$$

(2)

where $t_{walk,ij}^{E,k}$: the average walking time of the entering links and $t_{wait,ij}^{E,k}$: the waiting time of the entering links. In this paper, it is set that $t_{wait,ij}^{E,k}=\frac{1}{2f},\forall \left(i,j\right)\in A^{E,k},k\in \{p,r\}$, $f$ is the departure frequency, and $t_{wait,ij}^{E,k}=0, \forall \left(i,j\right)\in A^{E,k},k=\{c\}$.

Meanwhile, in the actual transportation system, leaving links $A^{L,k}$ ($\forall k\in K$) show the process of arriving at the destination, which mostly contains walking time. Hence, the travel time of the leaving links can be described as:

$${\mathrm{T}}_{ij}^{L,k}=t_{walk,ij}^{L,k},\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in A^{L,k},k\in K$$

(3)

where $t_{walk,ij}^{L,k}$ is the average walking time of leaving links.

(2) Monetary cost

Since there is no monetary cost on the entering links and leaving links, we set the monetary cost to zero, which is formulated as:

$$P_{ij}^{E,k}=P_{ij}^{L,k}=0,\hspace{1em}\forall \left(i,j\right)\in A^{E,k}{{\displaystyle \cup }}^{}{A}^{L,k},k\in K$$

(4)

where $P_{ij}^{E,k}$: the monetary cost of entering links and $P_{ij}^{L,k}$: the monetary cost of leaving links.

(3) Comfort loss

Since the trip is very short and the value of comfort loss is very small, we also set the comfort loss to zero on the entering links and leaving links. The equation is as follows:

$${\mathrm{S}}_{ij}^{E,k}={\mathrm{S}}_{ij}^{L,k}=0,\hspace{1em}\forall \left(i,j\right)\in A^{E,k}{{\displaystyle \cup }}^{}{A}^{L,k},k\in K$$

(5)

where $S_{ij}^{E,k}$: the comfort loss of entering links and $S_{ij}^{L,k}$: the comfort loss of leaving links.

(4) Risk reserve time

According to travel time, so we set the risk reservation time of the entering links as:

$$R_{ij}^{E,k}=\left({\rho }_{ij}^{E,k}-1\right)T_{ij}^{E,k},\hspace{1em}\forall \left(i,j\right)\in A^{E,k},k\in K$$

(6)

where ${\rho }_{ij}^{E,k}$: the delay parameter of the entering links, and ${\rho }_{ij}^{E,k}>1, \forall \left(i,j\right)\in A^{E,k},k\in K$.

Similarly, the risk reservation time of the leaving links is formulated as:

$$R_{ij}^{L,k}=\left({\rho }_{ij}^{L,k}-1\right)T_{ij}^{L,k},\hspace{1em}\forall \left(i,j\right)\in A^L,k\in K$$

(7)

where ${\rho }_{ij}^{L,k}$: the delay parameter of leaving links and ${\rho }_{ij}^{L,k}>1, \forall \left(i,j\right)\in A^L,k\in K$.

3.3. The Generalized Cost Formulas of Driving Links

(1) Travel time

In the actual transportation system, driving links $A^{D,k}$, $\forall k\in \left\{c\right\}$, stand for the road between adjacent intersections. In this paper, we set the travel time of car driving links as:

$$T_{ij}^{D,c}=t_{ij}^{D,c0}\left(1+\phi {\left(\frac{x_{ij}+M_{ij}^{D,c}}{\xi c_{ij}^{D,c}}\right)}^{\sigma }\right),\forall \left(i,j\right)\in A^{D,c}$$

(8)

where $t_{ij}^{D,c0}$: the free-flow travel time, $x_{ij}$: the newly assigned traffic flow, $M_{ij}^{D,c}$: the original traffic flow, $c_{ij}^{D,c}$: the capacity of driving links, $\xi$: the average number of passengers and $\phi$,$\sigma$: the undetermined coefficient.

Meanwhile, in the actual transportation system, driving links $A^{D,k}$, $\forall k\in \left\{r,p\right\}$ indicate adjacent stations, and the travel time of the bus and rail transit driving links are set as:

$$T_{ij}^{D,K}=t_{ij}^{D,k},\forall \left(i,j\right)\in A^{D,k},k\in \{p,r\}$$

(9)

where $t_{ij}^{D,k}$: the average travel time of the transportation mode $k$.

(2) Monetary cost

Since the car is charged depending on mileages, in this paper, the monetary cost of the car driving links is described as:

$$P_{ij}^{D,c}=p_{ij}^{D,c0}\ast L_{ij}^{D,c},\forall \left(i,j\right)\in A^{D,c}$$

(10)

where $p_a^{D,c0}$: the monetary cost per unit mileage,

$L_{ij}^{D,c}$: the length of the link $\left(i,j\right)$.

Moreover, as the price of the ticket is up to mileages, the monetary cost of the bus and rail transit driving links are set as:

$$P_{ij}^{D,k}=\{\begin{array}{c}{p}_{ij}^{D,k0} L_{ij}^{D,k}\le L^{D,k0}\\ p_{ij}^{D,k0}+\left[L_{ij}^{D,k}-L^{D,k0}\right]*p_{ij}^{D,k} L_{ij}^{D,k}>L^{D,k0}\end{array},\forall \left(i,j\right)\in A^{D,k},k\in \{p,r\}$$

(11)

where $p_{ij}^{D,k0}$: the starting fare, $L^{D,k0}$: the number of miles corresponding to the starting fare of the mode $k$, $L_{ij}^{D,k}$: the length of the link $\left(i,j\right)$ and $p_{ij}^{D,k}$: the increasing ticket price per unit mileage.

(3) Comfort loss

As the comfort loss is proportional to the travel time on the car network, it can be formulated as:

$${\mathrm{S}}_{ij}^{D,c}={\mathsf{\gamma }}^{D,c}·T_{ij}^{D,c},\forall \left(i,j\right)\in A^D$$

(12)

where: ${\mathsf{\gamma }}^{D,c}$: the degree of comfort loss per unit time of the car mode.

In addition, the comfort loss is mainly determined by travel time and congestion on the bus or rail transit network, so it can be described as:

$${\mathrm{S}}_{ij}^{D,k}=\left({\eta }_0^{D,k}+{\eta }_1^{D,k}\left(max\left(0,q_{ij}^{D,k}-f_{ij}^{D,k}·o_{ij}^{D,k}\right)\right)\right)T_{ij}^{D,k},\forall \left(i,j\right)\in A^D,k\in \{p,r\}$$

(13)

where ${\eta }_0^{D,k}$: the comfort loss parameter when the transportation mode $k$ is empty, ${\eta }_1^{D,k}$: the comfort loss parameter when congestion occurs, $q_{ij}^{D,k}$: the number of passengers, $f_{ij}^{D,k}$: the departure frequency and $o_{ij}^{D,k}$: the capacity of vehicles.

(4) Risk reserve time

Similarly, we set the risk reservation time of the driving links as follows:

$$R_{ij}^{D,k}=\left({\rho }_{ij}^{D,k}-1\right)T_{ij}^{D,k},\hspace{1em}\forall \left(i,j\right)\in A^{D,k},k\in K$$

(14)

where ${\rho }_{ij}^{D,k}$: the delay parameter of driving links and ${\rho }_{ij}^{D,k}>1, \forall \left(i,j\right)\in A^{D,k},k\in K$.

3.4. The Generalized Cost Formulas of Transfer Links

(1) Travel time

It has been mentioned above that the transfer modes mainly consist of walking and bike-sharing. Therefore, the travel time of transferring to the transportation mode $k$ can be formulated as:

$$T_{ij}^{T,k}=t_{walk,ij}^{T,k}+t_{wait,ij}^{T,k},\hspace{1em}\forall \left(i,j\right)\in A^{T,k},k\in K$$

(15)

or:

$$T_{ij}^{T,k}=t_{cycling,ij}^{T,k}+t_{wait,ij}^{T,k},\hspace{1em}\forall \left(i,j\right)\in A^{T,k},k\in K$$

(16)

where $t_{walk,ij}^{T,k}$: the average walking time for transfer to the transportation mode $k$, $t_{cycling,ij}^{T,k}$: the average cycling time for transfer to the transportation mode $k$, $t_{wait,ij}^{T,k}$: the waiting time for transfer to the transportation mode $k$, and we set $t_{wait,ij}^{T,k}=\frac{1}{2f},\forall \left(i,j\right)\in A^{T,k},k\in \{p,r\}$, $f$ is the departure frequency and $t_{wait,ij}^{T,k}=0, \forall \left(i,j\right)\in A^{T,k},k=\{c\}$.

(2) Monetary cost

Since there is no monetary cost for walking, and only the monetary cost of bike-sharing exists, the monetary cost of transferring to the mode $k$ can be represented as:

$$P_{ij}^{T,k}=p_{walk,ij}^{T,k}=0,\forall \left(i,j\right)\in A^{T,k},k\in K$$

(17)

or:

$$P_{ij}^{T,k}=p_{cycling,ij}^{T,k}=\{\begin{array}{c}{p}_{ij}^{T,k0} L_{ij}^{T,k}\le L^{T,k0}\\ p_{ij}^{T,k0}+\left[L_{ij}^{T,k}-L^{T,k0}\right]*p_{ij}^{T,k} L_{ij}^{T,k}>L^{T,k0}\end{array}, \forall \left(i,j\right)\in A^{T,k}, k\in K$$

(18)

where $p_{ij}^{T,k0}$: the starting fare for cycling, $L^{T,k0}$: the number of miles corresponding to the starting fare for cycling, $L_{ij}^{T,k}$: the length of the link $\left(i,j\right)$ and $p_{ij}^{T,k}$: the increasing fare per unit mileage.

(3) Comfort loss

Since the transfer trip is very short and the comfort loss can be ignored, we set the comfort loss of transferring to the transportation mode $k$ as:

$${\mathrm{S}}_{ij}^{T,k}=0,\forall \left(i,j\right)\in A^{T,k},k\in K$$

(19)

(4) Risk reserve time

Similarly, the risk reservation time of transferring to the transportation mode $k$ is expressed as:

$$R_{ij}^{T,k}=\left({\rho }_{ij}^{T,k}-1\right)T_{ij}^{T,k},\hspace{1em}\forall \left(i,j\right)\in A^{T,k},k\in K$$

(20)

where ${\rho }_{ij}^{T,k}$: the delay parameter of transferring to the transportation mode $k$ and ${\rho }_{ij}^{T,k}>1, \forall \left(i,j\right)\in A^T,k\in K$.

3.5. Bi-Objective Programming Model

The objective of multimodal DNDP is to decide on an optimal scheme $U^{*}$ from the candidate schemes $U=\left\{U^c,U^r,U^p\right\}$ to minimize the total cost, which includes the network operation cost and the construction cost of the optimization scheme. $U$ is the set of candidate links; $U^c$ is the set of added or expanded links for the car network; $U^r$ is the set of added or expanded links for the rail transit network, and $U^p$ is the set of added or expanded links for the bus network.

(1) Network operation cost

According to the generalized cost formulas mentioned above, the network operation cost of the multimodal transportation network can be formulated as follows:

$$\begin{gathered} W={\displaystyle \sum }_{\left(i,j\right)\in A{{\displaystyle \cup }}^{}U}{\displaystyle \sum }_{k\in K}{w}_{ij}^k·x_{ij}^k \\ ={\displaystyle \sum }_{\left(i,j\right)\in A{{\displaystyle \cup }}^{}U}{\displaystyle \sum }_{k\in K}(\alpha T_{ij}^k+\beta P_{ij}^k+\gamma S_{ij}^k+\delta R_{ij}^k)·x_{ij}^k \\ ={\displaystyle \sum }_{\left(i,j\right)\in A{{\displaystyle \cup }}^{}U}{\displaystyle \sum }_{k\in K}(\alpha T_{ij}^{\mathit{E,k}}+\beta P_{ij}^{\mathit{E,k}}+\gamma S_{ij}^{\mathit{E,k}}+\delta R_{ij}^{\mathit{E,k}})·x_{ij}^{\mathit{E,k}} \\ +(\alpha T_{ij}^{\mathit{L,k}}+\beta P_{ij}^{\mathit{L,k}}+\gamma S_{ij}^{\mathit{L,k}}+\delta R_{ij}^{\mathit{L,k}})·x_{ij}^{\mathit{L,k}} \\ +(\alpha T_{ij}^{\mathit{D,k}}+\beta P_{ij}^{\mathit{D,k}}+\gamma S_{ij}^{\mathit{D,k}}+\delta R_{ij}^{\mathit{D,k}})·x_{ij}^{\mathit{D,k}} \\ +(\alpha T_{ij}^{\mathit{T,k}}+\beta P_{ij}^{\mathit{T,k}}+\gamma S_{ij}^{\mathit{T,k}}+\delta R_{ij}^{\mathit{T,k}})·x_{ij}^{\mathit{T,k}} \end{gathered}$$

(21)

Here, $x_{ij}^k$ is the traffic flow of the link $\left(i,j\right)$.

(2) Construction cost

For DNDP, there are two methods to optimize the network: one is to add a new link; the other one is to expand the original link. In the multimodal super network topology, an added link is to connect two unconnected nodes, while an expanded link is to add a link to the originally connected nodes.

As shown in Figure 10: for the car network, since node 3 and node 14 were not connected originally, the added link (3,14) (the blue dotted link) represents the added optimization. Meanwhile, as node 7 and node 10 were connected originally, so link (7,10) (the blue dotted link) illustrates the expanded optimization. Therefore, we use the 0-1 variable $y_{ij}^c$ and $z_{ij}^c$ to respectively express whether to add or expand links. If the link $\left(i,j\right)$ is added/expanded, $y_{ij}^c/z_{ij}^c$ is equal to 1, otherwise $y_{ij}^c/z_{ij}^c$ is equal to 0, $\forall \left(i,j\right)ϵU^c$

For the bus network, the added method indicates adding a new link on the existed route, like link (16,17) (the green dotted link). The expanded method means to increase the frequency of departure, so it will change the whole route, such as link (1,2), (2,3), (3,4), (4,5), (5,6) (the green dotted link). Hence, if the link $\left(i,j\right)$ is added/expanded the 0–1 variable $y_{ij}^p/z_{ij}^p$ is equal to 1, otherwise $y_{ij}^p/z_{ij}^p$ is equal to 0, $\forall \left(i,j\right)ϵU^p$ in the bus network.

Similarly, for the rail transit network, the added method expresses to add a new link on the existed route, like link (1,3) (the red dotted link). And the expanded method represents to increase the frequency of departure, so it will change the whole route, such as links (10,12), (12,13), (13,14) (the red dotted link). Thus, if the link $\left(i,j\right)$ is added/expanded the 0–1 variable $y_{ij}^r/z_{ij}^r$ is equal to 1, otherwise $y_{ij}^r/z_{ij}^r$ is equal to 0, $\forall \left(i,j\right)ϵU^r$ in the rail transit network.

Consequently, the construction cost of the optimization scheme is formulated as:

$$\begin{gathered} B={\displaystyle \sum }_{\left(i,j\right)\in U}{\displaystyle \sum }_{k\in K}{B}_{ij}^{k1}·y_{ij}^k+B_{ij}^{k2}·z_{ij}^k \\ ={\displaystyle \sum }_{\left(i,j\right)\in U^c}(B_{ij}^{c1}·y_{ij}^c+B_{ij}^{c2}·z_{ij}^c)+{\displaystyle \sum }_{\left(i,j\right)\in U^{p }}(B_{ij}^{p1}·y_{ij}^p+B_{ij}^{p2}·z_{ij}^p) \\ +{\displaystyle \sum }_{\left(i,j\right)\in U^{r }}(B_{ij}^{r1}·y_{ij}^r++B_{ij}^{r2}·z_{ij}^r) \end{gathered}$$

(22)

where $B_{ij}^{k1}$: the cost of the added link $\left(i,j\right)$ for the mode $k, \forall k\in K$ and $B_{ij}^{k2}$: the cost of the expanded link $\left(i,j\right)$ for the mode $k, \forall k\in K$.

(3) Bi-objective programming model

In summary, a bi-objective programming model for multimodal DNDP is proposed based on Equations (21) and (22) to minimize the network operation cost and construction cost as follows:

$$\min Z\left(x,y,z\right)=\min \left[\theta W+\tau B\right]=min[\theta {\displaystyle \sum }_{\left(i,j\right)\in A{{\displaystyle \cup }}^{}U}{\displaystyle \sum }_{k\in K}{w}_{ij}^k·x_{ij}^k+\tau {\displaystyle \sum }_{\left(i,j\right)\in U}{\displaystyle \sum }_{k\in K}(B_{ij}^{k1}·y_{ij}^k++B_{ij}^{k2}·z_{ij}^k)]$$

(23)

$$s.t.·········0\le {{\displaystyle \sum }}_{\left(i,j\right)\in U}{B}_{ij}^{c1}·y_{ij}^c+B_{ij}^{c2}·z_{ij}^c\le B{G}^c\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in U^c$$

(24)

$$0\le {{\displaystyle \sum }}_{\left(i,j\right)\in U}{B}_{ij}^{p1}·y_{ij}^p+B_{ij}^{p2}·z_{ij}^p\le B{G}^{p }\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in U^p$$

(25)

$$0\le {{\displaystyle \sum }}_{\left(i,j\right)\in U}{B}_{ij}^{r1}·y_{ij}^r+B_{ij}^{r2}·z_{ij}^r\le B{G}^r\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in U^r$$

(26)

$$0\le x_{ij}^k+M_{ij}^k\le c_{ij}^k+y_{ij}^k{c}_{ij}^{k{1}^{\prime }}+z_{ij}^k{c}_{ij}^{k{2}^{\prime }}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in A{{\displaystyle \cup }}^{}U, k\in K$$

(27)

$${{\displaystyle \sum }}_i{x}_{ri}^E-{{\displaystyle \sum }}_i{x}_{ir}^E=q_{rs}\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in A{{\displaystyle \cup }}^{}U,k\in K$$

(28)

$${{\displaystyle \sum }}_i{x}_{si}^L-{{\displaystyle \sum }}_i{x}_{is}^L=-q_{rs }\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in A{{\displaystyle \cup }}^{}U,k\in K$$

(29)

$${{\displaystyle \sum }}_i{x}_{ij}^k-{{\displaystyle \sum }}_i{x}_{ji}^k=0\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in A{{\displaystyle \cup }}^{}U,k\in K$$

(30)

$$x_{ij}^k\ge 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)ϵA{{\displaystyle \cup }}^{}U,k\in K$$

(31)

$${{\displaystyle \sum }}_{\left(i,j\right)\in A{{\displaystyle \cup }}^{}U}{z}_{ij}^k=\omega ·N,\hspace{1em}\hspace{1em}\hspace{1em}\forall \left(i,j\right)\in A{{\displaystyle \cup }}^{}U,k\in \{p,r\}$$

(32)

where $\theta$, $\tau$: the weight coefficients and we have $\theta +\tau =1$, $B{G}^k$: the budget cost of the transportation mode $k$, $M_{ij}^k$,$c_{ij}^k$: the original traffic flow and the original capacity of the link $\left(i,j\right)$ respectively, $q_{rs}$: the traffic demand of OD pair $rs$, ${c_{ij}^{k1}}^{\prime }/{c_{ij}^{k2}}^{\prime }$: the capacity of the added/expanded link $\left(i,j\right)$ for the mode $k$,$\omega$: the binary variable, if the link $\left(i,j\right)$ is expanded, $\omega$ is equal to 1, otherwise, $\omega$ is equal to 0 on the bus or rail transit route and $N$: the number of expanded links on the bus or rail transit route.

Constraints (24)–(26) indicate that the cost of optimization schemes is less than the budget cost for car, bus, and rail transit network.

Constraint (27) shows that the sum of the assigned traffic flow and the original traffic flow is less than the sum of the original capacity and the increased capacity of the added or expanded optimization.

Constraints (28)–(31) are traffic flow equilibrium constraints, where constraint (28) means that for the starting point, the outflow minus the inflow is equal to $q_{rs}$. Constraint (29) shows that for the destination point, the outflow minus the inflow is equal to $-q_{rs}$. Constraint (30) expresses that for each node, the outflow and inflow must be equal. Constraint (31) indicates that the traffic flow cannot be less than zero.

Constraint (32) ensures that the expanded method will change the whole existed route for the bus and rail transit network. Specifically, if one link of the route is expanded, then the other links must be expanded.

4. Solution Algorithm

Since there are two types of decision variables in the proposed optimization model: the assignment of traffic flow and the decision of adding or expanding candidate links, the algorithm is divided into two parts:

Firstly, we need to assign the traffic flow to minimize the network operation cost. Since the capacity of each link is considered in the proposed model, it is appropriate that the minimum cost flow algorithm is applied to solve this problem.

Secondly, as multimodal DNDP is an integrated optimization problem, conventional solving algorithms are difficult to solve efficiently, heuristic algorithms are developed in this paper: simulated annealing algorithm to search the near-optimal decision $U^{*}$ from the candidate schemes $U=\left\{U^c,U^r,U^p\right\}$.

4.1. Minimum Cost Flow Algorithm

Let ${\mu }_k$ be the minimum cost augmentation chain of the $k$-th iteration, ${\epsilon }_k$ be the adjustable flow on the augmentation chain ${\mu }_k$, and $x^k$ be the feasible flow of the $k$-th iteration. Based on the shortest path method, a network $L\left(x\right)$ is constructed, whose nodes are the nodes of the original network $G$, specifically, the link $(v_i,v_j)$ of the original network $G$ is changed into two links with opposite directions $(v_i,v_j)$ and $\left(v_j,v_i\right)$. Define the weights of links $(v_i,v_j)$ and $\left(v_j,v_i\right)$ in $L\left(x\right)$ as $l_{ij}$ and $l_{ji}$:

$$l_{ij}=\{\begin{array}{c}{w}_{ij} \mathrm{if} x_{ij}<c_{ij} \\ +\infty \mathrm{if} x_{ij}=c_{ij}\end{array},$$

(33)

$$l_{ji}=\{\begin{array}{l}-w_{ij} \mathrm{if} x_{ij}>0 \\ +\infty \mathrm{if} x_{ij}=0\end{array}$$

(34)

Set the matrix $\mathit{D}={\left(d_{ij}\right)}_{n\times n}$, $d_{ij}$ represents the shortest length from $v_i$ to $v_j$ in the original network $G$; $\mathit{S}={\left(s_{ij}\right)}_{n\times n}$, $s_{ij}$ represents the end number of the first link of the shortest path from $v_i$ to $v_j$. For example, if $s_{ij}^{\left(n\right)}=t$, the first link of the shortest path from $v_i$ to $v_j$ is $\left(v_i,v_t\right)$.

Above all, the algorithm for solving the minimum cost feasible flow with the target flow $q_{rs}$ is as follows:

Step 1: Set $k$ = 0

Start with a minimum cost initial feasible flow $x^{\left(0\right)}, \left(x^{\left(0\right)}\le q_{rs}\right)$ (generally, $x^{\left(0\right)}=0$).

Step 2: Generate $L\left(x^{\left(k\right)}\right)$, find the minimum cost path from $v_r$ to $v_s$ in $L\left(x^{\left(k\right)}\right)$, and use the Floyd algorithm to solve the shortest path.

Step 2.1: Set $m=0$

$${\mathit{D}}^{\left(0\right)}={\left(d_{ij}^{\left(0\right)}\right)}_{n\times n},d_{ij}^{\left(0\right)}=\{\begin{array}{c}{w}_{ij} \left(v_i,v_j\right)\in A\\ \infty \left(v_i,v_j\right)\notin A\\ 0 v_i=v_j \end{array}$$

(35)

$${\mathit{S}}^{\left(0\right)}={\left(s_{ij}^{\left(0\right)}\right)}_{n\times n},s_{ij}^{\left(0\right)}=j(i,j=1,2,\cdots ,n).$$

(36)

Step 2.2: $m=m+1$

Calculate:

$${\mathit{D}}^{\left(m\right)}={\left(d_{ij}^{\left(m\right)}\right)}_{n\times n,}{\mathit{S}}^{\left(m\right)}={\left(s_{ij}^{\left(m\right)}\right)}_{n\times n}$$

(37)

where:

$$d_{ij}^{\left(m\right)}=min\left\{d_{ij}^{\left(m-1\right)},d_{im}^{\left(m-1\right)}+d_{mj}^{\left(m-1\right)}\right\},$$

(38)

$$s_{ij}^{\left(m\right)}=\{\begin{array}{c}{s}_{ij}^{\left(m-1\right)} d_{ij}^{\left(m-1\right)}\le d_{im}^{\left(m-1\right)}+d_{mj}^{\left(m-1\right)} \\ s_{im}^{\left(m-1\right)} d_{ij}^{\left(m-1\right)}\ge d_{im}^{\left(m-1\right)}+d_{mj}^{\left(m-1\right)}\end{array}.$$

(39)

If $m\ne n$ go to step 2.2, else go to step 2.3.

Step 2.3: when $m=n$, the algorithm ends.

${\mathit{D}}^{\left(n\right)}={\left(d_{ij}^{\left(n\right)}\right)}_{n\times n}$, $d_{ij}^{\left(n\right)}$ is the shortest path length from $v_i$ to $v_j$;

${\mathit{S}}^{\left(n\right)}={\left(s_{ij}^{\left(n\right)}\right)}_{n\times n}$, $s_{ij}^{\left(n\right)}$ is the end node of the first link in the shortest path from $v_i$ to $v_j$.

Step 3: If $L\left(x^{\left(k\right)}\right)$ does not have the shortest path from $v_r$ to $v_s$, then $x^{\left(k\right)}$ is regarded as the maximum flow, there is no minimum cost flow with the target flow of $q_{rs}$, end the algorithm; otherwise, go to the next step.

Step 4: Find the augmented chain ${\mu }_k$ corresponding to the shortest path from $v_r$ to $v_s$ in $L\left(x^{\left(k\right)}\right)$ in the original network $G$, and calculate ${\epsilon }_k=\min \left\{\min \left(c_{ij}-x_{ij}^k\right), \min x_{ij}^k\right\}$. If ${\epsilon }_k\le q_{rs}-x^{\left(k\right)}$, according to the maximum flow adjustment scheme, adjust the augmented flow ${\epsilon }_k$ on the augmented chain ${\mu }_k$ to obtain a new flow $x^{\prime }=x^{\left(k\right)}+{\epsilon }_k$, and let $k=k+1$, assign new flow $x^{\prime }$ to $x^k$, go to step 2; otherwise, when ${\epsilon }_k>q_{rs}-x^{\left(k\right)}$, adjust the augmented flow $q_{rs}-x^{\left(k\right)}$ on the augmented chain ${\mu }_k$ to obtain a new flow $x^{\prime }$, where $x^{\prime }$ is the minimum feasible flow of the target flow $q_{rs}$. End the algorithm.

4.2. Simulated Annealing Algorithm

(1) Determination of solution space

In this problem, all the possible added and expanded candidate schemes $U=\left\{U^c,U^r,U^p\right\}$ constitute the solution space, and a specific candidate scheme can be regarded as a partition of the set $U=\left\{U_1,\dots ,U_m\right\}$, where ${{\displaystyle \cup }}_{i=1}^m{U}_i=U$, $U_i{{\displaystyle \cap }}^{}{U}_j=\varnothing ,i\ne j$, and $U_i$ or $U_j$ is the feasible solution. The solution space is composed of all possible partitions, that is $S=\left\{\left\{U_1,\cdots ,U_m\right\},{{\displaystyle \cup }}_{i=1}^m{U}_i=U,U_i{{\displaystyle \cap }}^{}{U}_j=\varnothing ,i\ne j\right\}$

(2) Objective formula

According to the discussion presented in Section 3.5, the objective function of the optimization schemes $\left\{U_1,\cdots ,U_m\right\}$ can be defined as:

$$f\left\{U_1,\cdots ,U_m\right\}=\min [\theta {\displaystyle \sum }_{\left(i,j\right)\in A{{\displaystyle \cup }}^{}U}{\displaystyle \sum }_{k\in K}{w}_{ij}^k·x_{ij}^k+\tau {\displaystyle \sum }_{\left(i,j\right)\in U}{\displaystyle \sum }_{k\in K}(B_{ij}^{k1}·y_{ij}^k++B_{ij}^{k2}·z_{ij}^k)]$$

(40)

(3) The choice of initial solution

The initial solution is the initial point of the simulated annealing algorithm. A large number of experiments show that the final solution of the simulated annealing algorithm does not depend on the selection of the initial solution, so we randomly choose an initial as $U_i,i\in \left\{1,\cdots ,m\right\}$.

(4) The generation of a new solution

For this algorithm, we first need to use a certain strategy to generate a new solution based on the current solution in the space, then decide whether to accept the new solution. When the new solution is accepted, which will be treated as a new current solution, and the value of the objective function is modified correspondingly. The next iteration is started on this basis. If the new solution is not accepted, the next experiment will be continued based on the current solution.

Since the proposed optimization model is a binary integer programming, we can arbitrarily choose $u\in U_i$. If $u$ is 0, it will be replaced by 1; otherwise, if it is 1, it will be replaced by 0. Therefore, a new solution $U_j$ is generated and the difference of values of the objective function in two iterations can be calculated by the following formula:

$$△f_{ji}=f\left(U_j\right)-f\left(U_i\right)$$

(41)

(5) Acceptance criterion

An acceptance criterion is set to judge whether the new solution is accepted or not. Generally, the most commonly used acceptance criteria is Metropolis criteria:

$$\rho =\{\begin{array}{ll}1& △f_{ji}<0\\ \exp \left(-△f_{ji}/t\right)& △f_{ji}\ge 0\end{array}$$

(42)

where $t$ is the control parameter.

According to the settings above, the procedure of the simulated annealing algorithm is listed as follows:

Step 1: Randomly select an initial solution $U_i$, let the current solution $U_0=U_i$; the current number of iteration steps $k=0$; the current temperature $t_k=t_{max}$.

Step 2: When reaching the maximum number $M$ of iterations the inner loop, go to step 3; otherwise, randomly select a neighbor $U_j$ from the neighborhood $N\left(U_i\right)$ and calculate $△f_{ji}$, if $△f_{ji}\le 0$ then $U_i=U_j$, otherwise, if $\exp \left(-△f_{ji}/t_k\right)>\mathrm{random}\left(0,1\right)$ (represents a uniform random number between 0 and 1), then $U_i=U_j$, repeat step 2.

Step 3: $k=k+1,t_{k+1}=d\left(t_k\right)$ (representing the formula of temperature drop), and the classic simulated annealing algorithm cooling formula is $d\left(t_k\right)=\frac{t_0}{1+t_k}$. If the end temperature $t_{end}$, is reached, go to Step 4, otherwise, go to Step 2.

Step 4: Output the calculation result and stop.

As shown in Figure 11, the simulated annealing algorithm includes an inner loop and an outer loop. The inner loop is the second step, which means random search in the neighborhood $N\left(U_i\right)$ at the same temperature $t$. The outer loop mainly includes the temperature drop change $t_{k+1}=d\left(t_k\right)$, the number of iteration steps $k=k+1$, and the stop condition in the third step.

Consequently, we combine the minimum cost flow algorithm and simulated annealing algorithm as a hybrid heuristic algorithm that can solve the proposed model. The relationship between the minimum cost flow algorithm and the simulated annealing algorithm is shown in Figure 11. The minimum cost flow algorithm will be used to assign traffic flow before solving the objective function in each iteration of the simulated annealing algorithm.

5. Numerical Examples

In this section, two numerical tests are implemented to validate the proposed model and algorithm: a simple test network (the multimodal transportation network shown in Figure 2) and an actual network (an area of Beijing, China). All experiments are executed in Python software on a Lenovo laptop configured with an Intel Core i5-8250U 3.40 GHz CPU equipped with 8 GB RAM.

5.1. Simple Network

Before optimization, the maximum feasible flow of the network is 78, and the traffic demand $q_{rs}$ is 100, so it is necessary to improve the network. According to the passenger demand, some candidate links are given, as shown in Figure 12: the blue dotted links (3,14), (7,10) are the candidate links for the car network, namely $U^c$={(3,14), (7,10)}; the green dotted link (16,17) is the candidate link for the bus network, namely $U^p$={(16,17)}; the red dotted link (1,3) is the candidate link for the rail transit network, namely $U^r$={(1,3)}. Therefore, it can be concluded that the set of candidate schemes $U=\left\{U^c,U^r,U^p\right\}$= {(3,14), (7,10), (16,17), (1,3)}, so there are in total 2⁴ schemes. Next, we will use the exact algorithm and heuristic algorithm respectively to find the near-optimal scheme $U^{*}$ from the 2⁴ schemes.

(1) Exact algorithm

To test the feasibility of the developed heuristic algorithm, an exact algorithm is first used to solve the model. The specific steps are as follows:

Step 1: Calculate the generalized cost of each type of links

Firstly, give the information of links for each network in the multimodal transportation, among which, the car network mainly includes length (km), zero traffic flow driving time (min), existing vehicle (pcu/h), capacity (pcu/h); the bus network and rail transit network mainly include average driving time (min), frequency (number/ hour); transfer network mainly includes length (km), walking time (min) and cycling time (min). Then, calculate the generalized cost of each type of links according to the formulas in Section 3, and the results are shown in Figure 13: in brackets, the first term is the generalized cost of links and the second term is the capacity of links.

As shown in Figure 13: in the multimodal transportation super network topology, the blue dotted links (26,27) and (23,29) respectively represent the candidate links (3,14), (7,10) (in Figure 12) for the car network; the red dotted link (14,15) stands for the candidate link (1,3) (in Figure 12) for the rail transit network, and the green dotted link (12,13) expresses the candidate link (16,17) (in Figure 12) for the bus network.

Step 2: Traffic flow assignment

The minimum cost flow algorithm is coded by PYTHON based on the steps in Section 4.1 to assign the traffic flow. The traffic flow assignment and the composition of transportation mode for each shortest path are obtained, as shown in

Table 5. The traffic flow assignment and composition of transportation mode for the shortest path.

Number	Path	Traffic Mode	Traffic Flow
1	14-15-16-17-19-20-21	R1-R2	34
2	7-8-9-18-19-20-21	B1-R2	11
3	22-23-24-25	C	16
4	22-23-29	C	14
5	26-27-28-29	C	24
6	1-2-3-4-5-6-10-11-12-13	R2-R3	1

, in which all candidate links are taken.

Step 3: Calculate the value of the objective function

The optimal result of traffic flow assignment in step 2 is used to calculate the value of the network operation cost by Equation (21); then based on the optimization cost and the budget cost of each candidate link to calculate the value of construction cost by Equation (22); finally, the weighted sum of the operation cost and the construction cost by Equation (23) is the value of the objective function. When the generalized cost formula coefficients $\alpha$ = 0.25,$\beta$= 0.25, $\gamma$ = 0.25, $\delta =$0.25 in Equation (1), and the objective function weight coefficients $\theta =$ 0.5,$\tau =$ 0.5 in Equation (23), the calculation results are illustrated in

Table 6. Optimization results of the exact algorithm.

(7,10)	(3,14)	(1,3)	(16,17)	Flow	$\mathit{W}$	$\mathit{B}$	$\mathit{Z}$
0	0	0	0	78	3429	-	-
1	0	0	0	90	4041	-	-
0	1	0	0	78	3428	-	-
0	0	1	0	100	4114	3000	3557
0	0	0	1	78	3365	-	-
1	1	0	0	90	4028	-	-
1	0	1	0	100	3958	4000	3979
1	0	0	1	90	3977	-	-
0	1	1	0	100	4044	5000	4522
0	1	0	1	78	3364	-	-
0	0	1	1	100	4062	3500	3781
1	1	1	0	100	3888	6000	4944
1	0	1	1	100	3954	4500	4227
1	1	0	1	90	3964	-	-
0	1	1	1	100	3992	5500	4746
1	1	1	1	100	3884	6500	5192

and Figure 14.

It can be concluded from Table 6 and Figure 14 that the optimal solution of the exact algorithm is $U^{*}=$ (1,3), and the corresponding operation cost is 4114, construction cost is 3000, and total cost is 3557. Some schemes are without values of construction cost $B$ and objective function $Z$ in Table 6. Because the maximum feasible flow of the schemes does not reach $q_{rs}$ = 100, so the optimization schemes are not adopted, and there is no need to calculate the objective function.

(2) Heuristic algorithm

Similarly, the developed heuristic algorithm is also coded by PYTHON based on the steps in Section 4.2 to solve the model, and we set the initial temperature $t_{max}$ = 500, the end temperature $t_{end}$ = 100, the maximum number of iterations $M$ = 50. Besides, according to Equation (43), the relative error between the heuristic algorithm and the exact algorithm is calculated. The results are shown in

Table 7. Comparison between the heuristic algorithm and the exact algorithm.

Algorithm	Optimization Scheme	Transportation Mode	$\mathit{Z}$	$\mathit{G}\mathit{A}\mathit{P}$
Heuristic algorithm	(1,3)	rail transit	3557	0.00%
Exact algorithm	(1,3)	rail transit	3557

.

GAP= (near-optimal solution − exact solution)/exact solution × 100%

(43)

Clearly, the solution calculated by the heuristic algorithm is the same as the exact algorithm, which verifies the effectiveness and feasibility of the heuristic algorithm. To further test the heuristic algorithm, then we carry out sensitivity analysis of parameters in Equations (1) and (23).

(3) Sensitivity analysis

In this section, the sensitivity analysis is carried out on the weight coefficients of the generalized cost formula Equation (1) $\alpha , \beta , \gamma , \delta$ and the weight coefficients of the objective formula Equation (23) $\theta ,\tau$. The specific results are listed in

Table 8. Comparison between heuristic and exact algorithm under different weight coefficients.

$\mathit{\alpha }$	$\mathit{\beta }$	$\mathit{\gamma }$	$\mathit{\delta }$	$\mathit{\theta }$	$\mathit{\tau }$	Exact Algorithm		Heuristic Algorithm		$\mathit{G}\mathit{A}\mathit{P}$
						Optimization Scheme	$\mathit{Z}$	Optimization Scheme	$\mathit{Z}$
0.25	0.25	0.25	0.25	0.9	0.1	(1,3), (7,10)	3962.2	(1,3), (7,10)	3962.2	0.00%
0.25	0.25	0.25	0.25	0.1	0.9	(1,3)	3111.4	(1,3)	3111.4	0.00%
0.4	0.4	0.1	0.1	0.5	0.5	(1,3)	3876.6	(1,3)	3876.6	0.00%
0.4	0.4	0.1	0.1	0.9	0.1	(1,3), (7,10)	4532.3	(1,3), (7,10)	4532.3	0.00%
0.4	0.4	0.1	0.1	0.1	0.9	(1,3)	3281.2	(1,3)	3281.2	0.00%
0.6	0.2	0.15	0.05	0.5	0.5	(1,3), (3,14)	4927.3	(1,3), (3,14)	4927.3	0.00%
0.6	0.2	0.15	0.05	0.9	0.1	(1,3),(7,10),(16,17)	4028.6	(1,3),(7,10),(3,14)	4079.2	1.26%
0.6	0.2	0.15	0.05	0.1	0.9	(1,3)	3356.4	(1,3)	3356.4	0.00%
0.2	0.6	0.05	0.15	0.5	0.5	(1,3), (16,17)	3241.7	(1,3), (16,17)	3241.7	0.00%
0.2	0.6	0.05	0.15	0.9	0.1	(1,3),(3,14),(16,17)	4239.6	(1,3),(3,14)	4245.7	0.14%
0.2	0.6	0.05	0.15	0.1	0.9	(1,3)	3027.3	(1,3)	3027.3	0.00%

.

It can be seen from Table 8 that the results obtained by the heuristic algorithm are basically consistent with the exact solution, and only two calculation results deviate from the exact value. Moreover, the relative errors of the two results obtained by the two algorithms are within 1.5%, which validates the effectiveness and reliability of the heuristic algorithm within the allowable error range. In addition, the exact algorithm takes several hours to obtain the optimal solution, while the heuristic algorithm takes only within 56 s. Therefore, the heuristic algorithm is superior to the exact solution algorithm in terms of calculation time.

5.2. Actual Network

The actual transportation network in this case is an area from Xizhimen to Dongdan in Beijing, China. It is one of the busiest traffic areas in Beijing. The network of this area includes multiple bus, rail transit lines and integrates various travel modes, such as car, rail transit, bus, bicycle, and walking. It has many important transfer hub stations. So it is a typical multimodal transportation network. Moreover, there are many facilities for sharing bicycles near each transfer station, which facilitates passengers’ transfer behavior. That is consistent with the model proposed in this paper, which takes bike-sharing as a transfer mode. In addition, due to the huge passenger demand from Xizhimen to Dongdan and the bottleneck of the transportation network, the network capacity is insufficient. Thus, it is necessary to expand or add some links for the car, bus, and rail networks respectively. This is also an important reason why this regional network is selected as an actual case. The multimodal transportation network diagram is as follows, which combined car, bus, and rail transit modes.

As shown in Figure 15: the origin is Xizhimen while the destination is Dongdan. The transfer relationship among modes is as follows, among them, the pink nodes are the transfer stations:

• Firstly, inter-modal transfers between bus and rail transit include 3 routes: (1) bus line 1 → rail line 3; (2) bus line 2 → rail line 3; (3) bus line 3→ bus line 4 → rail line 2.
• Secondly, the inter-route transfers in the bus network include 2 routes: (1) bus line 3 → bus line 5; (2) bus line 3 → bus line 4 → bus line 5.
• Moreover, the inter-route transfer in the rail transit network only includes 1 route: rail line 2 → rail line 3.
• Besides, the inter-modal transfer between car and rail transit includes 1 route: passengers drive from the origin Xizhimen to node 13 and transfer to rail line 3 by node 13.

Before optimization, the maximum feasible flow of the network is 1524, and the traffic demand $q_{rs}$ is 2000, so it is necessary to improve the network. According to the passenger demand, the candidate links are given, as shown by the dotted line in Figure 15: for the car network, the blue dotted links (1,2), (2,3) represent the expansion optimization, and the blue dotted link (3,7) is the candidate link for the adding optimization, namely $U^c$={(1,2), (2,3), (3,7)}; for the bus network, the green dotted links (12,13), (15,16), (17,20) are the candidate links for adding optimization, namely $U^p$={(12,13), (15,16), (17,20)}; for the rail transit network, the red dotted link (6,7) is the candidate link for adding optimization, namely $U^r$ = {(6,7)}. Therefore, it can be concluded that the set of candidate schemes $U=\left\{U^c,U^r,U^p\right\}$ = {(1,2), (2,3), (3,7), (12,13), (15,16), (17,20), (6,7)}, so there are totally 2⁷ schemes. Next, we use the heuristic algorithm to find the near-optimal scheme from the 2⁷ schemes.

The multimodal transportation super network topology is built and the link information of each network is given to calculate the generalized cost of each type of links, as shown in Figure 16: in brackets, the first term is the generalized cost of links and the second term is capacity of links.

Finally, the proposed heuristic algorithm will be coded by PYTHON for the numerical test based on Section 4, which combines the minimum cost flow algorithm and simulated annealing algorithm. And we set the initial temperature $t_{max}$ = 1000, the end temperature $t_{end}$ = 100, the maximum number of iterations $M$ = 200. To analyze the optimal schemes under different weight coefficients, 12 groups of numerical experiments are carried out. The near-optimal schemes under different weight coefficients are shown in the table below.

It can be concluded from

Table 9. Optimization results of the actual network under different weight coefficients.

Case	$\mathit{\alpha }$	$\mathit{\beta }$	$\mathit{\gamma }$	$\mathit{\delta }$	$\mathit{\theta }$	$\mathit{\tau }$	Optimization Schemes	$\mathit{Z}$
1	0.25	0.25	0.25	0.25	0.5	0.5	(1,2), (2,3), (12,13), (15,16)	56823.0
2	0.25	0.25	0.25	0.25	0.9	0.1	(1,2), (2,3), (12,13), (15,16), (17,20)	78161.4
3	0.25	0.25	0.25	0.25	0.1	0.9	(1,2), (12,13), (15,16), (17,20)	34684.6
4	0.4	0.4	0.1	0.1	0.5	0.5	(1,2), (2,3), (12,13), (15,16)	62457.3
5	0.4	0.4	0.1	0.1	0.9	0.1	(1,2), (2,3), (12,13), (15,16), (17,20)	84172.2
6	0.4	0.4	0.1	0.1	0.1	0.9	(1,2), (12,13), (15,16), (17,20)	41435.1
7	0.6	0.2	0.15	0.05	0.5	0.5	(1,2), (2,3), (12,13), (15,16)	65381.5
8	0.6	0.2	0.15	0.05	0.9	0.1	(1,2), (2,3), (12,13), (6,7)	70242.2
9	0.6	0.2	0.15	0.05	0.1	0.9	(1,2), (2,3), (12,13), (15,16)	62369.7
10	0.2	0.6	0.05	0.15	0.5	0.5	(1,2), (12,13), (15,16), (17,20)	52854.8
11	0.2	0.6	0.05	0.15	0.9	0.1	(1,2), (2,3), (12,13), (15,16), (17,20)	75254.6
12	0.2	0.6	0.05	0.15	0.1	0.9	(1,2), (12,13), (15,16), (17,20)	30357.3

that the choice of the near-optimal scheme is affected by the weight coefficients:

(1)

When the value of $\mathit{\alpha }$ is larger than $\mathit{\beta }$ in Equation (1), the travel time is the main priority, and passengers are more willing to choose the car mode that can reach the destination quickly. In this case, when $\mathit{\alpha }$ = 0.6 (group 8,9,10), the car’s candidate links (1,2), (2,3) are all adopted in various groups, which are consistent with the choice of passengers. On the contrary, the monetary cost is focused on, and passengers prefer to choose the transportation mode that can save a lot of money. While $\mathit{\beta }$ = 0.6 (group 11,12,13), the bus’s candidate links (12,13), (15,16), (17,20) are all adopted in various groups, which are also tally with the actual situation

(2)

When the value of $\mathit{\theta }$ is larger than $\mathit{\tau }$ in Equation (23), the decision-maker pays more attention to the network operation cost. In this case, when $\mathit{\theta }$ = 0.9 (group 2,5,8,11), the car’s candidate links (1,2), (2,3) are the principal part of the near-optimal scheme under different groups. Conversely, the construction cost is mainly considered. While $\mathit{\tau }$ = 0.9 (group 3,6,9,12), the bus’s candidate links (12,13), (15,16), (17,20) are the main component of the near-optimal scheme in various groups. These are consistent with the actual situation, which proves that the developed heuristic algorithm can efficiently find the near-optimal solution with good stability and reliability.

Therefore, in an actual operation situation, the value of each parameter can be set according to the attention of the decision-maker, for example, when the travel time is more important, the value of $\alpha$ is larger than $\beta$, otherwise, the monetary cost is mainly considered; when decision-maker pays more attention to the operation cost, the value of $\theta$ is larger than $\tau$, conversely, the construction cost is principal considered.

Consequently, the good results of the two numerical tests are obtained in this section, which shows that the proposed model and developed algorithm in this paper are feasible and efficient.

6. Conclusions

In this paper, we comprehensively optimize a multimodal transportation DNDP that is composed of car, bus, rail transit, bicycle, and walking. Firstly, a multimodal super network topology that includes four types of links (entering links, leaving links, driving links, transfer links) is proposed, which clearly expresses inter-modal transfers among car, bus, and rail transit networks, as well as inter-route transfers in the bus or rail transit network. And to complete the above transfers, walking and bike-sharing are considered as transfer modes. Specifically, in Section 2 we present a simple multimodal transportation network that meets two types of the above transfer relationships and we also discuss the process of establishing a multimodal transportation super network topology. Secondly, the generalized cost formulas of each type of links in the super network topology are defined. Among them, the generalized cost is mainly composed of four types, namely travel time, monetary cost, and comfort loss, risk reserve time. Based on the above formulas, a bi-objective programming model to minimize the network operation cost and construction cost is proposed to decide whether to expand or add links for the car, bus, and rail network respectively. Moreover, based on the minimum cost flow algorithm and simulated annealing algorithm, we develop a hybrid heuristic algorithm to solve the proposed model, which can efficiently and effectively get the near-optimal solution. Finally, two numerical tests of a simple test network (designed in Section 2) and an actual network (an area from Xizhimen to Dongdan in Beijing, China) are implemented:

(1)

For the simple network, to test the feasibility of the developed heuristic algorithm, an exact algorithm is first used to solve the model. And the results show that the proposed algorithm is effective and feasible within the allowable error range of 1.5%.

(2)

For the actual network, 12 groups of numerical experiments are carried out to analyze the optimal schemes under different weight coefficients. The results indicate that the choice of the near-optimal scheme is affected by the weight coefficients, and the results are consistent with the actual situation, Consequently, the proposed model and developed algorithm can promote the planning of multimodal transportation systems in the actual transportation network.

In this paper, the proposed model and developed algorithm are flexible, and the objective function and constraints can be modified. In our future works, we can consider the network accessibility, environmental pollution, and other aspects, and modify the objective function and constraints correspondingly. In addition, the algorithm can be combined with other heuristic algorithms, such as tabu search algorithm, genetic algorithm, and so on, to get the near-optimal solution more quickly.

The study of multimodal transportation DNDP is conductive to guide passengers’ multimodal travel behavior and relieve congestion. The practical implications are as follows: (1) By studying the multimodal transportation DNDP, the optimal investment scheme of transportation network planning and construction can be obtained to provide comparison and reference for traffic planning departments, decision-makers, and researchers. (2) In the complicated urban transportation network formed by various modes, grasping the mutual influence between the operation of the multimodal transportation networks as a whole is helpful to improve the level of transportation management measures, and also conducive to giving full play to the advantages of various modes and coordinate the combination of various modes. These will bring great improvement to the transportation congestion, thus reducing vehicle delays and transportation costs.

Certain disadvantages of the proposed methods need to be mentioned here. In this paper, only single OD is considered, and the passenger demand is determined. In future work, we will study the multimodal DNDP of multi-OD under uncertain demand. In addition, this paper only studies five representative travel modes: car, bus, and rail transit, walking, and bike-sharing. However, they can be subdivided into many types in real life. For example, the car model includes private cars, taxis, online car-hailing, etc. And electromobile, motorcycle and so on are also the travel modes that many people choose. Therefore, we can take these into account to improve the proposed model in future work.