Research on Urban Distribution Route Optimization Based on Time-Sliced OD Travel Time Matrices

Abstract

Urban distribution operations are significantly affected by time-varying traffic conditions. If Euclidean distance or static shortest paths are still used as the travel cost between nodes, the actual distribution process under real road network conditions cannot be accurately represented. To address this issue, this study investigates a vehicle routing problem with soft time windows based on time-sliced travel times derived from a real road network. Travel time data between nodes in the core urban area of Zhengzhou are collected through an open map platform, and the service period is divided into multiple consecutive time intervals to construct time-sliced OD travel time matrices with directional and temporal heterogeneity. On this basis, a time-dependent vehicle routing optimization model is established with the objective of minimizing total distribution cost, in which time window deviations are incorporated into the objective function as penalty costs. Considering that local route adjustments may lead to subsequent changes in time states, an improved adaptive large neighborhood search algorithm is designed, together with a local time update mechanism to reduce repeated computations. A distribution network with 69 nodes in an urban area of Zhengzhou is used as the test instance, and the proposed method is compared with a genetic algorithm, ant colony optimization, simulated annealing, tabu search, and adaptive large neighborhood search. The results show that the proposed method can effectively reflect travel cost differences across time periods and achieves a relatively balanced performance in both total distribution cost control and computational efficiency.