  We consider a multiple depot, multiple vehicle routing problem with fuel
constraints. We are given a set of targets, a set of depots and a set of
homogeneous vehicles, one for each depot. The depots are also allowed to act as
refueling stations. The vehicles are allowed to refuel at any depot, and our
objective is to determine a route for each vehicle with a minimum total cost
such that each target is visited at least once by some vehicle, and the
vehicles never run out fuel as it traverses its route. We refer this problem as
Multiple Depot, Fuel-Constrained, Multiple Vehicle Routing Problem (FCMVRP).
This paper presents four new mixed integer linear programming formulations to
compute an optimal solution for the problem. Extensive computational results
for a large set of instances are also presented.
