Open vehicle routing problem with driver nodes and time deadlines

Aksen D., Özyurt Z., ARAS M. N.

Journal of the Operational Research Society, cilt.58, sa.9, ss.1223-1234, 2007 (SCI-Expanded, SSCI, Scopus) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 58 Sayı: 9
  • Basım Tarihi: 2007
  • Doi Numarası: 10.1057/palgrave.jors.2602249
  • Dergi Adı: Journal of the Operational Research Society
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Sayfa Sayıları: ss.1223-1234
  • Anahtar Kelimeler: Heuristics, Open vehicle routing, Tabu search, Time deadlines, Vehicle routing
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

In this paper, we consider a variant of the open vehicle routing problem in which vehicles depart from the depot, visit a set of customers, and end their routes at special nodes called driver nodes. A driver node can be the home of the driver or a parking lot where the vehicle will stay overnight. The resulting problem is referred to as the open vehicle routing problem with driver nodes (OVRP-d). We consider three classes of OVRP-d: with no time constraints, with a maximum route duration, and with both a maximum route duration as well as time deadlines for visiting customers. For the solution of these problems, which are not addressed previously in the literature, we develop a new tabu search heuristic. Computational results on randomly generated instances indicate that the new heuristic exhibits a good performance both in terms of the solution quality and computation time. © 2007 Operational Research Society Ltd. All rights reserved.