The target visitation arc routing problem
Tóm tắt
This paper studies the target visitation arc routing problem on an undirected graph. This problem combines the well-known undirected rural postman problem and the linear ordering problem. In this problem, there is a set of required edges partitioned into targets, which must be traversed and there are pairwise preferences for the order in which some targets are serviced, which generates a revenue if the preference is satisfied. The aim is to find a tour that traverses all required edges at least once, and offers a compromise between the revenue generated by the order in which targets are serviced, and the routing cost of the tour. A linear integer programming formulation including some families of valid inequalities is proposed. Despite the difficulty of the problem, the model can be used to solve to optimality around 62% of the test instances.
Tài liệu tham khảo
Alcaraz J, García-Nové EM, Landete M, Monge JF (2020) The linear ordering problem with clusters: a new partial ranking. TOP 28:646–671. https://doi.org/10.1007/s11750-020-00552-3
Aráoz J, Fernández E, Meza O (2009) Solving the prize-collecting rural postman problem. Eur J Oper Res 196(3):886–896
Arulselvan A, Commander CW, Pardalos PM (2007) A hybrid genetic algorithm for the target visitation problem. Nav Res Logist 1–20
Blázsik Z, Bartók T, Imreh B, Imreh C, Kovacs Z (2006) Heuristics on a common generalization of TSP and LOP. Pure Math Appl 17(3–4):229–239
Cabral E, Gendreau M, Ghiani G, Laporte G (2004) Solving the hierarchical Chinese postman problem as a rural postman problem. Eur J Oper Res 155(1):44–50
Christofides N, Campos V, Corberán A, Mota E (1981) An algorithm for the rural postman problem. Technical report, Imperial College Report IC.O.R.81.5
Colombi M, Corberán Á, Mansini R, Plana I, Sanchis J (2016) The hierarchical mixed rural postman problem. Transp Sci 51(2):755–770
Colombi M, Corberán Á, Mansini R, Plana I, Sanchis J (2017) The hierarchical mixed rural postman problem: polyhedral analysis and a branch-and-cut algorithm. Eur J Oper Res 257(1):1–12
Corberán Á, Laporte G (2014) Arc routing: problems, methods, and applications. MOS-SIAM series on optimization, vol 20. Philadelphia
Dror M, Stern H, Trudeau P (1987) Postman tour on a graph with precedence relation on arcs. Networks 17(3):283–294
Ghiani G, Improta G (2000) An algorithm for the hierarchical Chinese postman problem. Oper Res Lett 26(1):27–32
Grundel D, Jeffcoat D (2004) Formulation and solution of the target visitation problem. Technical report, Proceedings of the AIAA 1st Intelligent Systems Technical Conference, Chicago
Hertz A, Laporte G, Nanchen Hugo P (1999) Improvement procedures for the undirected rural postman problem. INFORMS J Comput 11:53–62
Hildenbrandt A (2018) Traveling salesman problems with additional ordering constraints. In: Kliewer N, Ehmke JF, Borndörfer R (eds) Operations research proceedings 2017. Springer International Publishing, Cham, pp 221–227
Hildenbrandt A, Reinelt G (2015) Inter programming models for the target visitation problem. Informatica 39:257–260
Hungerländer P (2015) A semidefinite optimization approach to the target visitation problem. Optim Lett 9(8):1703–1727
Korteweg P, Volgenant T (2006) On the hierarchical Chinese postman problem with linear ordered classes. Eur J Oper Res 169(1):41–52
Letchford AN, Eglese RW (1998) The rural postman problem with deadline classes. Eur J Oper Res 105(3):390–400
Li LYO, Eglese RW (1996) An interactive algorithm for vehicle routeing for winter-gritting. J Oper Res Soc 47(2):217–228
Martí R, Reinelt G (2011) In: Antman SS, Marsden JE, Sirovich L (eds) The linear ordering problem: exact and heuristic methods in combinatorial optimization, vol 175. Springer Science & Business Media, Berlin
Orloff CS (1974) A fundamental problem in vehicle routing. Networks 4(1):35–64
Panchamgam K, Xiong Y, Golden BL, Dussault B, Wasil EA (2013) The hierarchical traveling salesman problem. Optim Lett 7:1517–1524