Sage Journals: Discover world-class research

Abstract

The Custom Bus has advantages on punctuality, direct arrival, and economic benefits. It has a good effect on attracting passengers from private cars commuting in city. Due to the unscientific docking stations, the Custom Bus is always ineffective. There are little studies about the optimization of docking stations. Based on the reference to minimum cost maximum flow problem, using the chain of minimum cost increase flow and the Dijkstra algorithm, choosing points by 0-1 planning model, studying the docking forms on multi-origin to multi-destination. Guaranteeing the attendance rate and limited docking stations, to achieve the goals that shortest single path and the highest service rate by arranging the docking stations reasonably. This algorithm has been demonstrated during the process of optimizing Custom Bus docking stations between Guilin’s new and old urban districts.

Keywords

Custom Bus optimization of docking stations minimum cost maximum flow chain of minimum cost increase flow Dijkstra algorithm

Introduction

Currently, the rapid growth of private car population and its usage not only lower the use efficiency of resource for public road but also reduce the trip proportion of public transportation. In order to change this situation, and solve the problem of rush hour travel, the extension and application of Custom Bus have arisen. A bus mode which through efficient transportation from point to point for traffic travelers in commuting time gradually rise.¹

The Custom Bus determines the docking site according to passenger demand and adopts reasonable wiring to improve travel efficiency. The Custom Bus can travel between residential communities and work areas of the city according to the mode of fixed-point direct, its trip cost between buses and taxis. At present, there are many cities that have begun to put it into operation such as Beijing, Qingdao, Kunming, Ningbo, and other cities; at the same time, it will be launched subsequently in other cities such as Hangzhou, Tianjin, and Guilin.²

So far, research has been carried out in this field both internally and abroad. K Xu et al.³ and others have analyzed the service elements of customized bus. Z Wang and R Wang⁴ have combined the actual research to customize the bus through the composite ecological effect evaluation. Meanwhile, M Zhang et al.⁵ use the ant colony algorithm to build a customized bus route optimization model and solve the problem. L Hu et al.⁶ used the K-means cluster analysis method and the range cover formula to determine the location and layout of the customized bus station. However, the above model and algorithm cannot solve the problem of customized bus stop optimization all round. Therefore, it is necessary to search for another solution algorithm.

The optimized selection of docking stations can maximize the efficiency of Custom Bus, which can be regarded as a way to resolve the network problems of minimum cost maximum flow. In this article, we study the stops form of multi-origin and multi-destination, which can be converted to a network problem of minimum cost maximum flow at condition of certain attendance rate and limited number of stops. The chain of minimum cost increase flow, line selection of Dijkstra algorithm, and 0-1 screening point of programming model were used to realize the goal of shortest single-line route and biggest service rate of Custom Bus.

The optimization model of Custom Bus for docking stations

The basic configuration of optimization model for docking stations

In reality, the docking stations selection of single line contains multiple origin and destinations. Therefore, the research on the subject is an optimization problem of multi-origin and multi-destination for docking stations of Custom Bus. There are many O_i community of traffic travel, i = 1, 2, …, n. The travel destination are in the traffic region of arrival D_j, i = 1, 2, …, which includes the travel distance d_ab of O_ia to O_ib, the travel distance d_cd of D_jc to D_jd, the travel distance d_ij of O_i to D_j, and travel demand q_ij.

Constraint condition

1. Restriction of docking stations.

The service object of Custom Bus is mainly the crowd that has fixed work period and certain economic strength. Thus, there are multiple terminal stations for the same route, but the dwell time for station should be rather close. In other words, terminal station should be within neighboring regions. At the same time, in order to improve service levels, the number of docking stations for Custom Bus should be in certain restrictions.

2. Seat occupancy restriction.

In order to adapt the demand of passenger flow for Custom Bus, it is equipped with a variety of fixed seating, the seating type includes Si, I = 1, 2, …, n. For the basic profit, the seat occupancy should be above R.

The optimization object

1. Minimum cost goal: the shortest route.

Custom Bus for attracting passenger flow mainly refer to the customers of travel by private car, so in the basis of controlling reasonable fares, the travel time is close to the time of car. The shortest path should be distributed for choosing docking stations.

2. The target of maximum flow: the highest rate.

The higher service rate can enable users of Custom Bus even more. The each line cultivation of passenger flow laid the foundation to expanding the network of Custom Bus later.

The docking stations of optimization model establishment

In highest service rate and user optimum conditions, considering the restriction of docking stations and attendance, mature and large the allocation of passenger flow line is first priority. The planning model of building line is as follows

