Premium
Approximation algorithms and heuristics for a 2‐depot, heterogeneous Hamiltonian path problem
Author(s) -
Doshi Riddhi,
Yadlapalli Sai,
Rathinam Sivakumar,
Darbha Swaroop
Publication year - 2011
Publication title -
international journal of robust and nonlinear control
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.361
H-Index - 106
eISSN - 1099-1239
pISSN - 1049-8923
DOI - 10.1002/rnc.1701
Subject(s) - heuristics , mathematical optimization , heuristic , approximation algorithm , computer science , vehicle routing problem , set (abstract data type) , path (computing) , algorithm , linear programming , routing (electronic design automation) , integer programming , mathematics , computer network , programming language
This article addresses an important routing problem that arises in surveillance applications involving two heterogeneous vehicles. As the addressed routing problem is NP‐Hard, we develop an approximation algorithm and heuristics to solve the problem. Our approach involves solving the routing problem in two main steps: Partitioning and Sequencing. Partitioning involves finding a distinct set of targets to be visited by each vehicle. Sequencing provides the order in which each vehicle must visit the subset of targets assigned to it. The problem of partitioning is tackled by solving a linear program (LP) obtained by relaxing some of the constraints of an integer programming model for the problem. We consider two LP models for partitioning. The first LP model is obtained by mainly relaxing both the integrality and degree constraints, whereas the second model relaxes mainly the integrality constraints. Once the targets are partitioned, the sequencing problem can be solved either by Hoogeveen's algorithm or by the Lin–Kernighan heuristic to yield an approximately optimal solution. Computational results show that the algorithms based on the second LP model, on an average, provided better (closer to the optimum) solutions as compared with those based on the first LP model. We also observed that for both the LP models, the average quality of solutions given by the heuristics were found to be within 4% of the optimum, whereas the average quality of solutions obtained from the approximation algorithms were within 8–20% of the optimum depending on the problem size. Copyright © 2011 John Wiley & Sons, Ltd.