Open Vehicle Routing Problem with Time Deadlines: Solution Methods and an Application

Abstract. In the open route version of the well-known vehicle routing problem, vehicles are not required to return to the depot; or if they are required, then they return by traveling the same route back. In this study, we present a modified Clarke-Wright parallel savings al-gorithm, a nearest insertion algorithm and a tabu search heuristic for the open vehicle rout-ing problem with time deadlines. Some random test problems and a real-life school bus routing problem are solved by these heuristics, and results are compared.