A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows.

HEURISTIC; ROUTING (Computer network management); TRANSPORTATION problems (Programming); CONSTRAINT programming; ALGORITHM research; SCHEDULING; COMPUTER systems

The vehicle routing problem with time windows (VRPTW) is an important problem in logistics. The problem is to serve a number of customers at minimum cost without violating the customers' time-window constraints or the vehicle-capacity constraint. In this paper, we propose a two-stage algorithm for the VRPTW. The algorithm first minimizes the number of vehicles with an ejection pool to hold temporarily unserved customers, which enables the algorithm to go through the infeasible solution space. Then it minimizes the total travel distance using a multi-start iterated hill-climbing algorithm with classical and new operators including generalized ejection chains, which enable the algorithm to search a larger neighborhood. We applied the algorithm to Solomon's 56 VRPTW instances and Gehring and Homberger's 300 extended instances. The experimental results showed that the algorithm is effective and efficient in reducing the number of vehicles and is also very competitive in terms of distance minimization. The m-VRPTW is a variant of the VRPTW in which a limited number of vehicles is available. A feasible solution to m-VRPTW may contain some unserved customers due to the insufficiency of vehicles. The primary objective of m-VRPTW is to maximize the number of customers served. We extended our VRPTW algorithm to solve m-VRPTW and the experimental results showed consistently good performance of the algorithm when compared with other methods. [ABSTRACT FROM AUTHOR]

Copyright of INFORMS Journal on Computing is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)