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.