General Variable Neighborhood Search for the Quote-Travelling Repairman Problem

The Quota-Travelling Repairman Problem (Q-TRP) tries to find a tour that minimizes the waiting time while the profit collected by a repairman is not less than a predefined value. The Q-TRP is an extended variant of the Travelling Repairman Problem (TRP). The problem is NP-hard problem; therefore, metaheuristic is a natural approach to provide near-optimal solutions for large instance sizes in a short time. Currently, several algorithms are proposed to solve the TRP. However, the quote constraint does not include, and these algorithms cannot be adapted to the Q-TRP. Therefore, developing an efficient algorithm for the Q-TRP is necessary. In this paper, we suggest a General Variable Neighborhood Search (GVNS) that combines with the perturbation and Adaptive Memory (AM) techniques to prevent the search from local optima. The algorithm is implemented with a benchmark dataset. The results demonstrate that good solutions, even the optimal solutions for the problem with 100 vertices, can be reached in a short time. Moreover, the algorithm is comparable with the other metaheuristic algorithms in accordance with the solution quality.

@article{Ban2020,
  title     = {General Variable Neighborhood Search for the Quote-Travelling Repairman Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {11},
  number    = {4},
  year      = {2020},
  publisher = {The Science and Information Organization},
  author    = {Ha-Bang Ban},
  doi       = {10.14569/IJACSA.2020.0110490},
  url       = {https://doi.org/10.14569/IJACSA.2020.0110490}
}