关键词: 非对称网络, 容量约束, 在线算法, 即时取送货问题

Abstract: With the increasing scale and range of deliveries, riders have frequent traffic accidents. The complexity of the urban traffic network and the deviation of order capacity from the platform prediction force the riders to adopt non-standard loading methods such as mounted handlebars during peak hours, which significantly increases the risk of traffic accidents. Therefore, it is essential to consider capacity-constrained pickup and delivery strategies. So a real-time delivery route optimization problem with capacity constraints considering the characteristics of urban transportation networks is proposed. Firstly, the lower bound of the problem is demonstrated. Double judgment condition (DJC), judge path and load weighted (JPL) and wait and serve (W&S) strategies for specific and general networks are designed. And worst-case scenario analysis is used to prove the competitive ratios of these strategies. Finally, through case studies and analysis of the performance of the JPL and W&S strategies under different order densities, maximum asymmetry coefficients and order capacity demand ratios, the algorithms’ effectiveness is validated. The results indicate that the JPL strategy is highly applicable and performs best in urban traffic networks with higher order density, more large-capacity orders and smaller asymmetric coefficients. The W&S strategy is more suitable for asymmetric urban transportation networks with lower order density and significant capacity demand. The conclusion of the study provides a delivery strategy considering capacity constraints in different cases, and reduces the non-standard loading demand through real-time optimization of the path, ensuring the safe delivery of riders.

Key words: asymmetric network, capacity constraints, online algorithm, real-time pick-up and delivery problem