Abstract: 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.

Ha-Bang Ban, “General Variable Neighborhood Search for the Quote-Travelling Repairman Problem” International Journal of Advanced Computer Science and Applications(IJACSA), 11(4), 2020. http://dx.doi.org/10.14569/IJACSA.2020.0110490

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