Paper Info
Title
Computation of lower bounds for a multiple depot, multiple vehicle routing problem with motion constraints.
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.
Year
DOI
Venue
2013
10.1109/CDC.2013.6760236
CDC
Keywords
Field
DocType
path planning,transportation,travelling salesman problems,motion constraints,multiple depot,multiple traveling salesmen problem,multiple vehicle routing problem,path planning problem
Motion planning,Traveling purchaser problem,Vehicle routing problem,Mathematical optimization,Convexity,Shortest path problem,Computer science,Upper and lower bounds,2-opt,Longest path problem
Conference
ISSN
Citations 
PageRank 
0743-1546
1
0.35
References 
Authors
4
3
Name
Order
Citations
PageRank
Satyanarayana G. Manyam1106.26
Sivakumar Rathinam221623.81
Swaroop Darbha318426.64