A LagrangianBased Algorithm for a Multiple Depot, Multiple Travelling Salesmen Problem
Conference Paper

 Overview

 Identity

 Additional Document Info

 View All

Overview
abstract

In this manuscript, we consider the problem of motion planning of m Dubins' vehicles through n points in a plane. The initial location and heading of the vehicles is specified and is assumed to be distinct for each vehicle. A motion plan for a vehicle is given by the sequence of points and the corresponding angles at which each point must be visited by the vehicle. We require that each vehicle return to the same initial locatlon(depot) at the same heading after visiting the points. The objective of the motion planning problem is to choose at most q[≤ m) Dubins' vehicles and And their motion plans so that all the points are visited and the total cost of the tours1 of the chosen vehicles is a minimum amongst all the possible choice of vehicles and their tours. This problem is a generalization of the Multiple Depot, Multiple Travelling Salesmen Problem (MDMTSP) in two directions  the problem involves the determination of choice of vehicles and their respective headings at each of their assigned points. This problem is NPhard. We propose a two step approach to solving this problem  (1) the combinatorial problem of choosing the vehicles and their associated tours is based on Euclidean distances between points and (2) once the sequence of points to be visited, the heading at each point is determined based on a Dynamic Programming scheme. The solution to the first step is based on a generalization of HeldKarp's method for the MDMTSP. We modify the Lagrangian heuristics, in the literature, for finding a close primal solution from the HeldKarp's (dual) solution. Empirical results seem to indicate that this scheme seems to provide primal solutions which are within 5% of the optimum in the span of 25 dual iterations for instances which have about 45 cities to visit and 6 vehicles. © 2007 IEEE.
author list (cited authors)

Yadlapalli, S., Malik, W. A., Darbha, S., & Pachter, M.
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