Optimization of Correspondence Times in Bus Network Zones, Modeling and Resolution by the Multi-agent Approach

doi:10.1007/s40305-020-00307-8

Abstract

Abstract: Urban transportation, especially bus transportation, is an important sign of development in every city in the world. The average waiting time for passengers at correspondence stations of buses is one of the most important measures of effectiveness of bus transportation. To the best of our knowledge, the studies in the literature are about maximizing the number of synchronizations in those correspondence stations whose objective is to minimize the waiting time in the network. The classical definition of synchronization used in the literature related to a time window. In this work, we introduce a new definition of synchronization of two buses in network zones. Within this context, we present a mathematical formulation of the synchronization bus timetabling problem as a multi-objective program, where we use the new meaning for synchronization of two buses in the network zones. Since the problem is NP-hard, we adapt a multi-agent approach to solve it. Numerical experiments show that after adapting the multi-agent approach using our proposed definition, we obtain high-quality solutions compared to the classical definition.

Key words: Multi-objective problem, Bus transportation, Network zones, Multi-agent approach, Synchronization

CLC Number:

90B20

Elbaz Hassane, Elhilali Alaoui Ahmed. Optimization of Correspondence Times in Bus Network Zones, Modeling and Resolution by the Multi-agent Approach[J]. Journal of the Operations Research Society of China, 2020, 8(3): 415-436.

TrendMD

References

[1] Jansen, L.N., Pedersen, M.B., Nielsen, O.A.:Minimizing passenger transfer times in public transport timetables. In:7th Conference of the Hong Kong Society for Transportation Studies, pp. 229-239. Transportation in the information age, Hong Kong (2002)
[2] Guihaire, V., Hao, J.K.:Transit network design and scheduling:a global review. Transp. Res. Part A Policy Pract. 42(10), 1251-1273(2008)
[3] Daduna, J.R., Voß, S.:Practical experiences in schedule synchronization. In:Daduna, J.R., Branco, I., Paixao, J.M.P. (eds.) Computer-Aided Transit Scheduling, pp. 39-55. Springer, Berlin (1995)
[4] Ceder, A., Golany, B., Tal, O.:Creating bus timetables with maximal synchronization. Transp. Res. Part A Policy Pract. 35(10), 913-928(2001)
[5] Eranki, A.:A model to create bus timetables to attain maximum synchronization considering waiting times at transfer stops (2004)
[6] Cevallos, F., Zhao, F.:Minimizing transfer times in public transit network with genetic algorithm. Transp. Res. Rec. J. Transp. Res. Board 1971, 74-79(2006)
[7] Shrivastava, P., Dhingra, S.:Development of coordinated schedules using genetic algorithms. J. Transp. Eng. 128(1), 89-96(2002)
[8] Zhigang, L., Jinsheng, S., Haixing, W., Wei, Y.:Regional bus timetabling model with synchronization. J. Transp. Syst. Eng. Inf. Technol. 7(2), 109-112(2007)
[9] Ibarra-Rojas, O.J., Rios-Solis, Y.A.:Synchronization of bus timetabling. Transp. Res. Part B Methodol. 46(5), 599-614(2012)
[10] Fouilhoux, P., Ibarra-Rojas, O.J., Kedad-Sidhoum, S., Rios-Solis, Y.A.:Valid inequalities for the synchronization bus timetabling problem. Eur. J. Oper. Res. 251(2), 442-450(2016)
[11] Feng,X.,Zhu,X.,Qian,X.,Jie,Y.,Ma,F.,Niu,X.:Anewtransitnetworkdesignstudyinconsideration of transfer time composition. Transp. Res. Part D Transp. Environ. 66, 85-94(2019)
[12] Ibarra-Rojas, O.J., Muñoz, J.C., Giesen, R., Knapp, P.:(2019) Integrating frequency setting, timetabling, and route assignment to synchronize transit lines. J. Adv. Transp. (2019). https://doi.org/10.1155/2019/9408595
[13] Guihaire, V.:Modélisation et optimisation pour le graphicage des lignes de bus. Ph.D. Thesis, Université d'Angers (2009)
[14] TRB:Transit Capacity and Quality of Service Manual (TCRP 100), 2nd edn. Washington (2003)
[15] TRB:Traveller Response to Transportation System Changes:Transit Scheduling and Frequency (TCRP 95). Washington (2004)
[16] Pratt, R.H., Coople, J.:Traveler response to transportation system changes. Media Info, p. 408(1981)
[17] Jacques, F.:Les systèmes multi-agents, vers une intelligence collective, p. 322. InterEditions, Paris (1995)
[18] Laichour, H.:Modélisation multi-agent et aide à la décision:application à la régulation des correspondances dans les réseaux de transport urbain. Ph.D. Thesis, Lille 1(2002)
[19] Meignan, D.:Une approche organisationnelle et multi-agent pour la modélisation et l'implantation de métaheuristiques, application aux problèmes d'optimisation de réseaux de transports. Ph.D. Thesis, Université de Technologie de Belfort-Montbeliard (2008)
[20] Zgaya, H.:Conception et optimisation distribuée d'un système d'information d'aide à la mobilité urbaine:Une approche multi-agent pour la recherche et la composition des services liés au transport. Ph.D. Thesis, Ecole Centrale de Lille (2007)
[21] Özcan, E., Bilgin, B., Korkmaz, E.E.:A comprehensive analysis of hyper-heuristics. Intell. Data Anal. 12(1), 3-23(2008)
[22] Meignan, D., Créput, J.C., Koukam, A.:An organizational view of metaheuristics. In:First International Workshop on Optimisation in Multi-Agent Systems, AAMAS, vol. 8, pp. 77-85(2008)
[23] Meignan, D., Créput, J., Koukam, A.:Un framework organisationnel pour la conception et l'implantation multi-agent de métaheuristiques (2008)
[24] Meignan, D., Créput, J.C., Koukam, A.:A coalition-based metaheuristic for the vehicle routing problem.In:EvolutionaryComputation,2008.CEC:IEEEWorldCongressonComputationalIntelligence, IEEE Congress on, IEEE pp. 1176-1182(2008)
[25] Meignan, D., Koukam, A., Créput, J.C.:Coalition-based metaheuristic:a self-adaptive metaheuristic using reinforcement learning and mimetism. J. Heurist. 16(6), 859-879(2010)