Skip to Main content Skip to Navigation
New interface
Journal articles

A dynamic programming operator for tour location problems applied to the covering tour problem

Abstract : This paper presents an evaluation operator for single-trip vehicle routing problems where it is not necessary to visit all the nodes. Such problems are known as Tour Location Problems. The operator, called Selector, is a dynamic programming algorithm that converts a given sequence of nodes into a feasible tour. The operator returns a subsequence of this giant tour which is optimal in terms of length. The procedure is implemented in an adaptive large neighborhood search to solve a specific tour location problem: the Covering Tour Problem. This problem consists in finding a lowest-cost Hamiltonian cycle over a subset of nodes such that nodes outside the tour are within a given distance from a visited node. The metaheuristic proposed is competitive as shown by the quality of results evaluated using the output of a state-of-the-art exact algorithm.
Complete list of metadata

https://hal.laas.fr/hal-01880031
Contributor : Sandra Ulrich Ngueveu Connect in order to contact the contributor
Submitted on : Monday, September 24, 2018 - 2:22:37 PM
Last modification on : Tuesday, October 25, 2022 - 11:58:11 AM

Identifiers

Citation

Leticia Vargas, Nicolas Jozefowiez, Sandra Ulrich Ngueveu. A dynamic programming operator for tour location problems applied to the covering tour problem. Journal of Heuristics, 2017, 23 (1), pp.53 - 80. ⟨10.1007/s10732-017-9324-2⟩. ⟨hal-01880031⟩

Share

Metrics

Record views

24