The multiple vehicle balancing problem

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.