Lower and Upper Bounds for a Multiple Depot UAV Routing Problem
Conference Paper

 Overview

 Identity

 Additional Document Info

 View All

Overview
abstract

This paper extends the well known HeldKarp's lower bound available for a single Travelling Salesman Problem to the following Multiple Depot UAV Routing Problem (MDURP): Given a collection of UAVs that start at different depots, a set of terminals and destinations, the problem is to choose paths for each of the UAVs so that (1) each UAV starts at its respective depot, visits atleast one destination and reaches any one of the terminals not visited by other UAVs, (2) each destination is visited by exactly one UAV and (3) the cost of the paths is a minimum among all possible paths for the UAVs. The criteria for the cost of paths considered is the total cost of the edges travelled by the entire collection. This MDURP is formulated as a minimum cost constrained forest problem subject to side constraints. By dualizing the side constraints, one can obtain an infinite family of lower bounds for MDURP. Each lower bound can be computed in a tractable way using a matroid intersection algorithm. Also, when the costs of travelling between any two locations satisfy triangle inequality, it is shown that there exists a 2approximation algorithm for solving the MDURP. ©2006 IEEE.
author list (cited authors)

Rathinam, S., & Sengupta, R.
citation count
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
International Standard Book Number (ISBN) 10
International Standard Book Number (ISBN) 13
Additional Document Info