The multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem

In the Multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem (M-RRVRP), one of the very important pickup and disposal problems in the sanitation industry, tractors move large trailers, one at a time, between customer locations such as construction sites and shopping centers, disposal facilities and inventory locations. In this paper, we model the M-RRVRP as a time constrained vehicle routing problem on a multigraph (TVRP-MG). We then formulate the TVRP-MG as a set partitioning problem with an additional constraint and describe an exact method for solving the TVRP-MG. This exact method is based on a bounding procedure that combines three lower bounds derived from different relaxations of the formulation of the problem. Further, we obtain a valid upper bound and show how this bounding procedure can transform the solution of a Lagrangean lower bound into a feasible solution.