Solving a real-life roll-on–roll-off waste collection problem with column generation

In this paper, we develop an intelligent solution to a complex, real-life vehicle routing problem in the waste managementsector. Waste management companies deliver various types of empty waste containers to industrial customers, to be filledwith different types of waste, after which the containers are picked up again. The full containers are transported to a so-calledwaste management depot or waste handling depot, where they are emptied, after which they are reused. Empty containersare stocked in various stock depots. Time windows in which containers may be picked up and delivered at the customers andopening hours of the different depots have to be taken into account additionally. Very importantly, there are two types ofwaste collection trucks that can, respectively, carry one or two containers. The resulting vehicle routing problem belongs to aclass of so-called roll-on–roll-off problems, characterized by unit demand. Additionally, the problem discussed in this paperhas several characteristics (multiple waste types, multiple container types, multiple depots, a heterogeneous fleet, pickup anddelivery, time window constraints, and other) that make solving it a difficult task. To solve this problem, we develop a novelcolumn generation scheme that incorporates a heuristic approach to generate new columns. The master problem is solved bylinear relaxation of a set partitioning problem. New routes (columns) are generated by a constructive heuristic loosely basedon Solomon’s insertion heuristic for the vehicle routing problem with time windows. The construction heuristic operates ona reformulated version of the roll-on–roll-off problem, i.e., a generalized vehicle routing problem with time windows. Thealgorithm—called wmpopt—is submitted to an extensive sensitivity analysis to determine its response to different parametersettings. After this, we test it on four real-life problem instances and compare its results to those obtained by a commercialsolver. We show that wmpopt achieves much better solutions than the commercial solver in similar computing times.