期刊
出版社
ASME
DOI: 10.1115/1.4030354
关键词
-
This paper considers the problem of planning paths for a collection of identical vehicles visiting a given set of targets, such that the total lengths of their paths are minimum. Each vehicle starts at a specified location (called a depot) and it is required that each target to be on the path of at least one vehicle. The path of every vehicle must satisfy the motion constraints of every vehicle. In this paper, we develop a method to compute lower bound to the minimum total path lengths by relaxing some of the constraints and posing it as a standard multiple traveling salesmen problem (MTSP). A lower bound is often important to ascertain suboptimality bounds for heuristics and for developing stopping criterion for algorithms computing an optimal solution. Simulation results are presented to show that the proposed method can be used to improve the lower bounds of instances with four vehicles and 40 targets by approximately 39%.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据