Vehicle routing for mixed solid waste collection - comparing alternative hierarchical formulations

Abstract

The aim of this paper is to present and compare alternative hierarchical formulations for the periodic vehicle routing problem for solid waste collection. The solution of this problem is a one-week plan of daily routes for the transportation of mixed solid waste from containers to disposal facilities, taking into consideration the frequency of collection of each container within the planning horizon, the road network and the resources available. The objective is to minimize operation costs. The real-world case that supported this study was the collection of mixed solid waste in Ponte de Lima, a municipality in the north of Portugal, and the problem was modelled as a Periodic Vehicle Routing Problem (PVRP) with the additional constraint that routes must pass through one of the alternative disposal facilities before returning to the depot. Based on this real case scenario, we propose a framework of MIP models with three hierarchical approaches besides the monolithic model. The hierarchical approaches are identified by the aggregation of the decisions in each level: (1) assign and route together; (2) assign days first - assign vehicles and route second; (3) assign first - route second and (4) assign days first - assign vehicles second - route third. Some new estimates for downstream constraints were developed and integrated in upstream levels in order to guarantee feasibility.