Details

Autor(en) / Beteiligte

• Nguyen, Khanh-Phuong
• Ban, Ha-Bang

Titel

Metaheuristic for the Capacitated Multiple Traveling Repairman Problem

Ist Teil von

• International journal of advanced computer science & applications, 2020, Vol.11 (5)

Ort / Verlag

West Yorkshire: Science and Information (SAI) Organization Limited

Erscheinungsjahr

2020

Quelle

EZB Electronic Journals Library

Beschreibungen/Notizen

• 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.