NDLI: Lower and Upper Bounds for a Multiple Depot UAV Routing Problem

Content Provider	IEEE Xplore Digital Library
Author	Rathinam, S. Sengupta, R.
Copyright Year	2006
Description	Author affiliation: Dept. of Civil Eng., California Univ., Berkeley, CA (Rathinam, S.)
Abstract	This paper extends the well known Held-Karp'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 traveling between any two locations satisfy triangle inequality, it is shown that there exists a 2-approximation algorithm for solving the MDURP
Starting Page	5287
Ending Page	5292
File Size	186815
Page Count	6
File Format	PDF
ISBN	1424401712
DOI	10.1109/CDC.2006.377732
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-12-13
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Upper bound Unmanned aerial vehicles Routing Approximation algorithms Cost function Monitoring Resource management Traveling salesman problems Civil engineering USA Councils
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in