Vehicle Routing Problem with Pick-up and Delivery under Dynamic Travel Times

A two-stage method of optimization and adjustment was applied to solving vehicle routing problem with pick-up and delivery under dynamic travel times in an actual urban network. In optimization stage, according to the recurrent congestion information, a genetic algorithm was used to solve time-dependent vehicle routing problem with pick-up and delivery and arrange the initial delivery routes of vehicles. In adjustment stage, the link travel time is set as the time horizon and the rolling update was adopted to adjust delivery routes and avoid non-recurrent congestion. A series of mix-integer linear programming models were formulated for routing adjustment problem and a 2-opt algorithm hybrid with insertion algorithm was designed to solve the model. According to the shortest paths between customers derived from Dijkstra algorithm, the delivery routes are converted into the ones in an actual urban network. The numerical experiments show that in the rolling update, the time horizon of the link travel time can save 0.24–11.95 min in vehicle travel time compared with the time horizon of the travel time between customers; it can also save 0.08–8.06 min compared with the time horizon of the 24 min, and can decrease 10.02–34.59 in the number of updates compared with the time horizon of 6 min. Therefore, it is difficult to determine the optimal time horizon in the rolling update with a fixed horizon and thus it has a poor practicality. And the solving speed of 2-opt algorithm hybrid with insertion algorithm is 4 times the genetic algorithm.