Passenger’s routes planning in stochastic common-lines’ multi-modal transportation network through integrating Genetic Algorithm and Monte Carlo simulation

Yong Peng; Zhiyao Mo; Song Liu

doi:10.5604/01.3001.0015.0123

Authors

Yong Peng School of Transportation, Chongqing Jiaotong University, Chongqing Author https://orcid.org/0000-0002-2253-3524
Zhiyao Mo School of Transportation, Chongqing Jiaotong University, Chongqing Author https://orcid.org/0000-0001-6998-8174
Song Liu chool of Transportation, Chongqing Jiaotong University, Chongqing Author https://orcid.org/0000-0001-9589-0496

DOI:

https://doi.org/10.5604/01.3001.0015.0123

Keywords:

stochastic networks, multimodal transportation, passengers’ route, genetic algorithm, Monte Carlo simulation

Abstract

In the urban transportation network, most passengers choose public transportation to travel. However, bad weather, accidents, traffic jams and other factors lead to uncertainty in transportation network. Besides, transport vehicles running on the same segments of routes and belonging to different modes or routes make the transportation network more complicated. In order to improve the efficiency of passenger’s travel, this paper aim to introducing an approach for optimizing passenger travel routes. This approach takes the travel cost and the number of transfers as constraints to finding the shortest total travel duration of passenger in urban transportation network. The running duration and dwell duration of the vehicles in the network are uncertain, and the vehicles are running according to the timetables. As transportation modes, bus, rail transit and walk are considered. In terms of methodological contribution, this paper combines Genetic Algorithm (GA) and Monte Carlo simulation to deal with optimization problem under stochastic conditions. This paper uses Monte Carlo simulation to simulate the running duration and dwell time of vehicles in different scenarios to deal with the uncertainty of the network. The shortest path of passenger’s travel is solved by GA. Two kinds of population management strategies including single population management strategy and multiple population management strategy are designed to guide the solution population evolving process. The two kinds of population management strategies of GA are tested in numerical example. The satisfactory convergence performance and efficiency of the model and algorithm is verified by the numerical example. The numerical example also demonstrated that the multiple population management strategy of GA can get better results in a shorter CPU time. At the same time, the influences of some significant variables on solution are performed. This paper is able to provide a scientific quantitative support to the path scheme selection under the influence of common-lines and timetables of different modes of transportation in stochastic urban multimodal transportation network.

References

Abbaspour, R. A., & Samadzadegan, F. (2010). An evolutionary solution for multimodal shortest path problem in metropolises. Computer Science and Information Systems. https://doi.org/10.2298/CSIS090710024A.

Artigues, C., Huguet, M. J., Gueye, F., Schettini, F., & Dezou, L. (2013). State-based accelerations and bidirectional search for biobjective multi-modal shortest paths. Transportation Research Part C: Emerging Technologies. https://doi.org/10.1016/j.trc.2012.08.003.

Bagheri, M., Ghafourian, H., Kashefiolasl, M., Pour, M. T. S., & Rabbani, M. (2020). Travel management optimization based on air pollution condition using Markov decision process and genetic algorithm (case study: Shiraz city). Archives of Transport, 53(1), 89-102. https://doi.org/10.5604/01.3001.0014.1746.

Botea, A., Kishimoto, A., Nikolova, E., Braghin, S., Berlingerio, M., & Daly, E. (2019). Computing Multi-Modal Journey Plans under Uncertainty. Journal of Artificial Intelligence Research. https://doi.org/10.1613/jair.1.11422 .

Chen, L., Gendreau, M., Hà, M. H., & Langevin, A. (2016). A robust optimization approach for the road network daily maintenance routing problem with uncertain service time. Transportation Research Part E: Logistics and Transportation Review. https://doi.org/10.1016/j.tre.2015.11.006.

Cheng, P., Xu, C., Lebreton, P., Yang, Z., & Chen, J. (2019). TERP: Time-event-dependent route planning in stochastic multimodal transportation networks with bike sharing system. IEEE Internet of Things Journal. https://doi.org/10.1109/JIOT.2019.2894511.

Chriqui, C., & Robillard, P. (1975). COMMON BUS LINES. Transportation Science. https://doi.org/10.1287/trsc.9.2.115.

Dalkiliç, F., Doǧan, Y., Birant, D., Kut, R. A., & Yilmaz, R. (2017). A Gradual Approach for Multimodel Journey Planning: A Case Study in Izmir, Turkey. Journal of Advanced Transportation. https://doi.org/10.1155/2017/5656323.

Dib, O., Moalic, L., Manier, M. A., & Caminada, A. (2017). An advanced GA-VNS combination for multicriteria route planning in public transit networks. Expert Systems with Applications. https://doi.org/10.1016/j.eswa.2016.12.009

Dib, Omar, Caminada, A., Manier, M. A., & Moalic, L. (2018). Computing multicriteria shortest paths in stochastic multimodal networks using a memetic algorithm. Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI. https://doi.org/10.1109/ICTAI.2017.00177

Dotoli, M., Zgaya, H., Russo, C., & Hammadi, S. (2017). A Multi-Agent Advanced Traveler Information System for Optimal Trip Planning in a Co-Modal Framework. IEEE Transactions on Intelligent Transportation Systems. https://doi.org/10.1109/TITS.2016.2645278.

Faroqi, H., & Mesgari, M. S. (2016). Performance Comparison between the Multi-Colony and Multi-Pheromone ACO Algorithms for Solving the Multi-objective Routing Problem in a Public Transportation Network. Journal of Navigation. https://doi.org/10.1017/S0373463315000594.

Ghavami, S. M. (2019). A web service based advanced traveller information system for itinerary planning in an uncertain multimodal network. Geocarto International. https://doi.org/10.1080/10106049.2019.1583773.

