Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem

作者：Doshi Riddhi; Yadlapalli Sai; Rathinam Sivakumar; Darbha Swaroop^*

来源：International Journal of Robust and Nonlinear Control, 2011, 21(12): 1434-1451.

DOI：10.1002/rnc.1701

• approximation algorithms
• heuristics
• Hamiltonian path
• heterogeneous vehicles
• vehicle routing

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.

• 出版日期2011-8