Document Type : Research Paper
Authors
1 Assistant Professor, Industrial Engineering Department, Faculty of Engineering, Islamic Azad University, Tehran North Branch, Tehran, Iran
2 M.Sc. in Industrial Engineering, Faculty of Engineering, Islamic Azad University, Tehran North Branch, Tehran, Iran
Abstract
The development of a variety of public transportation systems that cover different areas, has made it difficult for passengers and users to choose the type of transportation system and appropriate route between two specified departures. In large cities such as Tehran, a network of public transportation systems, called multi-modal systems, are consist of stations as nodes and public transport vehicles intermediate between the two consecutive stations as arcs. Travelers are looking continuously for a way to find the optimal route in complex multi-modal transportation networks to reach their desired destination with minimal cost and confusion. In this paper, a multi-objective programming model with three objective functions has been developed for routing in multi-modal transport systems. The objectives of the proposed model are to minimize the cost, travel time and the number of vehicle types. By examining the validation of models by test issues, two exact and meta-heuristic algorithms (ant colony algorithm) have been developed to solve the proposed model. The results show that problem solving by exact method for networks with more than 15 nodes are non-operating, while the meta-heuristic algorithm provides the same problems with same precision in the exact method but with logical time.
Keywords
برادران، و.، شاه‌محمد، ح.، واقفی، پ. (1392). «ارائه مدل و نرم‌افزار مسیریابی در شهرها بر اساس معیارهای چندگانه»، سیزدهمین کنفرانس بین‌المللی مهندسی حمل‌ونقل و ترافیک، تهران، ایران.
حسنی‌نسب، س.ش.، صفارزاده، م.، ممدوحی، ا. (1390). «روشی برای مسیریابی بهینه در حمل‌ونقل همگانی یکپارچه شبکه اتوبوس و اتوبوس تندرو»، مهندسی حمل‌ونقل، سال دوم، شماره چهارم، 316-303.
کامروز خدایار، گ.، کفاش چرندایی، ن. و آل شیخ، ع.ا. (1390)، «ارزیابی و مقایسه عملکرد الگوریتم‌های بهینه‌سازی کلونی مورچه‌ها و ژنتیک در حل مسئله فروشنده دوره‌گرد»، مجموعه مقالات همایش ژئوماتیک، اردیبهشت 90، 25-27، تهران، ایران.
عینی، ا.، صالحی‌پور، ا. (1390). "ارائه یک الگوریتم برای یافتن کوتاهترین مسیر در شبکه‌های حمل و نقل"، فصلنامه علمی و پژوهشی مطالعات مدیریت صنعتی، سال هشتم، شماره 21، 180-167.
خاتمی فیروزآبادی، ع.، محبی، ح.، زارعی محمود آبادی، م. (1390). "الگوریتمی جهت حل مسئله کوتاهترین مسیر مبتنی بر قوانین دارهای الکتریکی"، فصلنامه علمی و پژوهشی مطالعات مدیریت صنعتی، سال هشتم، شماره 21، 61-39.
صالحی صدقیانی، ج. (1389). "حل مسئله فروشنده دوره‌گرد متقارن با در نظر گرفتن زمان عزیمت فازی بین شهرها توسط الگوریتم فراابتکاری مورچگان"، فصلنامه علمی و پژوهشی مطالعات مدیریت صنعتی، سال هشتم، شماره 18، 122-105.
Aneja, Y.P., Aggarwal, V. and Nair, K.P.K. (1983), “Shortest chain subject to side constraints”, Networks, Vol. 13, No. 2, pp. 295–302.
Bevrani, B., Burdett, R.L., Bhaskar, A., Yarlagadda, P. K.D.V. (2017). “A Capacity Assessment Approach for Multi-Modal Transportation Systems”, European Journal of Operational Research, Vol. 263, No. 3, pp. 864-878. doi: 10.1016/j.ejor.2017.05.007.
Bezerra, L. C. T., Goldbarg, E. F. G., Goldbarg, M. C., and Buriol, L. S. (2011), "Grace: A generational randomized aco for the multi-objective shortest path problem." In R. Takahashi, K.
Bezerra, L.C.T., Goldbarg, E.F.G., Goldbarg, M.C. and Buriol, L.S. (2013), “Analyzing the impact of MOACO components: An algorithmic study on the multi-objective shortest path problem”, Expert Systems with Applications, Vol. 40, pp. 345–355.
Breugem, T., Dollevoet, T. and van den Heuvel, W. (2017). “Analysis of FPTASes for the Multi-Objective Shortest Path Problem”, Computers and Operation Research, Vol. 78, pp. 44-56.
Chandra, S., Braughton, M., Galicia, L. D., Sanchez, A., Medina, M., Aldrete, R. (2016). “A multi-modal transportation score to evaluate infrastructure supply-demand for commuters”, International Conference on Sustainable Design, Engineering and Construction, Procedia Engineering, Vol. 145, pp. 304 – 311.
Chica, M., Cordón, O., Damas, S. and Bautista, J. (2011). "A new diversity induction mechanism for a multi-objective ant colony algorithm to solve a real-world time and space assembly line balancing problem", Memetic Computing, Vol. 3, pp.15–24.
Climaco, J.C.N., Craveirinha, J.M.F., Pascoal, M.M.B. )2003(. "A bicriterion approach for routing problems in multimedia networks", Networks, Vol. 41, No. 4, pp. 399–404.
Dib, O., Manier, M. and Caminada, A. (2015). “Memetic Algorithm for Computing Shortest Paths in Multimodal Transportation Networks”, Transportation ResearchProcedia, Vol. 10, pp. 745-755.
Dijkstra, E.W. (1959). “A note on two problems in connection with graphs”, Numerische Mathematik, Vol. 1, pp. 269–271.
Doerner, K., Hartl, R. F. and Reimann, M. (2001). “Are competants more competent for problem solving? The case of a multiple objective transportation problem”. GECCO’01. Berlin, Heidelberg: Morgan Kaufmann, p. 802.
Dorigo, M. and Stützele, T. (2004), “Ant Colony Optimization”, MIT Press, Cambridge, MA.
Dorigo, M., Maniezzo, V. and Colorni, A. (1996), "Ant system: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man and Cybernetics Part B, Vol. 26, No. 1, pp. 29–41.
Dorigo, M., Maniezzo, V. and Colorni,A. (1991), “Ant System: An Autocatalytic Optimizing Process, Technical Report”, Dipartimento di Elettronica e Informazione, Politecnico di Milano.
Du, L. and He, R. (2012). “Combining Nearest Neighbor Search with Tabu Search for Large-Scale Vehicle Routing Problem”, Physics Procedia, Vol. 25, pp. 1536-1546.
Duque, D., Lozano, L. and Medaglia, A.L. (2015), “An exact method for the biobjective shortest path problem for large-scale road networks”, European Journal of Operational Research, Vol. 242. No. 3, pp. 788–797.
Ergun, F., Sinha, R. and Zhang, L. (2002). “An improved FPTAS for restricted shortest path”, Information Processing Letters, Vol. 83, pp. 287–291.
Ghezail, F., Pierreval, H. and Hajri-Gabouj, S. (2009), “Multi Objective Optimization Using Ant Colonies Complex Systems and Self-organization Modelling”, Part of the series Understanding Complex Systems, pp. 65-70.
Ghoseiri, K. and Nadjari, B. (2010), “An ant colony optimization algorithm for the bi-objective shortest path problem”, Applied Soft Computing, Vol. 10, pp. 1237–1246.
Glover, F. and Laguna, M. (1997), “Tabu Search”, Kluwer Academic Publishers.
Goldberg, H.C. (2005). “Computing the shortest path: A* meets graph theory”, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), SIAM.
Gunichev, A., Bedathur, S., Seufert, S. and Weikum, G. (2010). “Fast and accurate estimation of shortest paths in large graphs”, in: Proc. 19th ACM International Conference on Information and Knowledge Management, Toronto, Canada, pp. 499–508.
Gutiérrez-Jarpa, G., Laporte, G., Marianov, V., Mocciad, L. (2017), “Multi-objective rapid transit network design with modal competition: The case of Concepción, Chile”, Computers & Operations Research, Vol. 78, pp. 27-43.
Hadas, Y., Nahum, O.E. (2016), “Urban bus network of priority lanes: A combined multi-objective, multi-criteria and group decision-making approach”, Transport Policy, Vol. 52, pp. 186-196.
Handler, G. and Zang, I. (1980), “A dual algorithm for the constrained shortest path problem”, Networks, Vol. 10, No. 4, pp. 293–310.
Huguet, M. and Kirchler, D. (2013), Pierre Parent, Roberto Wolfler Calv, "Efficient algorithms for the 2-Way Multi Modal Shortest Path Problem", Electronic Notes in Discrete Mathematics, Vol. 41, pp. 431-437.
Joksch, H.C. (1966), “The shortest route problem with constraints”, J. Math. Anal. Appl. Vol.14, No. 2, pp.191–197.
Ke, L., Feng, Z., Xu, Z., Shang, K., and Wang, Y. (2010). “A multiobjective ACO algorithm for rough feature selection”. In PACCS’10, pp. 207–210.
Khalili-Damghani, K. and Amiri, M. (2012). "Solving binary-state multi-objective reliability redundancy allocation series-parallel problem using efficient epsilon-constraint, multi-start partial bound enumerational gorithm,and DEA", Reliability Engineering and System Safety, Vol. 103, pp. 35–44.
Mandow, L., Perez de la Cruz, J.L. (2005). “A new approach to multi objective A* search”, in: Proc. of IJCAI’05, pp. 218–223.
Mavrotas, G. (2009). “Effective implementation of the e-constraint method in multi- objective mathematical programming problems”, Applied Mathematics and Computation, Vol. 213, pp. 55–65.
Mora, A. M., Merelo, J. J., Laredo, J. L. J., Millan, C. and Torrecillas, J. (2009). “Chac, a moaco algorithm for computation of bi-criteria military unit path in the battlefield: Presentation and first results”, International Journal of Intelligence Systems, Vol. 24, pp.818–843.
Niksirat, M., Ghatee, M. M. and Hashemi, S.M. (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, Vol. 36, pp. 5709–5726.
Patiño, M.S. and Lozanoa, A. (2014), “Shortest hyperpaths in a multimodal network for the public transportation system: Central Southern Mexico City”, Social and Behavioral Science, Vol. 160, pp. 529-538.
Pyrga, E., Schulz, F., Wagner, D. and Zaroliagis, C. (2008), “Efficient models for timetable information in public transportation systems”, ACM Journal of Experimental Algorithmics, Vol. 12, No. 2.4, pp. 1-39.
Rivera, J.C., Afsar, H.M. and Prins, C. (2016). “Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem”, Eur. J. Oper. Res., Vol. 249, No. 1, pp. 93–104.
Sheng, Y. and Gao, Y. (2016). “Shortest path problem of uncertain random network”, Computers & Industrial Engineering, Vol. 99, pp. 97–105.
Shi, N, Zhou, S., Wang, F. and Liu, L. (2017). “The multi-criteria constrained shortest path problem”, Transportation Research Part E, Vol. 101, pp. 13-29.
Siddiqi, U. F., Shiraishi, Y., Dahba, M. and Sait, S. M. (2014), “A memory efficient stochastic evolution based algorithm for the multi-objective shortest path problem”, Applied Soft Computing, Vol. 14, pp. 653–662.
Socharoentum, M. and Karimi, H. A. (2016).“Multi-modal transportation with multi-criteria walking (MMT-MCW): Personalized route recommender”, Computers, Environment and Urban Systems, Volume 55, pp. 44-54.
Stern R. (1996). “Passenger transfer system review”, Synthesis of Transit Practice 19, Transportation Research Board, National Academy Press.
Tarapata, Z. (2007). “Selected multi criteria shortest path problems: an analysis of complexity, models and adoption of standard algorithms”, Int. J. Appl. Math. Comput. Sci, Vol. 17, No. 2, pp. 269–287.
Tsaggouris, G. and Zaroliagis, C. (2009), “Multiobjective optimization: improved FPTAS for shortest paths and non-linear objectives with applications”, J. Theory Comput. Syst, Vol. 45, No. 1, pp. 162–186.
Udenta, F.C., Jha, M.K., Mishra, S. and Maji, A. (2013), “Strategies to Improve the Efficiency of a Multimodal Interdependent Transportation System in Disasters”, Social and Behavioral Sciences, Vol. 104, pp. 805 – 814.
Verma, M., Verter, V. and Zufferey, N. (2012). “A bi-objective model for planning and managing rail-truck intermodal transportation of hazardous materials”, Transp. Res. Part E, Vol. 48, No. 1, pp. 132–149.
Wang, L., Yang, L. and Gao. Z., (2016). “The constrained shortest path problem with stochastic correlated link travel times”, Eur. J. Oper. Res., Vol. 255, No. 1, pp. 43–57.
Wang, S., Meng, Q. and Sun, Z. (2013). “Container routing in liner shipping”, Transp. Res. Part E, Vol. 49, No. 1, pp. 1–7.
)