An exact method for the vehicle routing problem with backhauls

An exact method for the vehicle routing problem with backhauls

0.00 Avg rating0 Votes
Article ID: iaor2001744
Country: United States
Volume: 33
Issue: 3
Start Page Number: 315
End Page Number: 329
Publication Date: Aug 1999
Journal: Transportation Science
Authors: , ,
Keywords: transportation: road, programming: integer
Abstract:

We consider the problem in which a fleet of vehicles located at a central depot is to be optimally used to serve a set of customers partitioned into two subsets of linehaul and the backhaul customers. Each route starts and ends at the depot and the blackhaul customers must be visited after the linehaul customers. A new (0–1) integer programming formulation of this problem is presented. We describe a procedure that computes a valid lower bound to the optimal solution cost by combining different heuristic methods for solving the dual of the LP-relaxation of the exact formulation. An algorithm for the exact solution of the problem is presented. Computational tests on problems proposed in the literature show the effectiveness of the proposed algorithms in solving problems up to 100 customers.

Reviews

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