Rolling-Horizon Vehicle Routing for Dynamic Urban Distribution with Soft Time Windows: A Dynamic Adaptive Large Neighborhood Search Approach

Abstract

Urban distribution plans often have to be adjusted after vehicles leave the depot because new orders continue to arrive and some vehicles are still executing earlier routes. This creates a routing problem in which available information and vehicle states change over time. The problem considered here involves a single depot, vehicle-capacity limits, soft latest-service times, fixed committed routes, and limited order postponement. The study aims to improve route adjustment when only part of the order information is known at the beginning of the planning horizon. A rolling-horizon dynamic adaptive large neighborhood search method is developed for this setting. At each decision epoch, newly released orders are combined with unfinished orders from the previous epoch, and only vehicles that have returned to the depot are available for replanning. Orders are served whenever a feasible insertion exists; postponement is used only when no feasible insertion can be found. Three operators are added to the search process to account for order time pressure, insertion priority, and postponement history. Local search, adaptive operator weighting, and simulated-annealing acceptance are also used. The common search parameters are selected through an orthogonal experiment. The method is tested on dynamic Solomon RC101 instances with 40, 60, and 80 customers and is compared with five benchmark approaches. It obtains the best overall mean rank of 2.05. At 40 customers, it is not the best-performing method. At 60 and 80 customers, however, it gives the lowest mean objective values. For the 60-customer instances, the mean objective value is 1905.79, compared with 2047.52 for the standard rolling-horizon adaptive large neighborhood search method. The corresponding values for the 80-customer instances are 2326.43 and 2351.53. The proposed method also reaches 90% of its total improvement after 9.5% of normalized search progress, while the standard rolling-horizon method requires 26.0%. Its performance advantage becomes larger when a greater share of orders is released dynamically. The method is therefore more useful when route adjustment becomes more difficult, although its advantage is not consistent under every tested condition.