Improved large neighborhood search algorithm for vehicle routing problem with time windows
FU Ke-qiang · Computer Integrated Manufacturing Systems · 2004
The vehicle routing problem with time windows (VRPTW) cannot be solved effectively by using the existing Large Neighborhood Search (LNS) algorithm. A universal mathematical model of VRPTW was built. By analyzing the relation of several main variables, a simple, fast deterministic initial algorithm was proposed. An improved LNS algorithm was put forward based on the shortest route priority strategy, which could solve the problems with long scheduling horizon effectively. The strategy could also be applied to solving the problems with short scheduling horizon to accelerate searching process. Experiment results show that the improved algorithm can find the optimal or near optimal solution to VRPTW in short time.