An Exact Algorithm for the Vehicle Routing Problem with Backhauls

Paolo Toth and Daniele Vigo
Additional contact information
Paolo Toth: D.E.I.S., Università di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
Daniele Vigo: D.E.I.S., Università di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy

Transportation Science, 1997, vol. 31, issue 4, 372-385

Abstract: The Vehicle Routing Problem with Backhauls is an extension of the capacitated Vehicle Routing Problem where the customers' set is partitioned into two subsets. The first is the set of Linehaul, or Delivery, customers, while the second is the set of Backhaul, or Pickup, customers. The problem is known to be NP-hard in the strong sense and finds many practical applications in distribution planning. In this paper we consider, in a unified framework, both the symmetric and the asymmetric versions of the vehicle routing problem with backhauls, for which we present a new integer linear programming model and a Lagrangian lower bound which is strengthened in a cutting plane fashion. The Lagrangian lower bound is then combined, according to-the additive approach, with a lower bound obtained by dropping the capacity constraints, thus obtaining an effective overall bounding procedure. A branch-and-bound algorithm, reduction procedures and dominance criteria are also described. Computational tests on symmetric and asymmetric instances from the literature, involving up to 100 customers, are given, showing the effectiveness of the proposed approach.

Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (41)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.31.4.372 (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:31:y:1997:i:4:p:372-385

Access Statistics for this article

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