Abstract: With the changing consumer attitudes of residents and the popularization of online shopping, the express industry has achieved vigorous development, and its business volume continues to rise. In the process of express service, the company not only dispatches trucks to deliver goods to specific demand points, but also undertakes the collection of goods awaiting retrieval. The quantity and variety of goods awaiting retrieval at each demand point vary. Besides, consumers may issue new retrieval orders or cancel existing ones during the process of delivery and pickup, resulting in an inability to accurately anticipate of the quantity of goods awaiting retrieval at each demand point before the truck reaches it. The research on vehicle routing problem with simultaneous delivery and pickup (VRPSDP) mainly focuses on two scenarios: demands are completely known and randomized. There is comparatively less research in the scenario of unpredictable demands, and multiple types of goods has not been considered. To address the above gaps, this study explores the VRPSDP-2 types of goods awaiting retrieval with different importance and unpredictable quantity (VRPSDP-2TDUQ). This investigation holds significant implications for enhancing the efficiency of delivery and pickup operations for express companies.
In VRPSDP-2TDUQ, the quantities of goods awaiting retrieval at each demand point is unpredictable and appear sequentially, which necessitates real-time decision-making with each decision affecting the subsequent steps in the entire process. The uncertainty of demand information and the sequential nature of decisions indicate that this problem is an online problem, which can be addressed through developing an online strategy. Based on the theory and method of online problems and competitive strategies, this paper develops an online strategy denoted as Strategy T to address VRPSDP-2TDUQ by maximizing the total importance of retrieved goods as much as possible with the characteristics of two types of goods with unpredictable quantities to be retrieved. Based on the principle that when the truck arrives at a particular demand point it should have the maximum possible space to accommodate a greater quantity of goods, in Strategy T the service sequence is determined before the truck departs following the principle of prioritizing demand points with larger delivery demand and subsequently smaller delivery demand. When the truck reaches any demand point, real-time decisions are made on how to retrieve two types of goods, with an emphasis on retrieving as many units of the higher-importance goods as possible.
The competition ratio of Strategy T is analyzed, and the impact of parameter variations on the competition ratio is discussed. The results indicate that the smaller the difference in importance between two types of goods, the greater the number of demand points and the larger the cargo lower limit for the lower-importance goods, the better the performance of Strategy T. Strategy T is subsequently validated by using a road network of 30 express delivery sites in Xi’an city, and the results suggest that the execution performance of Strategy T is relatively good. A further analysis of the variation in the ratio of unit importance ratio between two types of goods reveals that as the ratio decreases, the total importance of retrieved goods diminishes. However, the competition ratio decreases simultaneously, which means the deviation between the online solution and the offline optimal solution decreases. This aligns with the conclusions drawn from a theoretical analysis.
Future research can be approached from the following three aspects: First, this study focuses on the scenario where the quantities of two types of goods awaiting retrieval are unpredictable, and suggests the exploration of scenario where the quantities of more than two types of goods are unpredictable is worthwhile. Second, this study has not yet considered the scenario where the quantities of goods are partially known. Further research is required to address this scenario. Third, designing strategies with better competitiveness ratios is also a direction for future research.

Key words: unpredictable quantity to be retrieved, two types of goods, different importance, VRPSDP, online strategy

摘要： 不确定环境下的同时取送货问题难于解决,本文研究重要度不同且待取回数量无法预知的两种货物同时取送货车辆路径问题,目标是取回货物的总重要度尽可能大。首先界定问题并建立数学模型,并针对两种货物待取回数量均无法预知的特征设计在线策略T。策略T先确定货车的送货次序,在货车到达需求点后再确定如何取回A和B两种单位重要度不同的货物。其次分析策略T的竞争比,并讨论参数变化对竞争比的影响。结果表明,两种货物的单位重要度差异越小、需求点个数越多、单位重要度较小货物的载货下限越大,策略T的执行效果越好。最后通过实例对策略T进行验证,研究成果可为决策者在不确定环境下决策车辆路径和取送货方案提供支持。

关键词: 待取回数量无法预知, 两种货物, 重要度不同, VRPSDP, 在线策略