×

zbMATH — the first resource for mathematics

A variable neighborhood search for solving the multi-vehicle covering tour problem. (English) Zbl 1362.90090
Jarboui, Bassem (ed.) et al., Selected short papers of the 3rd international conference on variable neighborhood search (VNS’14), Djerba, Tunisia, October 8–11, 2014. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 47, 285-292, electronic only (2015).
Summary: In this article, we consider a transportation problem with different kinds of locations: \(V\), \(T\), and \(W\). The set \(T \subset V\) consists of vertices that must be visited through the use of potential locations in \(V\) and \(W\) consists of locations that must be covered. The problem consists in minimizing vehicle routes on a subset of \(V\) including \(T\). We develop a variable neighborhood search heuristic based on a variable neighborhood descent in which a set of locations must be visited, whereas another subset must be close enough to the planned routes. We tested and compared our algorithm on datasets based on TSP Library instances.
For the entire collection see [Zbl 1310.68013].

MSC:
90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
VRP
PDF BibTeX Cite
Full Text: DOI
References:
[1] Current, J. R., Multiobjective design of transportation networks, (1981), Department of Geography and Environmental Engineering, The Johns Hopkins University, Ph.D. thesis
[2] Current, J. R.; Schilling, D. A., The covering salesman problem, Transportation Science, 23, 208-213, (1989) · Zbl 0682.90092
[3] Gendreau, M.; Laporte, G.; Semet, F., The covering tour problem, Operations Research, 45, 568-576, (1997) · Zbl 0887.90122
[4] Hà, H.; Hoàng, M.; Bostel, N.; Langevin, A.; M Rousseau, L., An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices, European Journal of Operational Research, 226, 211-220, (2013) · Zbl 1292.90050
[5] Hachicha, M.; Hodgson, M.; Laporte, G.; Semet, F., Heuristics for the multi-vehicle covering tour problem, Computers & Operations Research, 27, 29-42, (2000) · Zbl 0973.90019
[6] Hansen, P.; Mladenović, N.; Pérez, J. A.M., Variable neighborhood search: methods and applications, Annals of Operations Research, 175, 367-407, (2010) · Zbl 1185.90211
[7] Jozefowiez, N., A column generation approach for the muti-vehicle covering tour problem, (Proc. of Recherche Opérationnelle et Aide à la Décision Française (ROADEF 2011), Saint-Etienne, France, (2011))
[8] Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms, European Journal of Operational Research, 59, 345-358, (1992) · Zbl 0761.90034
[9] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers and Operations Research, 24, 1097-1100, (1997) · Zbl 0889.90119
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.