Robust Multiple-Vehicle Route Planning

Planning problems with multiple vehicles occur in many settings, including the well-known vehicle routing problem (VRP) and drone delivery operations, including the flying sidekick problem.   Most approaches to these problems assume that the vehicles are reliable and will not fail.

In the real world, however, a vehicle could fail, in which case the other vehicles would have to change their routes to cover the locations that the failed vehicle did not visit.  In recent research done at the University of Maryland, Ruchir Patel studied this challenge and developed approaches for generating robust routes for multiple-vehicle operations.  His thesis, Multi-Vehicle Route Planning for Centralized and Decentralized Systems, describes the results of his research.  The key idea is to consider the worst-case performance of a solution instead of the best-case performance.  A solution with better worst-case performance is more robust and will perform well even if a vehicle fails.

He found that a genetic algorithm (GA) could find high quality solutions, but the computational effort was substantial because evaluating the robustness of a solution required evaluating all possible failure scenarios and generating a recovery plan for each one.  His approach used Prim's Algorithm to generate a minimum spanning tree and construct a recovery plan quickly.  Although the computational effort may be acceptable for pre-mission planning, faster approaches could be useful for real-time, online planning.