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

TLDR

Time‑window constraints can be highly general, enabling the handling of diverse scheduling problems. The study proposes local search algorithms for vehicle routing with soft time‑window constraints. The algorithm models time‑window penalties as piecewise linear functions, uses local search with a cyclic‑exchange neighborhood to assign and order customers, and applies dynamic programming to compute optimal start times for each vehicle. Computational experiments on benchmark and real‑world instances demonstrate the effectiveness of the proposed approach.

Abstract

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 nonconvex and discontinuous as long as it is piecewise linear. In our algorithm, we use local search to assign customers to vehicles and to find orders of customers for vehicles to visit. Our algorithm employs an advanced 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 report computational results for various benchmark instances of the vehicle routing problem. The generality of time-window constraints allows us to handle a wide variety of scheduling problems. As an example, we mention in this paper an application to a production scheduling problem with inventory cost, and report computational results for real-world instances.