Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
AbstractThis article addresses an important routing problem that arises in surveillance applications involving two heterogeneous vehicles. As the addressed routing problem is NPHard, 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 LinKernighan 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 820% of the optimum depending on the problem size. Copyright 2011 John Wiley & Sons, Ltd.
