A dynamic programming operator for tour location problems applied to the covering tour problem
详细信息 查看全文
- 作者：Leticia Vargas ; Nicolas Jozefowiez ; Sandra Ulrich Ngueveu
- 关键词：Evaluation operator ; Dynamic programming ; Adaptive large neighborhood search ; Covering tour problem ; Tour location problems
- 刊名：Journal of Heuristics
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：23
- 期：1
- 页码：53-80
- 全文大小：
- 刊物类别：Mathematics and Statistics
- 刊物主题：Operations Research, Management Science; Operation Research/Decision Theory; Artificial Intelligence (incl. Robotics); Calculus of Variations and Optimal Control; Optimization;
- 出版者：Springer US
- ISSN：1572-9397
- 卷排序：23
文摘
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.