Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints

T. Ibaraki, S. Imahori, M. Kubo, T. Masuda, T. Uno and M. Yagiura
We propose local search algorithms for the vehicle routing problem with soft time window constraints. The time window constraint for each customer is treated as a penalty function, which is very general in the sense that it can be non-convex and discontinuous as long as it is piecewise linear. The generality of time window constraints allows us to handle a wide variety of scheduling problems. As such an example, we mention in this paper an application to a production scheduling problem with inventory cost. In our algorithm, we use local search to assign customers to vehicles and to find orders of customers for vehicles to visit. It employs a new neighborhood, called the cyclic exchange neighborhood, in addition to standard neighborhoods for the vehicle routing problem. After fixing the order of customers for a vehicle to visit, we must determine the optimal start times of processing at customers so that the total penalty is minimized. We show that this problem can be efficiently solved by using dynamic programming, which is then incorporated in our algorithm. We also report computational results for various benchmark instances of the vehicle routing problem, as well as real world instances of a production scheduling problem.

Keywords: adaptive multi-start local search, dynamic programming, general time window constraints, local search, metaheuristics, vehicle routing problem, very large scale neighborhood.

Transportation Science, 39 (2005) 206-232.

Back to the Paper List