The generalized rollon-rolloff vehicle routing problem and savings-based algorithm

Taking the waste collection management as the practical background, the rollon-rolloff vehicle routing problem (RRVRP) involves tractors pulling large containers between customer locations and the disposal facility. Each used-tractor begins and ends its route at the depot. Customer demand includes emptying a full container, ordering an empty container or changing a container. The objective is to find tractor routes that feature the minimum amount of total nonproductive time. In the literature the RRVRP is formulated as the node routing problem, and the “trip” definition that is the complete transport service of a container is used. To relax some assumptions of the RRVRP to cater to practical desires, we present a variant called the generalized RRVRP (G-RRVRP). The G-RRVRP generalizes the practical background, the objective function and the demand flow, and considers specially container loading and unloading time constraints. The G-RRVRP classifies demand into loaded-container demand and cargo demand with time windows. On condition of respecting container loading/unloading time and customer time windows, the G-RRVRP can design tractor routes for the synchronous scheduling of loaded and empty containers so as to ensure the timeliness of transport service. The G-RRVRP aims to minimize the total running cost of used tractors, instead of the total nonproductive time of tractors adopted by the RRVRP. A mixed integer linear programming model for the G-RRVRP is proposed. The Benders decomposition algorithm involving Pareto-optimal cuts and Benders decomposition-callback implementation, and a two-stage heuristic involving the savings algorithm followed by a local search phase are provided. The mathematical formulation and the two-stage heuristic are tested by solving 40 small-scale instances and 20 benchmark instances. Small-scale instances can be solved directly by CPLEX through the Benders decomposition strategies to find exact solutions. The case study indicates the applicability of the G-RRVRP model and the two-stage heuristic to realistic-size problems abstracted from intercity linehaul systems. The computational experiments and case study indicate that the heuristic can solve various instances of the G-RRVRP such that the solution quality and the computation time are acceptable.