Research on model and algorithm for two-echelon vehicle routing problem considering time-dependent road networks

For the urban vehicle distribution routing problem, most existing models fail to consider the adaptation of abstract path visit sequences to the real road network or lack a fine-grained microscopic path search mechanism. Algorithmic optimizations tend to emphasize full-period performance and lack targeted responsiveness to the dynamic characteristics of individual time periods. To address this, this study proposes a two-echelon routing planning model considering time-dependent road networks and a hierarchical solution strategy. Firstly, a two-echelon programming model aiming to minimize total distribution time is established: the upper echelon is a route selection model that determines the task visit sequence; the lower echelon is a time-dependent shortest path model, used to solve for the shortest travel routes between demand points within the actual road network. To solve this model, a hierarchical collaborative solution strategy is designed. The upper echelon employs an improved ant colony algorithm, whose core innovation lies in a dynamic pheromone update mechanism bound to time periods, ensuring pheromone accumulation and evaporation occur only within the same traffic state period, thereby enabling more precise learning of routing experience across different periods. The lower echelon utilizes the TD-Dijkstra algorithm to accurately calculate the actual shortest travel time between any two points given a specific departure time. Comparative experiments demonstrate that the proposed model and algorithm exhibit excellent performance in both solution accuracy and adaptability to dynamic environments. This provides a new and effective solution for dynamic routing within urban intelligent transportation systems.