×

Mixed integer programming formulations for the generalized traveling salesman problem with time windows. (English) Zbl 1534.90142

Summary: The generalized traveling salesman problem with time windows (GTSPTW) is defined on a directed graph where the vertex set is partitioned into clusters. One cluster contains only the depot. Each vertex is associated with a time window, during which the visit must take place if the vertex is visited. The objective is to find a minimum cost tour starting and ending at the depot such that each cluster is visited exactly once and time constraints are respected, i.e., for each cluster, a single vertex is visited during its time window. In this paper, four mixed integer linear programming formulations for the GTSPTW are proposed and compared. They are based on different definitions of variables. All the formulations are compact, which means the number of decision variables and constraints is polynomial with respect to the size of the instance. Dominance relations between their linear relaxations are established theoretically. Computational experiments are conducted to compare the linear relaxations and branch-and-bound performances of the four formulations. The results show that two formulations are better than the other ones.

MSC:

90C27 Combinatorial optimization
90C11 Mixed integer programming
Full Text: DOI

References:

[1] Ascheuer, N.; Fischetti, M.; Grötschel, M., Solving the asymmetric travelling salesman problem with time windows by branch-and-cut, Math Program, 90, 3, 475-506 (2001) · Zbl 1039.90056 · doi:10.1007/PL00011432
[2] Baldacci, R.; Mingozzi, A.; Roberti, R., New state-space relaxations for solving the traveling salesman problem with time windows, INFORMS J Comput, 24, 3, 356-371 (2012) · Zbl 1462.90102 · doi:10.1287/ijoc.1110.0456
[3] Dash, S.; Günlük, O.; Lodi, A.; Tramontani, A., A time bucket formulation for the traveling salesman problem with time windows, INFORMS J Comput, 24, 1, 132-147 (2012) · Zbl 1462.90103 · doi:10.1287/ijoc.1100.0432
[4] Desrochers, M.; Desrosiers, J.; Solomon, M., A new optimization algorithm for the vehicle routing problem with time windows, Oper Res, 40, 2, 342-354 (1992) · Zbl 0749.90025 · doi:10.1287/opre.40.2.342
[5] Fischetti, M.; Salazar González, JJ; Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Oper Res, 45, 3, 378-394 (1997) · Zbl 0893.90164 · doi:10.1287/opre.45.3.378
[6] Hawkins AJ (2018) Amazon will now deliver packages to the trunk of your car. https://www.theverge.com/2018/4/24/17261744/amazon-package-delivery-car-trunk-gm-volvo. Accessed May 2019
[7] Israeli, E.; Wood, RK, Shortest-path network interdiction, Netw Int J, 40, 2, 97-111 (2002) · Zbl 1027.90106
[8] Kara I, Guden H, Koc ON (2012) New formulations for the generalized traveling salesman problem. In: Proceedings of the 6th international conference on applied mathematics, simulation, modelling, ASM, vol 12, pp 60-65
[9] Karapetyan D (2012) Gtsp instances library. http://www.cs.nott.ac.uk/ pszdk/gtsp.html. Accessed Aug 2018
[10] Kirsten K (2016) Volvo’s solution for the package theft epidemic: your car’s trunk. http://fortune.com/2016/05/10/volvo-urb-it-delivery/. Accessed Mar 2019
[11] Miller, CE; Tucker, AW; Zemlin, RA, Integer programming formulation of traveling salesman problems, J ACM, 7, 4, 326-329 (1960) · Zbl 0100.15101 · doi:10.1145/321043.321046
[12] Ozbaygin, G.; Karasan, OE; Savelsbergh, M.; Yaman, H., A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations, Transp Res Part B Methodol, 100, 115-137 (2017) · doi:10.1016/j.trb.2017.02.003
[13] Pop, PC, New integer programming formulations of the generalized traveling salesman problem, Am J Appl Sci, 4, 11, 932-937 (2007) · doi:10.3844/ajassp.2007.932.937
[14] Reyes, D.; Savelsbergh, M.; Toriello, A., Vehicle routing with roaming delivery locations, Transp Res Part C Emerg Technol, 80, 71-91 (2017) · doi:10.1016/j.trc.2017.04.003
[15] Yuan, Y.; Cattaruzza, D.; Ogier, M.; Semet, F., A branch-and-cut algorithm for the generalized traveling salesman problem with time windows, Eur J Oper Res, 286, 3, 849-866 (2020) · Zbl 1443.90327 · doi:10.1016/j.ejor.2020.04.024
[16] Yuan, Y.; Cattaruzza, D.; Ogier, M.; Semet, F., A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for routing problems with time windows, Oper Res Lett, 48, 2, 167-169 (2020) · Zbl 1525.90379 · doi:10.1016/j.orl.2020.01.008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.