A Time Window Assignment Strategy for Dynamic Vehicle Routing Problem

The exponential growth of e-commerce has made it increasingly important for home delivery services to optimize the delivery experience for ultimate customer satisfaction. A key aspect of this optimization journey is negotiating and assigning delivery time windows between carriers and customers, particularly in the crucial last-mile delivery phase. Broader delivery windows allow carriers to accommodate flexibility in their operations, while customers tend to prefer narrower time frames to minimize waiting periods. In this paper, we address the challenge of Dynamic Vehicle Routing with Time Window Assignment (DVRPTW), which is a fundamental problem in modern logistics management. Our approach involves introducing a dynamic strategy for assigning time windows to customers, starting with providing ample time windows for established customers and then fine-tuning them in response to new orders and existing route constraints. We designed an insertion heuristic algorithm to both routing and assigning Time Windows to customers. The routing process is enhanced by combining the insertion heuristic with the Simulated annealing. We conduct experimental experiment in the Lackner’s benchmark to show the impact of TW width to the service level. The general trend confirms an intuition that large widths lead to greater service level. However, this is not the case for other instances. We are investigating possible reasons that lead to this unexpected result.