بهينه سازي مسائل حمل و نقل حوزه مديريت شهري با استفاده از مسئله جهت يابي با افق زماني وابسته
محورهای موضوعی : مدیریت شهریمهدی جعفریان 1 , عزیزاله جعفری 2 , رامین ُصادقیان 3
1 - گروه مهندسي صنايع، دانشگاه پيام نور، تهران، ايران
2 - گروه مهندسي صنايع، دانشکده فني و مهندسي، دانشگاه علم و فرهنگ، تهران، ايران
3 - گروه مهندسي صنايع، دانشگاه پيام نور، تهران، ايران
کلید واژه: مديريت شهري حمل و نقل شهري مسئله جهت يابي,
چکیده مقاله :
مدل سازي و ارائه رويکردهاي حل جهت بهينه سازي اقتصادي و زماني مسائل مختلف موجود در حوزه حمل و نقل شهري از مهمترين و پرچالش ترين مباحث موجود در فضاي برنامه ريزي و مديريت شهري است. طيف وسيعي از پژوهش هاي داخلي و خارجي، مسائلي از جمله حمل و نقل هاي عمومي و مديريت ترافيک شهري، جمع آوري و مديريت پسماند، امداد و نجات و حتي گردشگري شهري را در اين حوزه مد نظر قرار مي دهند و معتقدند ماحصل چنين پژوهش هايي کاهش چشمگير هزينه ها، افزايش سرعت و تسهيل جابجايي ها در شهر، کاهش آلودگي ها و مضرات زيست محيطي و حرکت به سمت پايدارسازي شهرها مي باشد. از اين رو مقاله حاضر حالت خاصي از مسئله کلاسيک و مشهور جهت يابي را که از قابليت تطبيق بالايي با مسائل حمل و نقل شهري برخوردار بوده و در آن افق زماني متاثر از وقايع، اتفاقات و شرايط بوجود آمده حين بازديد هر يک از رئوس مي باشد، مدل سازي نموده و با استفاده از يک الگوريتم ابتکاري مبتني بر مفاهيم حريصانه به حل آن پرداخته است. به منظور بررسي نحوه عملکرد الگوريتم، تعداد 85 مسئله تصادفي در 7 دسته توليد شده و الگوريتم پيشنهادي جهت حل اين مسائل بکار گرفته شده اند.
In urban management area, modeling and proposing new solving approaches to optimize different related transportation problems, is one of the most important and challengeable subject. In the literature, researchers have considered different problems related to public transportation and urban traffic, waste management, rescue and crisis, and even urban tourism in this context, and have discussed these works have caused decreasing costs, increasing rapidity and ease of transportation, decreasing pollution, and accelerating movement to build a sustainable city. This paper proposes, describes and models a new type of Orienteering Problem (OP) which has high level of compatibility with urban transportation problems, and in which the time horizon is not constant and changes depending on the events and conditions of visiting vertices. To solve this problem, a heuristic algorithm, based on greedy concepts is proposed and its performance has been investigated by 85 random samples.
[1] Vansteenwegen, P., W. Souffriau, and D. VanOudheusden, The orienteering problem: A survey. European Journal of Operational Research, 2011. 209(1): p. 1-10.
[2] Gunawan, A., H.C. Lau, and P. Vansteenwegen, Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 2016. 255(2): p. 315-332.
[3] Tricoire, F., et al., Heuristics for the multi-period orienteering problem with multiple time windows. Computers & Operations Research, 2010. 37(2) p. 351-367.
[4] Tsiligirides, T., Heuristic methods applied to orienteering. Journal of the Operational Research Society, 1984: p. 797-809.
[5] Golden, B.L., L. Levy, and R. Vohra, The orienteering problem. Naval research logistics, 1987. 34(3): p. 307-318.
[6] Bovet, J. The selective traveling salesman problem. in EURO VI Conference, Vienna. 1983.
[7] Fischetti, M. and P. Toth, An additive approach for the optimal solution of the prize collecting traveling salesman problem. Vehicle Routing: Methods and Studies, 1988: p. 319-343.
[8] Kataoka, S. and S. Morito, An algorithm for single constraint maximum collection problem. J. OPER. RES. SOC. JAPAN., 1988. 31(4): p. 515-530.
[9] Balas, E., The prize collecting traveling salesman problem. Networks, 1989. 19(6): p. 621-636.
[10] Hayes, M. and J. Norman, Dynamic programming in orienteering: route choice and the siting of controls. Journal of the Operational Research Society, 1984: p. 791-796.
[11] Kantor, M.G. and M.B. Rosenwein, The orienteering problem with time windows. Journal of the Operational Research Society, 1992: p. 629-635.
[12] Righini, G. and M. Salani, Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research, 2009. 36(4): p. 1191-1203.
[13] Gunawan, A., H.C. Lau, and K. Lu. An iterated local search algorithm for solving the orienteering problem with time windows. in European Conference on Evolutionary Computation in Combinatorial Optimization. 2015. Springer.
[14] Aghezzaf, B. and H. El Fahim, Iterated local search algorithm for solving the orienteering problem with soft time windows. SpringerPlus, 2016. 5(1): p. 1781.
[15] Gunawan, A., Z. Yuan, and H.C. Lau. A mathematical model and metaheuristics for time dependent orienteering problem. 2014. PATAT.
[16] Verbeeck, C., P. Vansteenwegen, and E.-H. Aghezzaf. The orienteering problem with time-dependent stochastic travel times. in Verolog 2014. 2014.
[17] Gavalas, D., et al. Efficient heuristics for the time dependent team orienteering problem with time windows. in International Conference on Applied Algorithms. 2014. Springer.
[18] Gavalas, D., et al., Heuristics for the time dependent team orienteering problem: Application to tourist route planning. Computers & Operations Research, 2015. 62: p. 36-50.
[19] Sun, P., et al., The Time-Dependent Pro_table Pickup and Delivery Traveling Salesman Problem with Time Windows. Eindhoven University of Technology, 2015.
[20] Verbeeck, C., P. Vansteenwegen, and E.-H. Aghezzaf, Solving the stochastic time-dependent orienteering problem with time windows. European Journal of Operational Research, 2016. 255(3): p. 699-718.
[21] Tricoire, F., et al. Algorithms for the multi-period orienteering problem with multiple time windows. in EU/MEeting 2008: Workshop on Metaheuristics for Logistics and Vehicle Routing, paper. 2008.
[22] Campbell, A.M., M. Gendreau, and B.W. Thomas, The orienteering problem with stochastic travel and service times. Annals of Operations Research, 2011. 186(1): p. 61-81.
[23] Varakantham, P. and A. Kumar. Optimization approaches for solving chance constrained stochastic orienteering problems. in International Conference on Algorithmic DecisionTheory. 2013. Springer.
[24] Zhang, S., J.W. Ohlmann, and B.W. Thomas, A priori orienteering with time windows and stochastic wait times at customers. European Journal of Operational Research, 2014. 239(1): p. 70-79.
[25] Zhang, S., J.W. Ohlmann, and B.W. Thomas, Dynamic orienteering on a network of queues. Transportation Science, 2018.
[26] Papapanagiotou, V., R. Montemanni, and L.M. Gambardella, Objective function evaluation methods for the orienteering problem with stochastic travel and service times. Journal of applied Operational research, 2014. 6(1): p. 16-29.
[27] Miller, C.E., A.W. Tucker, and R.A. Zemlin, Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 1960. 7(4): p. 326-329.