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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2021
18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW)
Online streaming
15-17 June, 2020
5
223
235
Martins, Lucas Burahem; Iori, Manuel; Moreira, Mayron César O.; Zucchi, Giorgio
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].
File in questo prodotto:
File
BurahemMartinsIoriMoreiraZucchi2021.pdf

Accesso riservato

Descrizione: BurahemMartinsIoriMoreiraZucchi2021
Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 137.58 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11380/1244257`