A transformation for the mixed general routing problem with turn penalties
Tóm tắt
In this paper, we study a generalization of the Mixed General Routing Problem (MGRP) with turn penalties and forbidden turns. Thus, we present a unified model of this kind of extended versions for both node- and arc-routing problems with a single vehicle. We provide a polynomial transformation of this generalization into an asymmetric travelling salesman problem, which can be considered a particular case of the MGRP. We show computational results on the exact resolution on a set of 128 instances of the new problem using a recently developed code for the MGRP.
Tài liệu tham khảo
Albiach J, Sanchis JM and Soler D (2006). An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation. Eur J Opl Res, doi: 10.1016/j.ejor.2006.09.099.
Arkin EM, Bender MA, Demaine ED, Fekete SP, Mitchell JSB and Sethia S (2006). Optimal covering tours with turn costs. Siam J Comput 35: 531–566.
Bautista J and Pereira J (2004). Ant Algorithms for Urban Waste Collection Routing. Lecture Notes in Computer Science, 3172. Springer: Berlin. pp 302—309.
Benavent E and Soler D (1999). The directed rural postman problem with turn penalties. Transp Sci 33: 408–418.
Blais M and Laporte G (2003). Exact solution of the generalized routing problem through graph transformations. J Opl Res Soc 54: 906–910.
Bodin L, Fagin G, Welebny R and Greenberg J (1989). The design of a computerized sanitation vehicle routing and scheduling for the town of Oyster Bay, New York. Comput Opl Res 16: 45–54.
Carpaneto G, Dell'Amico M and Toth P (1995). Exact solution of large-scale, asymmetric traveling salesman problems. ACM Trans Math Softw 21: 394–409.
Chopra S and Rinaldi G (1996). The graphical asymmetric traveling salesman polyhedron: Symmetric inequalities. SIAM J Discrete Math 9: 602–624.
Clossey J, Laporte G and Soriano P (2001). Solving arc routing problems with turn penalties. J Opl Res Soc 52: 433–439.
Corberán A, Martí R, Martínez E and Soler D (2002). The rural postman problem on mixed graphs with turn penalties. Comput Opl Res 29: 887–903.
Corberán A, Romero A and Sanchis JM (2003). The mixed general routing polyhedron. Math Program Ser A 96: 103–137.
Corberán A, Mejía G and Sanchis JM (2005). New results on the mixed general routing problem. Opns Res 53: 363–376.
CPLEX 8.0 (2002). http://www.ilog.com/products/cplex. ILOG S.A., France.
Fischetti M and Toth P (1997). A polyhedral approach to the asymmetric traveling salesman problem. Mngt Sci 43: 1520–1536.
Kwon SH, Kim HT and Kang MK (2005). Determination of the candidate arc set for the asymmetric traveling salesman problem. Comput Opl Res 32: 1045–1057.
Lacomme P, Prins C and Ramadane-Cherif W (2004). Competitive memetic algorithms for arc routing problems. Ann Opl Res 131: 159–185.
Lacomme P, Prins C and Ramadane-Cherif W (2005). Evolutionary algorithms for periodic arc routing problems. Eur J Opl Res 165: 535–553.
Noon CE and Bean JC (1993). An efficient transformation of the generalized traveling salesman problem. INFOR 31: 39–44.
Roy S and Rousseau JM (1989). The capacitated Canadian postman problem. INFOR 27: 58–73.