MULTI-VEHICLE ROUTE PLANNING FOR CENTRALIZED AND DECENTRALIZED SYSTEMS

Abstract

Multi-vehicle route planning is the problem of determining routes for a set of vehicles to visit a set of locations of interest. In this thesis, we describe a study of a classical multi-vehicle route planning problem which compared existing solutions methods on min-sum (minimizing total distance traveled) and min-max (minimizing maximum distance traveled) cost objectives. We then extended the work in this study by adapting approaches tested to generate robust solutions to a failure-robust multi vehicle route planning problem in which a potential vehicle failure may require modifying the solution, which could increase costs. Additionally, we considered a decentralized extension to the multi-vehicle route planning problem, also known as the decentralized task allocation problem. The results of a computational study show that our novel genetic algorithm generated better solutions than existing approaches on larger instances with high communication quality.