Open vehicle routing problem with driver nodes and time deadlines

Abstract

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.

Keywords:

• vehicle routing
• open vehicle routing
• tabu search
• heuristics
• time deadlines

Acknowledgements

We thank the editor and two referees for bringing additional relevant references to our attention. Deniz Aksen and Zeynep Özyurt were supported by KÜMPEM, Koç University Migros Professional Training Center. Necati Aras was supported by the Boğaziçi University Research Fund Grant no. 05HA301D.