In this paper, we propose a combined algorithm based on an Iterated Local Search (ILS) and a mathematical model to solve the Time Window Assignment Vehicle Routing Problem (TWAVRP). The TWAVRP appears when the volume of customer demands is uncertain and time windows should be allocated to customers so as to minimize expected travel costs. Our goal is to find a heuristic strategy that can efficiently improve the current TWAVRP solution methods in the literature. For this purpose, we first use an ILS algorithm to generate feasible sets of routes. Then, we invoke a Mixed Integer Linear Programming formulation that assigns time windows to customers and selects the subset of routes of minimum expected cost. Computational results performed on benchmark instances show that our algorithm is competitive with respect to the literature, especially for instances with more than 45 clients.
On Solving the Time Window Assignment Vehicle Routing Problem via Iterated Local Search / Martins, Lucas Burahem; Iori, Manuel; Moreira, Mayron César O.; Zucchi, Giorgio. - 5:(2021), pp. 223-235. (Intervento presentato al convegno 18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW) tenutosi a Online streaming nel 15-17 June, 2020) [10.1007/978-3-030-63072-0_18].
On Solving the Time Window Assignment Vehicle Routing Problem via Iterated Local Search
Iori, Manuel;Zucchi, Giorgio
2021
Abstract
In this paper, we propose a combined algorithm based on an Iterated Local Search (ILS) and a mathematical model to solve the Time Window Assignment Vehicle Routing Problem (TWAVRP). The TWAVRP appears when the volume of customer demands is uncertain and time windows should be allocated to customers so as to minimize expected travel costs. Our goal is to find a heuristic strategy that can efficiently improve the current TWAVRP solution methods in the literature. For this purpose, we first use an ILS algorithm to generate feasible sets of routes. Then, we invoke a Mixed Integer Linear Programming formulation that assigns time windows to customers and selects the subset of routes of minimum expected cost. Computational results performed on benchmark instances show that our algorithm is competitive with respect to the literature, especially for instances with more than 45 clients.File | Dimensione | Formato | |
---|---|---|---|
BurahemMartinsIoriMoreiraZucchi2021.pdf
Accesso riservato
Descrizione: BurahemMartinsIoriMoreiraZucchi2021
Tipologia:
AAM - Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione
137.58 kB
Formato
Adobe PDF
|
137.58 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris