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

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

0.00 Avg rating0 Votes
Article ID: iaor20072484
Country: United Kingdom
Volume: 33
Issue: 9
Start Page Number: 2667
End Page Number: 2702
Publication Date: Sep 2006
Journal: Computers and Operations Research
Authors: , ,
Keywords: programming: integer, vehicle routing & scheduling, location
Abstract:

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. Our computational results show that the proposed method is very effective in deriving an optimal or near optimal solution to the M-RRVRP in a reasonable amount of computing time. Since the capacitated vehicle routing problem (CVRP) can be transformed into a TVRP-MG, we tested our procedure on 11 instances of the CVRP. Our computational results show that our procedure very effectively found the optimal solution to 7 of the 11 instances of the CVRP. In many cases, our procedure was at least 10 times faster than the procedure proposed by Fukasawa et al. Both our procedure and the procedure of Fukasawa et al. solved problem E-n76-k10, the most famous CVRP instance that until recently was unsolved.

Reviews

Required fields are marked *. Your email address will not be published.