The present work models a routing problem not yet addressed in the literature where open routes between depots are allowed, i.e., all routes start at one depot but can end at the same one or at a different depot, depending on the objective considered. This study has been motivated by a real-life problem of a waste cooking oil collection system characterized by the existence of multiple depots with an outsourced vehicle fleet. The company operates 3 depots and has to collect oil containers at 303 sites (restaurants, schools and canteens). In a collection day, the full oil containers are collected and exchanged for empty and cleaned ones. Vehicles leave depots with empty containers and return to a depot to unload and clean the meanwhile full oil containers. Strategically, the company has decided to contract independent vehicles to collect this type of waste. The contracted vehicles involve the payment of a fixed cost per vehicle and a variable cost per kilometer travelled. The objective of the company is to minimize the total cost which considers the number of vehicles required and the total distance travelled when visiting all the collection sites. The starting location can be different from the ending location, since a hired vehicle fleet is used, but all routes have to start and end at one depot of the network. Due to the characteristics of the problem under study a variant of the standard multi-depot vehicle routing problem is here studied, where vehicles may start and finish their routes at different depots. A mixed-integer linear programming (MILP) formulation with capacity and duration constraints is proposed to solve such problem, which from now on is identified as the Multi-Depot Vehicle Route with Open Routes (MDVRP-OR). To test the developed model for the MDVRP-OR and to assess the effect of allowing open routes between depots over the traditional operational settings of having only closed routes, benchmark literature instances involving up to 360 customers for the MDVRP are solved. Finally, the model developed is applied to the real case study providing the vehicle routes planning where a decrease of 13% on mileage and 11% on fleet hiring cost are achieved, when comparing with the current company solution.

--

Routing, Cooking Oil, Open routes