×

A general variable neighborhood search variants for the travelling salesman problem with draft limits. (English) Zbl 1382.90096

Summary: In this paper, we present two general variable neighborhood search (GVNS) based variants for solving the traveling salesman problem with draft limits (TSPDL), a recent extension of the traveling salesman problem. TSPDL arises in the context of maritime transportation. It consists of finding optimal Hamiltonian tour for a given ship which has to visit and deliver products to a set of ports while respecting the draft limit constraints. The proposed methods combine ideas in sequential variable neighborhood descent within GVNS. They are tested on a set of benchmarks from the literature as well as on a new one generated by us. Computational experiments show remarkable efficiency and effectiveness of our new approach. Moreover, new set of benchmarks instances is generated.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

TSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Battara, M., Pessoa, A.A., Subramanian, A., Uchoa, E.: Exact algorithms for the travelling salesman problem with draft limits. Eur. J. Oper. Res. doi:10.1016/j.ejor.2013.10.042 · Zbl 1305.90342
[2] Hansen, P., Mladenović, N., Moreno-Pérez, J.A.: Variable neighbourhood search: methods and applications. 4OR 6, 319-360 (2008) · Zbl 1179.90332 · doi:10.1007/s10288-008-0089-1
[3] Hansen, P., Mladenović, N., Moreno-Pérez, J.A.: Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175, 367-407 (2010) · Zbl 1185.90211 · doi:10.1007/s10479-009-0657-6
[4] Johnson, DS; McGeoch, LA; Aarts, EHL (ed.); Lenstra, JK (ed.), The traveling salesman problem: a case study in local optimization, 215-310 (1995), New York · Zbl 0947.90612
[5] Mjirda, A., Jarboui, B., Macedo, R., Hanafi, S., Mladenović, N.: A two phase variable neighborhood search for the multi-product inventory routing problem. Comput. Oper. Res. doi:10.1016/j.cor.2013.06.006i · Zbl 1348.90035
[6] Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24, 1097-1100 (1997) · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[7] Mladenović, N., Todosijević, R., Urosević, D.: An efficient General variable neighborhood search for large TSP problem with time windows. Yugosl. J. Oper. Res. 22, 141-151 (2012) · Zbl 1299.90417
[8] Mladenović, N., Todosijević, R., Urosević, D.: Two level General variable neighborhood search for Attractive traveling salesman problem. Comput. Oper. Res. doi:10.1016/j.cor.2013.04.015 · Zbl 1348.90113
[9] Mladenović, N., Urosević, D., Hanafi, A., Ilić, A.: A General variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem. Eur. J. Oper. Res. 220, 270-285 (2012) · Zbl 1253.90200 · doi:10.1016/j.ejor.2012.01.036
[10] Mladenović, N., Urosević, N., Hanafi, S.: Variable neighborhood search for the travelling deliveryman problem. 4OR 11, 57-73 (2012) · Zbl 1268.90068 · doi:10.1007/s10288-012-0212-1
[11] Panchamgam, K., Xiong, Y., Golden, B., Dussault, B., Wasil, E.: The hierarchical traveling salesman problem. Optim. Lett. 7, 1-8 (2013) · Zbl 1280.90101 · doi:10.1007/s11590-012-0553-x
[12] Rakke, J.G., Christiansen, M., Fagerholt, K., Laporte, G.: The travelling salesman problem with draft limits. Comput. Oper. Res. 39, 2162-2167 (2012) · Zbl 1251.90333
[13] Reinelt, G.: TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3, 376-384 (1991) · Zbl 0775.90293 · doi:10.1287/ijoc.3.4.376
[14] Yadlapalli, S., Rathinam, S., Darbha, S.: 3-Approximation algorithm for a two depot, heterogeneous traveling salesman problem. Optim. Lett. 6, 141-152 (2012) · Zbl 1259.90116 · doi:10.1007/s11590-010-0256-0
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.