Premium
The single‐vehicle routing problem with unrestricted backhauls
Author(s) -
Süral Haldun,
Bookbinder James H.
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10067
Subject(s) - solver , computer science , backhaul (telecommunications) , vehicle routing problem , mathematical optimization , set (abstract data type) , revenue , routing (electronic design automation) , mathematics , computer network , economics , programming language , accounting , base station
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. © 2003 Wiley Periodicals, Inc.