This paper addresses the k-traveling repairman problem with profits and uncertain travel times, a vehicle routing problem aimed at visiting a subset of customers in order to collect a revenue, which is a decreasing function of the uncertain arrival times. The introduction of the arrival time in the objective function instead of the travel time, which is common in most vehicle routing problems, poses compelling computational challenges, emphasized by the incorporation of the stochasticity in travel times. For tackling the solution of the risk-averse k-traveling repairman problem with profits, in this paper is proposed a hybrid heuristic, where a reactive greedy randomized adaptive search procedure is used as a multi-start framework, equipped with an adaptive local search algorithm. The effectiveness of the solution approach is shown through an extensive experimental phase, performed on a set of instances, generated from three sets of benchmark instances containing up to 200 nodes.

A hybrid reactive GRASP heuristic for the risk-averse k-traveling repairman problem with profits

Bruni M. E.
;
Beraldi P.;Khodaparasti S.
2020

Abstract

This paper addresses the k-traveling repairman problem with profits and uncertain travel times, a vehicle routing problem aimed at visiting a subset of customers in order to collect a revenue, which is a decreasing function of the uncertain arrival times. The introduction of the arrival time in the objective function instead of the travel time, which is common in most vehicle routing problems, poses compelling computational challenges, emphasized by the incorporation of the stochasticity in travel times. For tackling the solution of the risk-averse k-traveling repairman problem with profits, in this paper is proposed a hybrid heuristic, where a reactive greedy randomized adaptive search procedure is used as a multi-start framework, equipped with an adaptive local search algorithm. The effectiveness of the solution approach is shown through an extensive experimental phase, performed on a set of instances, generated from three sets of benchmark instances containing up to 200 nodes.
Adaptive neighbourhood search; GRASP; Mean-risk model; Traveling repairman problem
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/20.500.11770/301429
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 12
social impact