NDLI: Approximation algorithms for a heterogeneous Multiple Depot Hamiltonian Path Problem

Content Provider	IEEE Xplore Digital Library
Author	Yadlapalli, S. Jungyun Bae Rathinam, S. Darbha, S.
Copyright Year	2011
Description	Author affiliation: Dept. of Mech. Eng., Texas A&M Univ., College Station, TX, USA (Yadlapalli, S.; Jungyun Bae; Rathinam, S.; Darbha, S.)
Abstract	In this article, we present the first approximation algorithm for a routing problem that is frequently encountered in the motion planning of Unmanned Vehicles (UVs). The considered problem is a variant of a Multiple Depot-Terminal Hamiltonian Path Problem and is stated as follows: There is a collection of m UVs equipped with different sensors on-board and there are n targets to be visited by them collectively. There are restrictions on the targets of the following type: (1) A target may be visited by any UV, (2) a target must be visited only by a subset of UVs (with appropriate on-board sensor) and (3) a target may not be visited by a subset of UVs (as the set of on board sensors on the UV may not be suitable for viewing the targets). The UVs are otherwise identical from the viewpoint of dynamic constraints on their motion and hence, the cost of traveling from a target A to a target B is the same for all vehicles. We will assume that triangle inequality is satisfied by the cost associated with travel, i.e., it is cheaper to travel from a target A to a target B directly than to go via an intermediate target C. The UVs may possibly start from different locations (referred to as depots) and are not required to return to the depot. While there are different objectives that can be considered for this problem, we consider the total cost of travel of all the UVs as an objective to be minimized. The problem considered in this article is a generalized version of single depot-terminal Hamiltonian Path Problem and is NP-hard.
Sponsorship	Control Syst. Soc.
Starting Page	2789
Ending Page	2794
File Size	153495
Page Count	6
File Format	PDF
ISBN	9781457700804
ISSN	07431619
e-ISBN	9781457700811
DOI	10.1109/ACC.2011.5991534
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-06-29
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	American Automatic Control Council(AACC)
Subject Keyword	Approximation algorithms Vehicles Approximation methods Partitioning algorithms Vegetation Optimized production technology Sensors
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering

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

2−approximation algorithm for a generalized, multiple depot hamiltonian path problem (2007).

A transformation for a Multiple Depot, Multiple Traveling Salesman Problem

An approximation algorithm for a 2-Depot, heterogeneous vehicle routing problem

Pan and scan: Configuring cameras for coverage

Ant Colony optimization technique to Solve the min-max multi depot vehicle routing problem

How to split a flow?

An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem

3/2-Approximation Algorithm for a Generalized, Multiple Depot, Hamiltonian Path Problem

A Lagrangian-Based Algorithm for a Multiple Depot, Multiple Travelling Salesmen Problem

Approximation algorithms for a heterogeneous Multiple Depot Hamiltonian Path Problem

Similar Documents

2−approximation algorithm for a generalized, multiple depot hamiltonian path problem (2007).

A transformation for a Multiple Depot, Multiple Traveling Salesman Problem

An approximation algorithm for a 2-Depot, heterogeneous vehicle routing problem

Pan and scan: Configuring cameras for coverage

Ant Colony optimization technique to Solve the min-max multi depot vehicle routing problem

How to split a flow?

An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem

3/2-Approximation Algorithm for a Generalized, Multiple Depot, Hamiltonian Path Problem

A Lagrangian-Based Algorithm for a Multiple Depot, Multiple Travelling Salesmen Problem

Approximation algorithms for a heterogeneous Multiple Depot Hamiltonian Path Problem