Goerigk, M., & Schmidt, M. (2017). Line planning with user-optimal route choice. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2016.10.034

Guimarans, D., Dominguez, O., Panadero, J., & Juan, A. A. (2018). A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times. Simulation Modelling Practice and Theory. https://doi.org/10.1016/j.simpat.2018.09.004

Janssen, H. (2013). Monte-Carlo based uncertainty analysis: Sampling efficiency and sampling convergence. Reliability Engineering and System Safety. https://doi.org/10.1016/j.ress.2012.08.003

Ji, Z., Kim, Y. S., & Chen, A. (2011). Multi-objective α-reliable path finding in stochastic networks with correlated link costs: A simulation-based multi-objective genetic algorithm approach (SMOGA). Expert Systems with Applications. https://doi.org/10.1016/j.eswa.2010.07.064

Jin, F., Yao, E., Zhang, Y., & Liu, S. (2017). Metro passengers’ route choice model and its application considering perceived transfer threshold. PLoS ONE, 12(9), 1–17. https://doi.org/10.1371/journal.pone.0185349

Juan, A. A., Rabe, M., Faulin, J., & Grasman, S. E. (2015). Guest editorial. Journal of Simulation, 9(4), 261–262. https://doi.org/10.1057/jos.2015.18.

Juan, Angel A., Faulin, J., Ruiz, R., Barrios, B., & Caballé, S. (2010). The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem. Applied Soft Computing Journal. https://doi.org/10.1016/j.asoc.2009.07.003

Kang, Y., & Youm, S. (2017). Multimedia application to an extended public transportation network in South Korea: optimal path search in a multimodal transit network. Multimedia Tools and Applications. https://doi.org/10.1007/s11042-016-4015-9.

Liu, L., Mu, H., & Yang, J. (2017). Toward algorithms for multi-modal shortest path problem and their extension in urban transit network. Journal of Intelligent Manufacturing https://doi.org/10.1007/s10845-014-1018-0.

López, D., & Lozano, A. (2019). Shortest hyperpaths in a multimodal hypergraph with real-time information on some transit lines. Transportation Research Part A: Policy and Practice. https://doi.org/10.1016/j.tra.2019.09.020.

Luan, S., Chen, X., Su, Y., Dong, Z., & Ma, X. (2019). Modeling travel time volatility using copula-based Monte Carlo simulation method for probabilistic traffic prediction. Transportmetrica A: Transport Science. https://doi.org/10.1080/23249935.2019.1692959.

Narayan, J., Cats, O., van Oort, N., & Hoogendoorn, S. (2020). Integrated route choice and assignment model for fixed and flexible public transport systems. Transportation Research Part C: Emerging Technologies. https://doi.org/10.1016/j.trc.2020.102631.

Nassir, N., Hickman, M., & Ma, Z. L. (2019). A strategy-based recursive path choice model for public transit smart card data. Transportation Research Part B: Methodological. https://doi.org/10.1016/j.trb.2018.01.002.

Nguyen, S., Pallottino, S., & Gendreau, M. (1998). Implicit enumeration of hyperpaths in a logit model for transit networks. Transportation Science. https://doi.org/10.1287/trsc.32.1.54.

Niksirat, M., Ghatee, M., & Mehdi Hashemi, S. (2012). Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms. Applied Mathematical Modelling. https://doi.org/10.1016/j.apm.2012.01.007

Pi, X., Ma, W., & Qian, Z. (Sean). (2019). A general formulation for multi-modal dynamic traffic assignment considering multi-class vehicles, public transit and parking. Transportation Research Part C: Emerging Technologies. https://doi.org/10.1016/j.trc.2019.05.011.

Xiao, Q., & He, R. C. (2017). Carpooling scheme selection for taxi carpooling passengers: A multi-objective model and optimisation algorithm. Archives of Transport, 42(2), 85-92. https://doi.org/10.5604/01.3001.0010.0530.

Yeh, W. C., Lin, Y. C., Chung, Y. Y., & Chih, M. (2010). A particle swarm optimization approach based on monte carlo simulation for solving the complex network reliability problem. IEEE Transactions on Reliability. https://doi.org/10.1109/TR.2009.2035796.

Zhang, S., Xu, J., Lee, L. H., Chew, E. P., Wong, W. P., & Chen, C. H. (2017). Optimal Computing Budget Allocation for Particle Swarm Optimization in Stochastic Optimization. IEEE Transactions on Evolutionary Computation. https://doi.org/10.1109/TEVC.2016.2592185.

Zhang, T., Dong, S., Zeng, Z., & Li, J. (2018). Quantifying multi-modal public transit accessibility for large metropolitan areas: a time-dependent reliability modeling approach. International Journal of Geographical Information Science. https://doi.org/10.1080/13658816.2018.1459113.

Zhang, Y., & Tang, J. (2018). Itinerary planning with time budget for risk-averse travelers. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2017.11.023.

Zhu, W., Fan, W. li, Wahaballa, A. M., & Wei, J. (2019). Calibrating travel time thresholds with cluster analysis and AFC data for passenger reasonable route generation on an urban rail transit network. Transportation, 0123456789. https://doi.org/10.1007/s11116-019-10040-8.

Zockaie, A., Nie, Y. M., & Mahmassani, H. S. (2014). Simulation-based method for finding minimum travel time budget paths in stochastic networks with correlated link times. In Transportation Research Record. https://doi.org/10.3141/2467-15.

Zockaie, A., Nie, Y., Wu, X., & Mahmassani, H. (2013). Impacts of correlations on reliable shortest path finding. Transportation Research Record. https://doi.org/10.3141/2334-01.