AN APPROXIMATION ALGORITHM FOR A HETEROGENEOUS TRAVELING SALESMAN PROBLEM Conference Paper uri icon

abstract

  • Surveillance applications require a collection of heterogeneous vehicles to visit a set of targets. In this article, we consider a fundamental routing problem that arises in these applications involving two vehicles. Specifically, we consider a routing problem where there are two heterogeneous vehicles that start from distinct initial locations, and a set of targets. The objective is to find a tour for each vehicle such that each of the targets is visited at least once by a vehicle and the sum of the distances traveled by the vehicles is a minimum. We present a novel primal-dual algorithm for the same that provides an approximation ratio of 2.

name of conference

  • ASME 2011 Dynamic Systems and Control Conference and Bath/ASME Symposium on Fluid Power and Motion Control, Volume 1

published proceedings

  • PROCEEDINGS OF THE ASME DYNAMIC SYSTEMS AND CONTROL CONFERENCE AND BATH/ASME SYMPOSIUM ON FLUID POWER AND MOTION CONTROL (DSCC 2011), VOL 1

author list (cited authors)

  • Bae, J., & Rathinam, S.

citation count

  • 5

complete list of authors

  • Bae, Jungyun||Rathinam, Sivakumar

publication date

  • January 2012