An improved LNS algorithm for real-time vehicle routing problem with time windows

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 2, February 2012, Pages 151-163

Lianxi, Hong

This paper studies the dynamic vehicle routing problem with hard time windows (DVRPTW). The main study course of this problem was briefly reviewed. The solving strategy and algorithm of the problem are put forward. First of all, DVRPTW problem is decomposed into a series of static VRPTW. When and how to decompose the DVRP is the issue, that must be addressed. An event-trigger mechanism has been proposed and used to decompose the DVRPTW into a series of system delay-snapshots. The trigger event to be adopted is a new request arrival during the stable operation. And each snapshot is regarded as…