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

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