The single-vehicle routing problem with unrestricted backhauls


Sural H., Bookbinder J.

NETWORKS, cilt.41, sa.3, ss.127-136, 2003 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 41 Sayı: 3
  • Basım Tarihi: 2003
  • Doi Numarası: 10.1002/net.10067
  • Dergi Adı: NETWORKS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.127-136
  • Anahtar Kelimeler: vehicle routing with backhauls, mixed pickup and delivery, private carriage, TRAVELING SALESMAN PROBLEM, ALGORITHM, DELIVERY
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.