Analysis of Mixed-Integer Linear Programming Formulations for a Fuel-Constrained Multiple Vehicle Routing Problem Academic Article uri icon

abstract

  • This paper addresses a fuel-constrained, multiple vehicle routing problem (FCMVRP) in the presence of multiple refueling stations. We are given a set of targets, a set of refueling stations, and a depot where [Formula: see text] 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 (MILP) 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.

published proceedings

  • UNMANNED SYSTEMS

altmetric score

  • 2

author list (cited authors)

  • Sundar, K., Venkatachalam, S., & Rathinam, S.

citation count

  • 19

complete list of authors

  • Sundar, Kaarthik||Venkatachalam, Saravanan||Rathinam, Sivakumar

publication date

  • October 2017