Large-scale Real-time Time-dependent Vehicle Routing Problem

Vehicle routing problem (VRP) is core of the optimization in logistics distribution, and it is a typical combinational optimization problem and NP-hard problem, also a well-known difficult problem in operations research. The problem considered in this paper is a pure pick-up or pure delivery vehicle routing problem with time windows in which we consider multiple vehicles with large scale customers, real-time service requests and time-dependent travel times between demand nodes.The purpose of this paper is to propose a new method based on variable neighborhood search (VNS) for solving the Real-time Time-dependent Vehicle Routing Problem (RT-TDVRP) with Time Windows. The problem is a pickup or delivery vehicle routing problem with time windows (VRPTW) in which we consider real-time service requests, time-dependent travel times between demand nodes and real-time vehicle control. Models based on time-dependent travel speed is adopted and applied in order to satisfy the FIFO rule. A global algorithm framework is designed to repeatedly update the schedule according to the dynamic information. As the core of the framework, the proposed VNS algorithm contains three neighborhood structures, with All-exchange and All-2-opt for shaking period and All-relocate for local search period. Computational results are presented for the 100 customer problem, showing that our approach is competitive and outperforms existing heuristics in the literature. Experiments with 1,000 customer problems also show that the proposed VNS heuristic is competitive for solving large scale RT-TDVRP.