A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem Academic Article

abstract

• 2015, Springer-Verlag Berlin Heidelberg. Surveillance applications require a collection of heterogeneous vehicles to visit a set of targets. 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 minimal. We consider an important special case of this routing problem where the travel costs satisfy the triangle inequality and the following monotonicity property: the first vehicles cost of traveling between any two targets is at most equal to the second vehicles cost of traveling between the same targets. We present a primal-dual algorithm for this case that provides an approximation ratio of 2.

authors

• Rathinam, Sivakumar

published proceedings

• OPTIMIZATION LETTERS

author list (cited authors)

• Bae, J., & Rathinam, S.

citation count

• 6

complete list of authors

• Bae, Jungyun||Rathinam, Sivakumar

publication date

• August 2016

publisher

• Springer Nature  Publisher

published in

• Optimization Letters  Journal

keywords

• Approximation Algorithms
• Primal-dual Method
• Traveling Salesman Problem

Digital Object Identifier (DOI)

• 10.1007/s11590-015-0924-1

start page

• 1269

end page

• 1285

volume

• 10

issue

• 6

URL

• http://dx.doi.org/10.1007/s11590-015-0924-1

user-defined tag

• 7 Affordable and Clean Energy