Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints
Authors:
- 1 May 2005
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 39 (2) , 206-232
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.Keywords
This publication has 29 references indexed in Scilit:
- Local optimization and the Traveling Salesman Problem2005
- Minimizing a Convex Cost Closure SetSIAM Journal on Discrete Mathematics, 2003
- A survey of very large-scale neighborhood search techniquesDiscrete Applied Mathematics, 2002
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximationsEuropean Journal of Operational Research, 2002
- Very large‐scale neighborhood searchInternational Transactions in Operational Research, 2000
- Ejection chains, reference structures and alternating path methods for traveling salesman problemsDiscrete Applied Mathematics, 1996
- Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per InequalitySIAM Journal on Computing, 1994
- A new adaptive multi-start technique for combinatorial global optimizationsOperations Research Letters, 1994
- Large-step markov chains for the TSP incorporating local search heuristicsOperations Research Letters, 1992
- Discrete OptimizingJournal of the Society for Industrial and Applied Mathematics, 1965