Details

Autor(en) / Beteiligte

• Ban, Ha-Bang

Titel

Penalty Variable Neighborhood Search for the Bounded Single-Depot Multiple Traveling Repairmen Problem

Ist Teil von

• Informatica (Ljubljana), 2021-03, Vol.45 (1), p.93-104

Ort / Verlag

Ljubljana: Slovenian Society Informatika / Slovensko drustvo Informatika

Erscheinungsjahr

2021

Link zum Volltext

Quelle

EZB Free E-Journals

Beschreibungen/Notizen

• Multiple Traveling Repairmen Problem (mTRP) is a class of NP-hard combinatorial optimization problems with many practical applications. In this paper, a general variant of mTRP, also known as the Bounded Single-Depot Multiple Traveling Repairmen Problem (Bounded-mTRP), is introduced. In the Bounded-mTRP problem, a ñeet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from the depot is only allowed to visit the number of customers within a predetermined interval, and each customer must be visited exactly once. Such restrictions appear in real-life applications where the purpose is to have a good balance of workloads for the repairmen. The goal is to ñnd the order of customer visits that minimizes the sum of waiting times. In our work, the proposed algorithm is encouraged by the efficiency of the algorithms in [15, 19, 20] that are mainly based on the principles of the VNS [14]. The penalty VNS extends the well-known VNS [14] by including constraint penalization, to solve the Bounded-mTRP effectively. Extensive numerical experiments on benchmark instances show that our algorithm reaches the optimal solutions for the problem with 76 vertices at a reasonable amount of time. Moreover, the new best-known solutions are found in comparison with the state-of-the-art metaheuristic algorithms.