This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ibaraki, T. Articles by Yagiura, M. Search for Related Content

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

Department of Informatics, School of Science and Technology, Kwansei Gakuen University, 2-1 Gakuen, Sanda 669-1337, Japan
Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
Department of Logistics and Information Engineering, Faculty of Marine Technology, Tokyo University of Marine Science and Technology, 2-1-6 Etchujima, Kouto-ku, Tokyo 135-8533, Japan
Communication & High Technology, Accenture, Nihon Seimei Akasaka Daini Bldg., 7-1-16 Akasaka Minato-ku, Tokyo 107-8672, Japan
National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan
ibaraki{at}ksc.kwansei.ac.jp
imahori{at}simplex.t.u-tokyo.ac.jp
kubo{at}e.kaiyodai.ac.jp
tomoyasu.masuda{at}accenture.com
uno{at}nii.jp
yagiura{at}i.kyoto-u.ac.jp

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.

Key Words: vehicle routing; adaptive multistart local search; dynamic programming; time-window constraints; metaheuristics; very large scale neighborhood
History: Received: August 2002; revised: March 2003; accepted: March 2003.

This article has been cited by other articles:

				J.-Y. Potvin State-of-the Art Review--Evolutionary Algorithms for Vehicle Routing INFORMS Journal on Computing, October 1, 2009; 21(4): 518 - 548. [Abstract] [PDF]

				A. Ceselli, G. Righini, and M. Salani A Column Generation Algorithm for a Rich Vehicle-Routing Problem Transportation Science, February 1, 2009; 43(1): 56 - 69. [Abstract] [PDF]

				A. Lim and X. Zhang A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows INFORMS Journal on Computing, January 1, 2007; 19(3): 443 - 457. [Abstract] [PDF]