A vehicle routing problem with movement synchronization of drones, sidewalk robots, or foot-walkers

摘要

The vehicle routing problem (VRP) and its variants have many city logistics applications, such as goods delivery. The VRP extension with movement synchronization (VRPMS) has potential applications of drone and robot technologies to assist with the delivery of parcels. VRPMS seeks the optimal route for a set of composite resources, e.g. delivery van with drones, or delivery van with sidewalk robots. This paper proposes an exact formulation of the problem, and a metaheuristic approach to solve larger instances of the VRPMS in order to assess the economic benefits of the different technologies. It is shown that with the current physical constraints of drone technology, assisted delivery with drones has some challenges because of its capacity. Sidewalk robots and walkers, however, do contribute a cost savings compared to truck deliveries. As the technology matures, the presented metaheuristic approach can be used to evaluate improved economic benefits and cost benefit ratios.