  This paper addresses a fuel-constrained, autonomous vehicle path planning
problem in the presence of multiple refueling stations. We are given a set of
targets, a set of refueling stations, and a depot where $m$ vehicles are
stationed. The vehicles are allowed to refuel at any refueling station, and the
objective of the problem is to determine a route for each vehicle starting and
terminating at the depot, such that each target is visited by at least one
vehicle, the vehicles never run out of fuel while traversing their routes, and
the total travel cost of all the routes is a minimum. We present four new
mixed-integer linear programming formulations for the problem. These
formulations are compared both analytically and empirically, and a
branch-and-cut algorithm is developed to compute an optimal solution. Extensive
computational results on a large class of test instances that corroborate the
effectiveness of the algorithm are also presented.
