Abstract: With the rapid development of takeout industry, the time and scale of distribution are continuously improved, which makes the traffic violations such as retrograde motion and over speed increase sharply. The rapid development of takeout industry also makes takeout platforms and restaurateurs pay more and more attention to customer satisfaction, further reduces the distribution time which directly relates to customer satisfaction. O2O takeout platforms use the straight-line distance to estimate the delivery time, but the transportation network of urban business district actually has an asymmetric structure. Therefore, the distribution problem considering customer satisfaction and actual distribution network has become an important research problem of terminal real-time distribution. Based on the actual distribution network, the paper explores the optimization of real-time pick-up and delivery path considering customer satisfaction. In view of the real-time and difference of customers’ orders, distribution vehicles are required to adjust the distribution path and determine whether to return to the origin.
The real-time pick-up and delivery path optimization problem considering customer satisfaction is studied. Softtime window constraints are added to characterize customer satisfaction and a real-time pick-up and delivery path optimization model considering customer satisfaction is established. By defining and adjusting the asymmetric network coefficients, the asymmetric distribution network is constructed; the Ignore strategy and Real-time strategy are proposed. The Ignore strategy requires the deliveryman to ignore all new orders before returning to the distribution starting point. The Real-time strategy requires the deliveryman to judge in real-time whether to return to the starting point to pick up goods and re-plan the distribution route when new orders appear. Using the numerical simulation software and calling the genetic algorithm, the applicability of the two strategies is analyzed under different network sizes, rolling time domain duration, asymmetric coefficient, time windows and order quantity. The numerical example analysis shows that the Real-time strategy is more suitable for the case of larger network, while the Ignore strategy will be more suitable when the network is smaller and the number of orders is fewer. When the network is large, as the asymmetric coefficient increases, the number of times the cost mean of the Real-time strategy is lower than the cost mean of the Ignore strategy will gradually decrease. As the number of orders increases, the number of times the average cost of the Real-time strategy is lower than the average cost of the Ignore strategy will gradually increase. When the network is small, this trend will be exactly the opposite as the asymmetry coefficient and order quantity increase.Will the dynamic release characteristics of orders have a significant impact on actual delivery costs? Will the asymmetry of distribution networks, which has a significant impact on distribution costs, be considered? On the premise of not affecting customer purchasing behavior, different delivery times can be promised to customers when there are significant differences in order distribution.
This paper is based on asymmetric networks and studies the real-time pickup and delivery path optimization problem based on customer time windows. Online algorithms are designed and mathematical models are built to study the problem. In the future, further optimization of the research object and background can be achieved. The scenario considered in this article is bicycles, a single type of customer. Future research can classify customer types based on customer value or the value of delivered goods, and use multiple vehicles for delivery, making it more relevant to the real background. The setting of asymmetric network coefficients in the case analysis is too singular. In the future, random functions can be used to set different parameter value.

Key words: traveling salesman problem, combined shipping, real-time pick-up and delivery, unilateral soft time window, asymmetrical networks for different paths

摘要： 针对即时配送订单出现的动态性、服务客户的满意度、末端配送路网的非对称性,在配送订单的时间窗限制下,建立实时取送货路径优化模型。通过定义并调整非对称网络系数,构建非对称配送网络,提出滚动时域忽略策略(Ignore策略)和滚动时域实时判断策略(Real-time策略)。Ignore策略要求配送员一旦出发,返回配送起点前忽略所有新出现的订单,Real-time策略要求配送途中实时判断当新订单出现时,是否返回起点取货,重新规划配送路线。使用数值仿真软件,在不同非对称系数、客户时间窗、订单数量等的情形下分析策略适用性。数值算例分析表明,Real-time策略适用于网络较大的情形,而网络较小且订单数量较少时,Ignore策略更适用。研究结果可为城市末端合单配送和路径优化策略提供新的思路和参考。

关键词: 旅行商问题, 合单配送, 实时取送货, 单边软时间窗, 非对称网络