An Exact Method for the Vehicle Routing Problem with Backhauls

Aristide Mingozzi, Simone Giorgi and Roberto Baldacci
Additional contact information
Aristide Mingozzi: Department of Mathematics, University of Bologna, Piazza di Porta S. Donato, 5, 40127 Bologna, Italy
Simone Giorgi: Department of Mathematics, University of Bologna, Piazza di Porta S. Donato, 5, 40127 Bologna, Italy
Roberto Baldacci: The Management School, Imperial College, 53 Prince's Gate Exhibition Road, London SW7 2PG, United Kingdom

Transportation Science, 1999, vol. 33, issue 3, 315-329

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 backhaul customers. Each route starts and ends at the depot and the backhaul 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.

Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.33.3.315 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:33:y:1999:i:3:p:315-329

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().