A Primal Dual Algorithm for a Heterogeneous Traveling Salesman Problem

Details A Primal Dual Algorithm for a Heterogeneous Traveling Salesman Problem A Primal Dual Algorithm for a Heterogeneous Traveling Salesman Problem

2011-11-02

arxiv.org/abs/1111.0567v1

Computer Science

Discrete Mathematics

Scientific paper

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 primal-dual algorithm for a variant of this routing problem that provides an approximation ratio of 2.

Affiliated with

Also associated with

No associations

Rating

A Primal Dual Algorithm for a Heterogeneous Traveling Salesman Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Primal Dual Algorithm for a Heterogeneous Traveling Salesman Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Primal Dual Algorithm for a Heterogeneous Traveling Salesman Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-329643