AN EXACT ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH BACKHAULS

The Vehicle Routing Problem with Backhauls is an extension of the capa citated Vehicle Routing Problem where the customers' set is partitione d into two subsets. The first is the set of Linehaul, or Delivery, cus tomers, 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 con sider, in a unified framework both the symmetric and the asymmetric ve rsions of the vehicle routing problem with backhauls, for which we int eger linear programming model and a Lagrangian lower bound which is st rengthened in a cutting plane fashion. The Lagrangian lower bound is t hen combined according to the additive approach, with a lower bound ob tained by dropping the capacity, constraints, thus obtaining an. effec tive overall bounding procedure. A branch-and-bound algorithm, reducti on procedures and dominance criteria are also described. Computational tests on symmetric and asymmetric instances from the literature, invo lving up to 100 customers, are given, showing the effectiveness of the proposed approach.