異種車両巡回問題に対する主双対アルゴリズム
A Primal Dual Algorithm for a Heterogeneous Traveling Salesman Problem
異なる初期位置から出発する2台の異種車両で全目標を訪問する経路を求め、総移動距離を最小化する問題に対し、近似比2の主双対アルゴリズムを提案した。
著者: Jungyun Bae, Sivakumar Rathinam
分類: cs.DM, cs.DS, cs.RO, math.CO
原文アブストラクト
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.
