Approximation Algorithm for a Heterogeneous Vehicle Routing Problem Academic Article uri icon


  • © 2015 Author(s). This article addresses a fundamental path planning problem which aims to route a collection of heterogeneous vehicles such that each target location is visited by some vehicle and the sum of the travel costs of the vehicles is minimal. Vehicles are heterogeneous as the cost of traveling between any two locations depends on the type of the vehicle. Algorithms are developed for this path planning problem with bounds on the quality of the solutions produced by the algorithms. Computational results show that high quality solutions can be obtained for the path planning problem involving four vehicles and 40 targets using the proposed approach.

author list (cited authors)

  • Bae, J., & Rathinam, S.

citation count

  • 4

publication date

  • January 2015