In this paper, we study the multi-depot k-traveling repairman problem. This problem extends the traditional traveling repairman problem to the multi-depot case. Its objective, similar to the single depot variant, is the minimization of the sum of the arrival times to customers. We propose two distinct formulations to model the problem, obtained on layered graphs. In order to find feasible solutions for the largest instances, we propose a hybrid genetic algorithm where initial solutions are built using a splitting heuristic and a local search is embedded into the genetic algorithm. The efficiency of the mathematical formulations and of the solution approach are investigated through computational experiments. The proposed models are scalable enough to solve instances up to 240 customers.

The multi-depot k-traveling repairman problem / Bruni, M. E.; Khodaparasti, S.; Martínez-Salazar, I.; Nucamendi-Guillén, S.. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - ELETTRONICO. - 16:(2022), pp. 2061-2709. [10.1007/s11590-021-01845-7]

The multi-depot k-traveling repairman problem

Bruni M. E.;Khodaparasti S.;
2022

Abstract

In this paper, we study the multi-depot k-traveling repairman problem. This problem extends the traditional traveling repairman problem to the multi-depot case. Its objective, similar to the single depot variant, is the minimization of the sum of the arrival times to customers. We propose two distinct formulations to model the problem, obtained on layered graphs. In order to find feasible solutions for the largest instances, we propose a hybrid genetic algorithm where initial solutions are built using a splitting heuristic and a local search is embedded into the genetic algorithm. The efficiency of the mathematical formulations and of the solution approach are investigated through computational experiments. The proposed models are scalable enough to solve instances up to 240 customers.
File in questo prodotto:
File Dimensione Formato  
Bruni2022_Article_TheMulti-depotK-travelingRepai.pdf

accesso aperto

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Creative commons
Dimensione 515.58 kB
Formato Adobe PDF
515.58 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2980529