Optimizing Transportation Problems in Urban Management Area Using Orienteering Problem with Dependent Time Horizon
Subject Areas :Mehdi Jafarian 1 , Azizolah Jafari 2 , Ramin Sadeghian 3
1 -
2 - University of Science & Culture
3 -
Keywords: Urban Management Transportation Problems Orienteering Problem,
Abstract :
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.