Metaheuristic for the Capacitated Multiple Traveling Repairman Problem

The Capacitated Multiple Traveling Repairmen Problem (CmTRP) is an extension of the Multiple Traveling Repairmen Problem (mTRP). In the CmTRP, the number of vehicles is dispatched to serve a set of customers, while each vehicle’s capacity is limited by a predefined-value as well as each customer is visited exactly once. The goal is to find a tour that minimizes the sum of waiting times. The problem is NP-hard because it is harder than the mTRP. Even finding a feasible solution is also NP-hard problem. To solve medium and large size instances, a metaheuristic algorithm is proposed. The first phase constructs a feasible solution by combining between the Nearest Neighborhood Search (NNS) and Variable Neighborhood Search (VNS), while the optimization phase develops the feasible solution by the General Variable Neighborhood Search (GVNS). The combination maintains the balance between intensification and diversification to escape local optima. The proposed algorithm is implemented on benchmark instances from the literature. The results indicate that the developed algorithm obtains good feasible solutions in a short time, even for the cases with up to 200 vertices.

@article{Nguyen2020,
  title     = {Metaheuristic for the Capacitated Multiple Traveling Repairman Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {11},
  number    = {5},
  year      = {2020},
  publisher = {The Science and Information Organization},
  author    = {Khanh-Phuong Nguyen and Ha-Bang Ban},
  doi       = {10.14569/IJACSA.2020.0110550},
  url       = {https://doi.org/10.14569/IJACSA.2020.0110550}
}