min C_{i} \leq {C_{i} (j)}

(1)

\max S = \frac{\sum_{1}^{n} \sum_{1}^{m} D_{j} O_{i}}{n \cdot m}

(2)

\begin{matrix} max L = \sum_{1}^{n} (\sum_{1}^{m} q_{ij} \cdot D_{j}) \cdot O_{i} \\ {\begin{matrix} \sum_{1}^{m} d_{jC} \leq A \\ \sum_{1}^{n} O_{i} + \sum_{1}^{m} D_{j} \leq B \\ L \subseteq {R \cdot S_{i} \leq L \leq S_{i}} \\ 0 \leq O_{i} \leq 1, 0 \leq D_{j} \leq 1, as integer \\ i = 1, 2, \dots, n, j = 1, 2, \dots, m \\ B \geq 0, as integer, A \geq 0 \end{matrix} \end{matrix}

(3)

In the formula, $C_{i} (j)$ is all possible paths of satisfying the conditions from origin and deformation based on the line C_i, S is the service rate of network for Custom Bus, A is the sum limit of station spacing for the same line, and B is the number limit of stops for the same line.

The derived analysis of docking stations optimization about minimum cost maximum flow problem

Minimum cost maximum flow problem and algorithm summary

Minimum cost maximum flow problem refers to choose the path and assign the flow of path that to achieve the minimum cost of network on the premise of maximum flow.^7–13

The chain of minimum cost increase flow refers to meet the minimum cost in the network, and the chain still can increase flow. The minimum cost flow chain shows that the current network is not a minimum cost maximum flow network and still need to increase the minimum cost flow on the chain to achieve maximum flow.^14–16

Dijkstra algorithm is a kind of typical most short-circuit algorithm that uses label principle to achieve the shortest path search. The algorithm is generally used to solve the shortest path problem from a single source point to other endpoint in directed graph. Dijkstra algorithm is basically summarized as starting point as the centers extend to the outer layers, until extended to the end of the problem.^17,18

The principle of docking stations optimization

Docking stations optimization about Custom bus can be abstracted as minimum cost maximum flow problem. By the chain of minimum cost increase flow and Dijkstra algorithm to form a minimum cost maximum flow network, screening the routes is cost optimal. After then, 0-1 programming model is established on the routes, on the basis of parameters in each point, detailed screening docking stations optimization about Custom Bus.

The key idea about docking stations optimization

OD points of logarithm are simplified by the destination partition. Make the multiple destinations as a destination, while using a virtual origin to absorb all origins, so transfer model as single point network to reduce the network complexity. Divide the destinations D_j for multiple groups and ensure the distance of each destination within the acceptable range in the group meets the conditions of $\sum_{1}^{m} d_{jC} \leq A$ . The group name is D_m; the sum of the demand for its destinations from origin O_i to group D_m is q_im.

Abstract set of docking stations, calibration impedance between the docking stations. Establishing minimum cost maximum flow network model, according to the distance of origins O_i and destinations D_j group centroid, configuration origins from far and near. And follow the rule for not setting the reverse route to establish network model as shown in Figure 1.

The shortest route and highest service rate goal transfer to seek the network’s minimum cost and maximum flow. Though the chain of minimum cost increase flow and the Dijkstra algorithm to find the minimum cost,^19,20 in this condition, successive superposition flow until achieve a maximum flow $\sum_{1}^{n} q_{im}$ , that make the total transportation cost $d (C) = \sum_{(O_{n}, D_{m}) \in C} d_{in} \cdot q_{im}$ achieve minimum in flow.

Selecting docking stations in accordance with the shortest route to service passengers as much as possible. According to the chain of increasing flow, detailed layout routes, then meet the condition of the number of docking stations under B and a certain amount of attendance, for seek the optimal plan which own the highest service rate by Simplex method.

Figure 1.

The origin-destination virtual network.

Steps of algorithm

Step 0. Network model set up is shown in Figure 1. Among them, the character above the arrow of point connection and under the origin in brackets means (distance, the number of demand). The character under the initial origin O_i is (0, q_im), and the character between O_i and O_n is (d_in, 0).

Step 1. Make the initial virtual points O_0. Specify O₀ to O_i the characters of brackets as (0, q_im), then use Dijkstra algorithm to calculate the short circuit from O₀ to D_m (if there are many short circuits at the same time, then select the most short circuit with more origins) as the chain of increases flow, and along C₁ to assign the maximum flow.

Step 2. Draw the network after the assignment, at the same time, write down the path of the chain C₁ which can increase flow and record the increase flow f₁.

Step 3. Repeat Step 1 and Step 2, until the sum of demand which arrive D_m meet the $\sum_{1}^{n} v_{im} = \sum_{1}^{n} q_{im}$ , at this time, the network has reached minimum cost and maximum flow.

Step 4. According to the chain of increases flow which has been recorded, select docking stations are detailed. Due to the shortest chain of increases flow, the sum of the distances cannot exceed the limit A. The linear programming model which screens docking stations in the chain of increases flow is as follows

\begin{matrix} max L = \sum_{1}^{n} (\sum_{1}^{m} q_{ij} \cdot D_{j}) \cdot O_{i} \\ {\begin{matrix} \sum_{1}^{n} O_{i} + \sum_{1}^{m} D_{j} \leq B \\ L \subseteq {R \cdot S_{i} \leq L \leq S_{i}} \\ 0 \leq O_{i} \leq 1, 0 \leq D_{j} \leq 1, as integer \\ i = 1, 2, \dots, n, j = 1, 2, \dots, m \end{matrix} \end{matrix}

(4)

Step 5. Seek the optimal plan on the basis of Simplex method. First of all, screen the set of docking stations included in the C₁— ${O_{a} | O_{a} \subseteq O_{i}, i = 1, 2, \dots, n}$ , then output Custom Bus route a, set of docking stations— ${O_{a}}$ and number of passengers in origin O_i— $\sum_{1}^{m} q_{ij} \cdot D_{j}$ .

Step 6. The remaining docking stations in C₁ continue operate Step 5 until no docking stations are screened out.

Step 7. Repeat Step 4, Step 5, and Step 6 until check all the chain of increase flow, then output all routes and parameters of Custom Bus.

Example

Selecting the survey data of fixed tourist source demand interval new and old town of Guilin as a case study, making analysis of Custom Bus optimization of docking stations. The data of demand point distribution are shown in Figure 2 and Table 1.

Figure 2.

The schematic diagram of demand point distribution.

Table 1.

Origin-destination travel.

D_j	O_i number	Yangtang	Yangtang original and terminal stations	Chuangye Building	Jiaotong Building
D_j	O_i number	1	2	3	4
Wumei Road	5	11	18	24	34
Seven Star Park	6	7	27	20	24
Donghuan Car Yard	7	5	12	14	15
Exhibition Center	8	9	15	19	20
	q_im	32	72	77	93

Combining with the Wumei Road station D₁, Seven Star Park station D₂, Donghuan Car Yard station D₃, and Exhibition Center station D₄ as a group D_m, first calculate the group D_m and then make origin-destination relationship network diagram according to the route of actual road diagram, in which brackets is (d_ij, q_ij), as shown in Figure 3.

Figure 3.

The origin-destination relationship network diagram.

Through the chain of minimum cost increase flow, increasing flow gradually, get the chain of increase flow C₁ = O₀O₄D_m, f₁ = 93; C₂ = O₀O₂D_m, f₂ = 72; C₃ = O₀O₃O₄D_m, f₂ = 77; C₄ = O₀O₁O₂D_m, f₂ = 32. Its simplified model of minimum cost maximum flow network diagram is shown in Figure 4.

Figure 4.

The minimum cost maximum flow network diagram.

Analyzed the routes about docking stations in detail, and setting the docking stations restriction number B = 4, seat occupancy R = 0.7, vehicle types S1 = 25, S2 = 35, S3 = 50, docking stations screening model is as follows

\begin{matrix} max L = \sum_{1}^{n} (\sum_{1}^{m} q_{ij} \cdot D_{j}) \cdot O_{i} \\ {\begin{matrix} \sum_{1}^{n} O_{i} + \sum_{1}^{m} D_{j} \leq B \\ L \subseteq {R \cdot S_{i} \leq L \leq S_{i}} \\ 0 \leq O_{i} \leq 1, 0 \leq D_{j} \leq 1, as integer \\ i = 1, 2, \dots, n, j = 1, 2, \dots, m \end{matrix} \end{matrix}

(5)

Calculating this 0-1 planning model by simplex algorithm, the final output of the Custom Bus docking stations is shown in Table 2.

Table 2.

The scheme of Custom Bus docking stations.

Route	Number of get on Point	Get on point passengers	Number of get off point	Get off point passengers	Vehicle types	Every vehicle type number	Seat occupancy	Passengers kilometer	Service rate
a	4	73	5-6-7	34-24-15	S₁-S₃	1-1	0.97	1000.1	0.91
b	4	20	8	20	S₁	1	0.80	274
c	2	57	5-6-7	18-27-12	S₁-S₂	1-1	0.95	917.7
d	3	58	5-6-7	24-20-14	S₁-S₂	1-1	0.97	957
e	3	19	8	19	S₁	1	0.76	313.5
f	1	23	5-6-7	11-7-5	S₁	1	0.92	483

From Table 2, the optimal scheme is as follows: open the Line a, boarding point 4, breakout point 5-6-7; the Line b, boarding point 4, breakout point 8; the Line c, boarding point 2, breakout point 5-6-7; the Line d, boarding point 3, breakout point 5-6-7; the Line e, boarding point 3, breakout point 8; and the Line f, boarding point 1, breakout point 5-6-7.

Concluding remarks

Conclusion

In the demand of docking stations which are multi-origin and multi-destination, transforming into minimum cost maximum flow network makes the routes own the shortest running mileage and the highest service rate, so that both of them obtain optimal benefits.

Examples certified the efficiency of the improvement of the chain of minimum cost increase flow and Dijkstra algorithm for configuration of Custom Bus routes, which proved the rationality of establishing 0-1 planning model to select docking stations.

Research prospects

After the diversified Custom Bus opened, with increasing constraints and the rising model complexity, it needs to improve the algorithm for enhancing the accuracy and efficiency.

When demand changes, there is a need to research the algorithm of sensitivity analysis for adjusting routes and optimizing docking stations rapidly.

Footnotes

Handling Editor: Yongjun Shen

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by National Natural Science Foundation of China (Nos 51268006 and 51408145) and Guangxi Natural Science Foundation (No. 2014GXNSFBA118255).

References

Zhang

et al . Research of a comprehensive evaluation method for customized flexible transit system. J Highw Transp Res Dev 2015; 32: 135–140.

Cheng

Study on the line network layout of customized shuttle bus planning of the level analysis method of point, line and plane. J Dalian Jiaotong Univ 2014; 35: 23–26.

Feng

et al . Discussion on subscription bus services. Urban Traffic 2013; 11: 24–27.

Wang

Adaptive management of Beijing urban traffic: a case study of the customized transit bus service. Mod Urban Res 2015; 3: 2–8.

Zhang

Feng

et al . Custom bus routes optimization model and its algorithm. In: 9th China intelligent transportation annual meeting symposium, vol. 11, 2014, p.8. China Intelligent Transportation Association.

Wang

et al . The layout of rideshare sites of urban customized shuttle bus. J Xuzhou Inst Technol 2016; 31: 27–32.

Zhao

Bai

Song

Labeling algorithm to solve maximum network flow problem. Comput Technol Dev 2012; 22: 94–96.

She

Bi-objective optimization of network min-cost and max-flow based on genetic algorithm. J Jiangsu Univ 2011; 32: 341–345, 358.

Zhao

Tao

A new algorithm for problem of minimum cost maximum flow. Comput Technol Dev 2014; 24: 130–132.

10.

Song

Several research and analysis base on min-cost max-flow algorithm. Master’s Thesis, Nanjing University of Posts and Telecommunications, Nanjing, China, 2012.

11.

Jia

Optimization algorithms for some problems of minimum and maximum in transportation network. Master’s Thesis, Nanchang University, Nanjing, China, 2014.

12.

She

Min-cost and max-flow algorithm of network with both node and edge capacity confined. Appl Res Comput 2010; 27: 3112–3114, 3119.

13.

Kou

Cui

An algorithm for minimum cost in multicommodity flow traffic network with different conveyance costs. J Tongji Univ 2014; 42: 1196–1202, 1210.

14.

Tao

Maximum flow algorithm and applied research. Master’s Thesis, Nanjing University of Posts and Telecommunications, Nanjing, China, 2014.

15.

Ren

Han

A generalization of minimum cost flows on linear programming. Exp Sci Technol 2014; 12: 32–34.

16.

Study on calculating methods of the passenger transport capacity of urban rail transit network. Master’s Thesis, Beijing Jiaotong University, Beijing, China, 2014.

17.

Ding

Chang

The courier vehicle distribution route optimization based on Dijkstra algorithm. Value Eng 2014; 3: 15–18.

18.

Liu

Deng

On the optimal path of emergency decision information system—based on impedance function theory and Dijkstra algorithm. J Catastrophology 2014; 3: 29–30.

19.

Discussion on subscription bus model of social reform in public institution. Transp Enterp Management 2014; 7: 19–20.

20.

Lin

Custom bus service evaluation index and its model study: a case of Beijing. World Surv Res 2016; 2: 46–49.