This paper deals with the multiple vehicle balancing problem (MVBP). Given a fleet of vehicles of limited capacity, a set of vertices with initial and target inventory levels and a distribution network, the MVBP requires to design a set of routes along with pickup and delivery operations such that inventory is redistributed among the vertices without exceeding capacities, and routing costs are minimized. The MVBP is NP‐hard, generalizing several problems in transportation, and arising in bike‐sharing systems. Using theoretical properties of the problem, we propose an integer linear programming formulation and introduce strengthening valid inequalities. Lower bounds are computed by column generation embedding an ad‐hoc pricing algorithm, while upper bounds are obtained by a memetic algorithm that separate routing from pickup and delivery operations. We combine these bounding routines in both exact and matheuristic algorithms, obtaining proven optimal solutions for MVBP instances with up to 25 stations.
The multiple vehicle balancing problem / M. Casazza, A. Ceselli, D. Chemla, F. Meunier, R. Wolfler Calvo. - In: NETWORKS. - ISSN 0028-3045. - 72:3(2018), pp. 337-357. ((Intervento presentato al 8. convegno International Workshop on Vehicle Routing, Intermodal Transport, and Related Areas (ROUTE) tenutosi a Rambouillet nel 2016 [10.1002/net.21822].
The multiple vehicle balancing problem
M. Casazza
;A. Ceselli;
2018
Abstract
This paper deals with the multiple vehicle balancing problem (MVBP). Given a fleet of vehicles of limited capacity, a set of vertices with initial and target inventory levels and a distribution network, the MVBP requires to design a set of routes along with pickup and delivery operations such that inventory is redistributed among the vertices without exceeding capacities, and routing costs are minimized. The MVBP is NP‐hard, generalizing several problems in transportation, and arising in bike‐sharing systems. Using theoretical properties of the problem, we propose an integer linear programming formulation and introduce strengthening valid inequalities. Lower bounds are computed by column generation embedding an ad‐hoc pricing algorithm, while upper bounds are obtained by a memetic algorithm that separate routing from pickup and delivery operations. We combine these bounding routines in both exact and matheuristic algorithms, obtaining proven optimal solutions for MVBP instances with up to 25 stations.File | Dimensione | Formato | |
---|---|---|---|
The Multiple Vehicle Balancing Problem.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
385.88 kB
Formato
Adobe PDF
|
385.88 kB | Adobe PDF | Visualizza/Apri |
Casazza_et_al-2018-Networks.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
794.59 kB
Formato
Adobe PDF
|
794.59 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.