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


  • 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.

name of conference

  • 52nd IEEE Conference on Decision and Control

published proceedings


author list (cited authors)

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

citation count

  • 5

complete list of authors

  • Manyam, Satyanarayana G||Rathinam, Sivakumar||Darbha, Swaroop

publication date

  • December 2013