The multiple vehicle balancing problem. Issue 3 (30th March 2018)

• Record Type: Journal Article
• Authors: Casazza, Marco; Ceselli, Alberto; Chemla, Daniel; Meunier, Frédéric; Wolfler Calvo, Roberto
• Is Part Of: Networks. Volume 72:Issue 3(2018)
• Page Start: 337
• Page End: 357
• Publication Date: 2018-03-30
• Subjects: bicycle sharing system -- column generation -- dominance properties -- memetic algorithm -- valid inequalities -- vehicle routing; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21822
• Languages: English
• ISSNs: 0028-3045

Abstract

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.