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.
bicycle sharing system; column generation; dominance properties; memetic algorithm; valid inequalities; vehicle routing
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
Article (author)
File in questo prodotto:
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

Caricamento 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: http://hdl.handle.net/2434/640386
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact