Name
Abstract | ||
|---|---|---|
The classic vehicle routing problem (VRP) is generally concerned with the optimal design of routes by a fleet of vehicles to service a set of customers by minimizing the overall cost, usually the travel distance for the whole set of routes. Although the problem has been extensively studied in the context of operations research and optimization, there is little research on solving the VRP, where distributed vehicles need to compute their respective routes in a decentralized fashion. Our first contribution is a synchronous distributed approximation algorithm that solves the VRP. Using the duality theorem of linear programming, we show that the approximation ratio of our algorithm is O(n · (ρ)
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/n</sup>
log(n + m)), where ρ is the maximum cost of travel or service in the input VRP instance, n is the size of the graph, and m is the number of vehicles. We report results of simulations and discuss implementation of our algorithm on a real fleet of unmanned aerial systems (UASs) that carry out a set of tasks. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/IPDPS.2017.90 | 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
Keywords | Field | DocType |
Vehicle routing problem,Distributed optimization,Unmanned aerial systems (UAS) | Approximation algorithm,Graph,Mathematical optimization,Vehicle routing problem,Algorithm design,Computer science,Duality (mathematics),Optimal design,Software,Linear programming | Conference |
ISSN | ISBN | Citations |
1530-2075 | 978-1-5386-3915-3 | 0 |
PageRank | References | Authors |
0.34 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Akhil Krishnan | 1 | 0 | 0.34 |
| Mikhail Markov | 2 | 0 | 0.68 |
| Borzoo Bonakdarpour | 3 | 490 | 45.02 |