Ant Colony with Dynamic Local Search for the Time Scheduling of Transport Networks
Keywords:
urban transportation systems, real-time scheduling, ant colony optimizationAbstract
This article presents an ant colony optimization for the time scheduling of public transport traffic. In fact, the assistance of a decision support system becomes necessary for the real-time regulation of this transport networks since the size of the search space increases exponentially with the number of vehicles and stops. So, we propose an ant colony algorithm with dynamic local search, in the case of unpredictable disturbance. This approach consists in applying a local search window with increasing dimension according to the iterations. It treats the regulation problem as an optimization and provides the regulator with relevant decisions. A regulated timetable is proposed as solution aiming at minimizing the waiting time of passengers. We insure the three most important criteria of regulation which are the punctuality, the regularity and the correspondence.References
D. Huisman, R. Freling, and A. P. M.Wagelmans, "A dynamic approach to vehicle scheduling," Econometric Inst., Erasmus University, Rotterdam, The Netherlands, Rep. EI2001-17, 2001. begin comment
S. Maouche, H. Laichour, S. Hayat, "Amélioration de la qualité de correspondances dans les réseaux de transport", rapport final GRRT, avril 2001.
P. Borne, B. Fayech, S. Hammadi and S. Maouche, "Decision Support System for Urban transportation networks", IEEE SMC Part C: Applications and Reviews, Special Issue on Decision Technologies in honour of Prof Madan Singh, Vol.33, No.1, pp.67-77, 2003.
A. Soulhi, "Contribution de l'intelligence artificielle à l'aide à la décision dans la gestion des systèmes de transport urbain". Thèse de doctorat, université des sciences et technologies de Lille, France, 2000.
H. Laichour, " Modélisation multi-agent et aide à la décision : Application à la régulation des correspondances dans les réseaux de transport urbain". Thèse de doctorat, université des sciences et technologies de Lille, France, 2002.
B. Fayech, "Régulation des réseaux de transport multimodal : systèmes multi-agent et algorithmes évolutionnistes", Thèse de doctorat, université des sciences et technologies de Lille, France, 2003.
J. D. Moss and C. G. Johnson, "An ant colony algorithm for multiple sequence alignment in bioinformatics", In David W. Pearson, Nigel C. Steele, and Rudolf F. Albrecht, editors, Artificial Neural Networks and Genetic Algorithms, pages 182-186. Springer,April 2003. http://dx.doi.org/10.1007/978-3-7091-0646-4_33
M. Dorigo,"Optimization, Learning and Natural Algorithms". Ph.D.Thesis, Politecnico di Milano, Italy, in Italian, 1992.
M. Dorigo and L. M. Gambardella, "Ant Colonies for the Traveling Salesman Problem". BioSystems, 43:73-81. Also Tecnical Report TR/IRIDIA/1996-3, IRIDIA, Université Libre de Bruxelles, 1997.
N. Monmarché, "Algorithme de fourmis artificielles : application à la classification et à l'optimisation", Thèse à l'université de François Rabelais Tour, 2000.
C. Gagné and W. L. Price, "Optimisation par colonie de fourmis pour un problème d'ordonnancement industriel avec temps de réglages dépendants de la séquence". 3e Conférence Francophone de MOdélisation et SIMulation MOSIM01, Troyes (France), 2001.
P. Lacomme, C. Prins, A. Tanguy, "Optimisation par colonies de fourmis pour les tournées sur arcs". 4e Conférence Francophone de MOdélisation et SIMulation MOSIM03, Toulouse (France), 2003.
I. Alaya, C. Solnon and K. Ghédira, "Algorithme fourmi avec différentes stratégies phéromonales pour le sac à dos multidimensionnel", MHOSI'05, Hammamet, Tunisie, 2005.
M. Dorigo, V. Maniezzo, and A. Colorni. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics, Part B, 26(1):2941, 1996. http://dx.doi.org/10.1109/3477.484436
T. Stutzle and H. Hoos. MAX-MIN Ant system and local search for combinatorial optimization problems. In S. Vos, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, pages 137-154. Kluwer, Boston, 1998.
B. Bullnheimer, R. F. Hartl, and C. Strauss. "A new rank-based version of the ant system: a computational study". Technical Report POM-03/97, Institute of Management Science, University of Vienna, Accepted for publication in the Central European Journal for Operations Research and Economics, 1997.
P. Lacomme, C. Prins andW. Ramdane-Chérif "Competitive genetic algorithms for the Capacitated Arc Routing Problem and its extensions", in E.J.W. Boers and al. (ed.), Applications of evolutionary computing, pp. 473-483, Lecture Notes in Computer Science 2037, Springer, 2001.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
