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 stations with initial and target inventory levels and a distribution network, the MVBP requires to design a set of routes and pickup and delivery operations along each route such that inventory is redistributed among the stations without exceeding the vehicle capacities and such that routing costs are minimized. The MVBP arises in bicycle sharing systems, where rebalancing is needed between stations when expected demand and number of available bicycles do not match. The MVBP turns out to be NP-hard, generalizing several problems in transportation like the Split Delivery Vehicle Routing Problem. We propose an integer linear programming formulation. Lower bounds to optimal solution values are computed by a column generation routine embedding an ad-hoc pricing algorithm; we also introduce strengthening valid inequalities. Upper bounds are obtained by a memetic algorithm based on a combin-atorial encoding of the solutions that allows to focus on routing and to consider the pickup and delivery operations in a post-processing phase. We combine lower and upper bounding routines in both exact and matheuristic algorithms, obtaining proven optimal solutions for MVBP instances with up to 25 stations and an unbounded number of vehicles, or up to 20 stations and 5 vehicles