Paper Info
Title
Optimizing for Transfers in a Multi-vehicle Collection and Delivery Problem.
Abstract
We address the Collection and Delivery Problem (CDP) with multiple vehicles, such that each collects a set of items at different locations and delivers them to a dropoff point. The goal is to minimize either delivery time or the total distance traveled. We introduce an extension to the CDP: what if a vehicle can transfer items to another vehicle before making the final delivery? By dividing the labor among multiple vehicles, the delivery time and cost may be reduced. However, introducing transfers increases the number of feasible schedules exponentially. In this paper, we investigate this Collection and Delivery Problem with Transfers (CDP-T), discuss its theoretical underpinnings, and introduce a two-approximate polynomial time algorithm to minimize total distance travelled. Furthermore, we show that allowing transfers to take place at any location for the CDP-T results in at most a factor of two improvement. We demonstrate our approximation algorithms on large simulated problem instances. Finally, we deploy our algorithms on robots that transfer and deliver items autonomously in an office building.
Year
DOI
Venue
2012
10.1007/978-3-642-55146-8_7
Springer Tracts in Advanced Robotics
Field
DocType
Volume
Simulated annealing,Approximation algorithm,Division (mathematics),Computer science,Schedule,Robot,Time complexity,Distributed computing
Conference
104
ISSN
Citations 
PageRank 
1610-7438
4
0.47
References 
Authors
9
2
Name
Order
Citations
PageRank
Brian Coltin1738.64
Manuela Veloso28563882.50