Optimization Method of Customized Shuttle Bus Lines under Random Condition
<p>Schematic plot of antibody coding.</p> "> Figure 2
<p>Layout of the customized shuttle bus service demand points.</p> "> Figure 3
<p>Results of the cluster analysis.</p> "> Figure 4
<p>Schematic diagram of the customized shuttle bus routes planning.</p> ">
Abstract
:1. Introduction
2. Problem Formulation
2.1. Travel Demand Analysis
2.2. Model Establishment
2.2.1. Modeling Assumption
- Each depot will be analyzed alone. The vehicle type for one depot will be the same. The unit operation cost is fixed and proportional to the operation mileages.
- Each vehicle can only travel along one route while serving several stops. The trip volume of each OD at each stop will not exceed the vehicle capacity.
- The number of passengers getting on or off the bus at each stop is known in the decision period. Passengers without an appointment are not allowed to take the bus.
- The timetable will be observed strictly. A delay caused by emergencies such as accidents or disasters will be neglected.
- A single ticket fare will be adopted.
2.2.2. Notations
Sets | |
A | set of depots (departure point of vehicles), A = {i|i= 1, 2, …, n} |
V | set of demand points (stops), V = {v|v= 1, 2, …, m} |
B | set of vehicles, B = {b|b= 1, 2, …, k} |
S | set of the number of stops served by vehicles, S= {s|s = 1, 2, …, m} |
Parameters | |
mb | the number of stops served by vehicle b, |
Qv | the number of passengers getting on the bus at stop v |
Pv | the number of passengers getting off the bus at stop v |
ds | the number of passengers in the area served by stop s |
fs | ticket fare for one passenger served by stop s |
rb | capacity of vehicle b |
lv | distance between the depot and demand point v |
lu,v | length of the shortest route between stop u and stop v |
cb | unit operation cost of a vehicle |
fixed cost of a vehicle for one trip | |
the number of passengers in vehicle b after the sth stop served | |
the time when the vehicle b starts from the depot | |
vehicle b running time from stop u to stop v | |
bus arrival time required by stop v | |
Lb | distance between the depot and first stop served by vehicle b, |
distance between the first stop and last stop served by vehicle b, | |
The time when vehicle b reaches stop v | |
Decision variables | |
0–1 if or not the sth stop served by vehicle b is stop v |
2.2.3. Mathematical Formulation
3. Solution Algorithm
Step 1 |
Generate input and output data of the uncertain function (15) with the stochastic simulation technique. |
Step 2 |
A neural network is trained to approximate the uncertain function from the input and output data generated in Step 1. |
Step 3 |
Create the initial population and the feasibility of antibodies will be checked with the neural network. |
Step 4 |
Update antibodies by a clone operator and immune genic operator and the feasibility of child antibodies will be checked with the neural network. |
Step 5 |
Calculate all antibodies’ objective values with the neural network. |
Step 6 |
Calculate all antibodies’ affinity based on the objective values. |
Step 7 |
Select antibodies by the clone selection. |
Step 8 |
Iterate from Step 4 to 7 until the end criterion is met. |
Step 9 |
Output the optimal solutions. |
3.1. Antibody Coding
3.2. Initial Population
3.3. Clone Operator
3.4. Immune Genic Operator
4. Numerical Example
Step 1 |
Initialization. Set a large enough initial temperature T0, T = T0, and determine the number of iterations of each T (that is, the chain length L of the Metropolis) by the randomly generated initial solution S. |
Step 2 |
For the current temperature T and k = 1, 2, ..., L, repeat Step 3 ~ 6. |
Step 3 |
A new solution S’ is generated by randomly perturbing the current solution S. |
Step 4 |
The increment d of S’ is calculated as f(S’) – f(S), where f(S) is the cost function of S. |
Step 5 |
If d < 0, then accept S’ as the new current solution; otherwise, calculate the acceptance exp(−d/T) of S’, and determine whether to retain S’ by comparing the value of the random number rand generated in (0,1) interval with the acceptance; if exp(−d/T) > rand, then accept S’ as the current solution, otherwise, retain S. |
Step 6 |
The termination condition of the algorithm is usually set as: In several continuous metropolis chains, the new solution S’ cannot be accepted, or reaches the set end temperature. If the termination condition of the algorithm is satisfied, the current solution will be the output as the optimal solution. Otherwise, the attenuation function T = qT (q is the cooling rate) attenuates T and returns to Step 2. |
5. Concluding Remarks
Author Contributions
Funding
Acknowledgments
Conflicts of Interest
References
- Cao, Y.; Wang, J. The key contributing factors of customized shuttle bus in rush hour: A case study in Harbin City. Procedia Eng. 2016, 137, 478–486. [Google Scholar] [CrossRef] [Green Version]
- Lei, Y.W.; Lin, P.Q.; Yao, K.B. The network scheduling model and its solution algorithm of Internet customized shuttle bus. J. Transp. Syst. Eng. Inf. Technol. 2017, 17, 157–163. [Google Scholar]
- Cheng, L.Q. Study on the line network layout of customized shuttle bus planning of the level analysis method of point, line and plane. J. Dali. Jiaotong Univ. 2014, 35, 23–26. [Google Scholar]
- Pan, S.L.; Yu, J.; Yang, X.F.; Liu, Y.; Zou, N. Designing a flexible feeder transit system serving irregularly shaped and gated communities: Determining service area and feeder route planning. J. Urban Plan. Dev. 2014. [Google Scholar] [CrossRef]
- Pan, S.L.; Lu, X.L.; Zou, N. Route planning and coordinated scheduling model for flexible feeder transit service. J. Jilin Univ. (Eng. Technol. Ed.) 2016, 46, 1827–1835. [Google Scholar]
- Lin, B.L.; Yang, F.S.; Li, P. Designing optimal bus network for minimizing trip times of passenger flows. China J. Highw. Transp. 1999, 12, 79–83. [Google Scholar]
- Zhou, G.W.; Luo, X. Network layout optimization model of multi-modal comprehensive public transit system and simulation. Appl. Res. Comput. 2013, 30, 1035–1040. [Google Scholar]
- He, S.X.; Fan, B.Q. Optimal path searching algorithm in transit network. J. Transp. Eng. Inf. 2007, 5, 22–27. [Google Scholar]
- Mireia, R.R.; Miquel, E.; César, T. The design of interurban bus networks in city centers. Transp. Res. Part A 2012, 46, 1153–1165. [Google Scholar]
- Perugia, A.; Moccia, L.; Cordeau, J.F.; Laporte, G. Designing a home-to-work bus service in a metropolitan area. Transp. Res. Part B 2011, 45, 1710–1726. [Google Scholar] [CrossRef]
- Amiripour, S.M.M.; Ceder, A.; Mohaymany, A.S. Designing large-scale bus network with seasonal variations of demand. Transp. Res. Part C 2014, 48, 322–338. [Google Scholar] [CrossRef]
- Leksakul, K.; Smutkupt, U.; Jintawiwat, R.; Phongmoob, S. Heuristic approach for solving employee bus routes in a large-scale industrial factory. Adv. Eng. Inform. 2017, 32, 176–187. [Google Scholar] [CrossRef]
- Ouyang, A.F.; Nourbakhsh, M.S.; Cassidy, J.M. Continuum approximation approach to bus network design under spatially heterogeneous demand. Transp. Res. Part B 2014, 68, 333–344. [Google Scholar] [CrossRef]
- Chang, Y.L.; Hu, Q.Z. Optimal line model on urban public traffic line network. China J. Highw. Transp. 2005, 18, 95–98. [Google Scholar]
- Tom, V.M.; Mohan, S. Transit route network design using frequency coded genetic algorithm. J. Transp. Eng. 2003, 129, 186–195. [Google Scholar] [CrossRef]
- Wei, F.; Machemehl, B.R. Using a simulated annealing algorithm to solve the transit route network design problem. J. Transp. Eng. 2006, 132, 122–132. [Google Scholar]
- Wei, F.; Machemehl, R.B. Bi-level optimization model for public transportation network redesign problem. Transp. Res. Rec. J. Transp. Res. Board 2012, 2263, 151–162. [Google Scholar]
- Xu, G.M.; Shi, F.; Luo, X.; Qin, J. Method of public transit network planning based on strategy equilibrium transit assignment. J. Transp. Syst. Eng. Inf. Technol. 2015, 15, 140–145. [Google Scholar]
- Yu, L.J.; Liang, M.P. Urban routine bus transit network optimizing design based on integer nonlinear programming model. China J. Highw. Transp. 2016, 29, 108–115. [Google Scholar]
- Hu, Q.Z.; Deng, W.; Tian, X.X. Optimization model of public traffic network and ant algorithm with four dimensions consumption. J. Southeast Univ. (Nat. Sci. Ed.) 2008, 38, 304–308. [Google Scholar]
- Yu, B.; Yang, Z.Z.; Jin, P.H.; Wu, S.H.; Yao, B.Z. Transit route network design-maximizing direct and transfer demand density. Transp. Res. Part C 2012, 22, 58–75. [Google Scholar] [CrossRef]
- Zhao, F.; Zeng, X.G. Optimization of user and operator cost for large-scale transit network. J. Transp. Eng. 2007, 133, 240–251. [Google Scholar] [CrossRef]
- Szeto, Y.W.; Jiang, Y. Transit route and frequency design: Bi-level modeling and hybrid artificial bee colony algorithm approach. Transp. Res. Part B 2014, 67, 235–263. [Google Scholar] [CrossRef] [Green Version]
- Wang, Q.; Wang, C.; Feng, Z.Y.; Ye, J.F. Review of K-means clustering algorithm. Electron. Des. Eng. 2012, 20, 21–24. [Google Scholar]
- Liu, B.D.; Zhao, R.Q.; Wang, G. Uncertain Programming with Applications, 3rd ed.; Tsinghua University Press: Beijing, China, 2003; pp. 54–96. [Google Scholar]
- Li, L.; Li, H.Q.; Xie, S.L.; Li, X.Y. Immune particle swarm optimization algorithms based on clone selection. Comput. Sci. 2008, 35, 253–278. [Google Scholar]
Stop | v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 | v9 | v10 | v11 | v12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
Distance | 4 | 1 | 1.5 | 6.5 | 11.5 | 14.5 | 17.5 | 5.5 | 8.5 | 10.5 | 5 | 4 |
v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 | v9 | v10 | v11 | v12 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
v1 | 0 | 4 | 1 | 6 | 11 | 15 | 18 | 5 | 8 | 10 | 4 | 6 |
v2 | 4 | 0 | 5 | 2 | 7 | 10 | 13 | 9 | 12 | 14 | 4 | 3 |
v3 | 1 | 5 | 0 | 7 | 12 | 15 | 18 | 4 | 7 | 9 | 5 | 7 |
v4 | 6 | 2 | 7 | 0 | 5 | 8 | 11 | 11 | 14 | 16 | 6 | 5 |
v5 | 11 | 7 | 12 | 5 | 0 | 3 | 6 | 16 | 19 | 21 | 11 | 10 |
v6 | 15 | 10 | 15 | 8 | 3 | 0 | 3 | 19 | 22 | 24 | 14 | 13 |
v7 | 18 | 13 | 18 | 11 | 6 | 3 | 0 | 22 | 25 | 27 | 17 | 16 |
v8 | 5 | 9 | 4 | 11 | 16 | 19 | 22 | 0 | 3 | 5 | 9 | 11 |
v9 | 8 | 12 | 7 | 14 | 19 | 22 | 25 | 3 | 0 | 2 | 12 | 14 |
v10 | 10 | 14 | 9 | 16 | 21 | 24 | 27 | 5 | 2 | 0 | 14 | 16 |
v11 | 4 | 4 | 5 | 6 | 11 | 14 | 17 | 9 | 12 | 14 | 0 | 3 |
v12 | 6 | 6 | 7 | 5 | 10 | 13 | 16 | 11 | 14 | 16 | 3 | 0 |
Stop | Arrival Time | Waiting Time (min) | Stop | Arrival Time | Waiting Time (min) |
---|---|---|---|---|---|
v1 | 8:00 | 2 | v7 | 8:50 | 2 |
v2 | 8:10 | 2 | v8 | 8:20 | 2 |
v3 | 8:05 | 2 | v9 | 8:30 | 2 |
v4 | 8:15 | 3 | v10 | 8:35 | 1 |
v5 | 8:30 | 2 | v11 | 8:05 | 2 |
v6 | 8:40 | 2 | v12 | 8:10 | 2 |
Travel Demand/Trip | Operation Time/s | Number of Vehicles | Service Rate/% |
---|---|---|---|
200 | 1.5 | 4 | 85 |
500 | 1.7 | 10 | 88 |
1000 | 2.2 | 22 | 90 |
Solution Method | Travel Demand/Trip | ||
---|---|---|---|
200 | 500 | 1000 | |
Hybrid intelligent optimization algorithm | 1.5 | 1.7 | 2.2 |
Simulated annealing algorithm | 5 | 11 | 21 |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Sun, Z.; Zhou, K.; Yang, X.; Peng, X.; Song, R. Optimization Method of Customized Shuttle Bus Lines under Random Condition. Algorithms 2021, 14, 52. https://doi.org/10.3390/a14020052
Sun Z, Zhou K, Yang X, Peng X, Song R. Optimization Method of Customized Shuttle Bus Lines under Random Condition. Algorithms. 2021; 14(2):52. https://doi.org/10.3390/a14020052
Chicago/Turabian StyleSun, Zhichao, Kang Zhou, Xinzheng Yang, Xiao Peng, and Rui Song. 2021. "Optimization Method of Customized Shuttle Bus Lines under Random Condition" Algorithms 14, no. 2: 52. https://doi.org/10.3390/a14020052