Computation of Lower Bounds for a Multiple Depot, Multiple Vehicle Routing Problem with Motion Constraints Conference Paper uri icon

abstract

  • In this paper, the problem of planning paths for a collection of vehicles passing through a set of targets is considered. Each vehicle starts at a specified location (called a depot) and it is required that each target be on the path of at least one vehicle. Every vehicle has a motion constraint and the path of each vehicle must satisfy that constraint. In this article, we developed a method to compute lower bounds to this path planning problem by relaxing some of the constraints and posing it as a standard multiple traveling salesmen problem. For those problem instances where the distance between every pair of targets is at least 4 units, another method is developed to compute a lower bound using the convexity property of the length of such paths. The proposed bounds are numerically corroborated. © 2013 IEEE.

author list (cited authors)

  • Manyam, S. G., Rathinam, S., & Darbha, S.

citation count

  • 5

publication date

  • December 2013

publisher