The single-vehicle routing problem with unrestricted backhauls

Suppose that a private carrier delivers to a set of customers and also has a number of (optional) backhaul opportunities. It wants to choose the best of these, depending on the revenue generated, and insert them in a revised tour. This will be at an expense of deviation from the original tour, because, here, deliveries need not precede backhauls. The problem is to find the mixed tour whose net cost is the lowest, selecting the most profitable backhauls subject to the overall capacity. We thus generalize several other vehicle routing problems with backhauls. A mixed-integer model is developed for the problem. It is based on Miller-Tucker-Zemlin subtour elimination constraints. We address several improvement techniques aimed at increasing computational tractability of the formulation. Computational results show that medium-sized problems can be solved optimally in a reasonable time by using a general-purpose commercial solver. (C) 2003 Wiley Periodicals, Inc.