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 ()
Additional contact information
T. Ibaraki: Department of Informatics, School of Science and Technology, Kwansei Gakuen University, 2-1 Gakuen, Sanda 669-1337, Japan
S. Imahori: Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
M. Kubo: 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
T. Masuda: Communication & High Technology, Accenture, Nihon Seimei Akasaka Daini Bldg., 7-1-16 Akasaka Minato-ku, Tokyo 107-8672, Japan
T. Uno: National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
M. Yagiura: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan

Transportation Science, 2005, vol. 39, issue 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: vehicle routing; adaptive multistart local search; dynamic programming; time-window constraints; metaheuristics; very large scale neighborhood (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (31)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1030.0085 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:39:y:2005:i:2:p:206-232

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().