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.
|Titolo:||The multiple vehicle balancing problem|
CASAZZA, MARCO (Corresponding)
|Parole Chiave:||bicycle sharing system; column generation; dominance properties; memetic algorithm; valid inequalities; vehicle routing|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
Settore MAT/09 - Ricerca Operativa
|Data di pubblicazione:||2018|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1002/net.21822|
|Appare nelle tipologie:||01 - Articolo su periodico|