Abstract: With a rise in the perishable product e-commerce and upgrading of consumption, the volume of perishable product road traffic is increasing constantly, and its delivery tasks are becoming more and more complex. The distribution of perishable products is the process of delivering certain quantities of perishables from a number of suppliers to the corresponding receivers according to their orders. The Vehicle Routing Problem (VRP) is a key part of distribution activity and VRP for perishable products incorporates real-life complexities, which tackles VRP for products that have fixed or loose shelf lives. Compared with non-perishable goods distribution, it is a challenging task because preserving the nutrition value and freshness of perishables during transport is tough. Both the producers and distributors are suffering from substantial losses of perishable goods caused by distribution. Even if we keep perishables under perfect transportation conditions they will deteriorate over time, with obvious potential negative impacts on economy and environment. Moreover, consumers have become more inquisitive and there is growing concern over the quality of perishable products. Combined with the reality that the particularity of perishable products and the gradual higher requirements for product quality from consumers, the transportation activity of perishables should not be limited to the traditional economic way. Improving customer satisfaction is becoming an important goal of perishable product delivery. In the industries, companies nowadays are attaching more importance to customers’ opinion and they are making efforts to prevent the perishables from deteriorating and offer fresher and safer products as much as possible by flexible service. The increasing demand for perishable products and the limited transportation capacity of companies have led to multi-trip deliveries. Faced with this situation, companies need to plan effective multi-trip delivery routes to meet customer demands, achieve cost reduction and improve efficiency in perishable product delivery.
This paper considers a perishable product supplier with distribution autonomy, aiming at minimizing the vehicle transportation cost and minimizing the maximum perishable product circulation time of each individual customer during the whole planning horizon, which is directly related to the customer satisfaction. The transportation activity is planned in a whole planning horizon containing multiple trips for each operating vehicle, of which the time duration of the planning horizon represents the limit working duration. The latest delivery time specified by each customer is considered and the order packaging is also merged in the optimization problem. Therefore, a bi-objective vehicle routing model for perishable products with time windows and limit working duration is developed. To solve the problem, the bi-objective optimization problem is transformed into a series of single-objective optimization problems by the ε-constraint method first and then a two-stage meta-heuristic algorithm combining variable neighborhood search (VNS) and simulated annealing (SA) is constructed. Three improvement measures are proposed, including obtaining the strict lower bound simply by a property, reducing the search space during the solving process and avoiding dominated solutions by post-processing procedure. In summary, this study differs from previous studies in the following four distinct ways: (1)The bi-objective model for vehicle routing problem of multi-trips with time windows is introduced into the optimization of perishable product distribution. (2)This paper considers the packaging time, and the decision variables are more comprehensive and detailed, avoiding unnecessary waste caused by premature packaging of perishable products. (3)This paper considers customer satisfaction from the individual perspective. (4)A meta-heuristic algorithm based on ε-constraint method is designed to solve the problem, and some improvement strategies are proposed.
Finally, a series of computational results validate the validity and effectiveness of the model and algorithm. The numerical results obtained by GUROBI and the proposed algorithm are compared by four indexes including the number of solutions covered, the number of optimal solutions covered, the mean deviation between the values of two objectives and the optimal solutions, which proves the effectiveness of the algorithm. In addition, the numerical results suggest that the post-processing method we propose help avoid the dominated solutions and help improve the customer satisfaction. The Pareto frontier obtained reflects the trade-off between transportation cost and customer satisfaction. Furthermore, a sensitivity analysis under different customer density scenarios is conducted and some managerial insights are derived. The customer satisfaction is higher with low-density customer for the same number of vehicle trips and the larger the number of the trips the higher the customer satisfaction. It also shows that there will be a variety of delivery plans when the number of vehicle trips remains the same. Decision-makers can make the best choice based on the desired level of customer satisfaction to be achieved in a real-world scenario to achieve better management.
In future work, several directions can extend our study. Real-time traffic conditions can be considered in the mathematical model. Although split deliveries are not allowed in this paper, VRP with customers allowing split deliveries is a worthy extension. Finally, developing more effective solution approaches is also important.

Key words: individual customer satisfaction, perishable products delivery, vehicle routing problem, bi-objective optimization, ε-constraint method

摘要： 随着生鲜电商的兴起,生鲜品的道路运输量越来越大,其配送任务越来越复杂,提升客户满意度是生鲜品配送的重要目标组成。文章以一个具有配送自主权的生鲜品供应商为研究对象,以整个计划周期内生鲜品配送的车辆运输成本最小及客户满意度最大为双目标,且客户满意度从顾客的个体视角考虑,构建双目标多车程带时间窗及考虑订单打包时间的车辆路径优化模型。基于ε-约束方法,设计了两阶段变邻域搜索(VNS)和模拟退火(SA)相结合的元启发式算法,基于车辆构造初始路线,并针对性地提出了3点改进措施,包括通过数学性质推导下界、减少求解过程中不必要的搜索空间以及规避求解过程中被支配解的后优化处理。最后,以Solomon标准算例为基础构造算例对所设计的算法进行了计算实验,其求解结果表明:其设计的算法具有有效性,并通过敏感性分析得出相关管理启示。

关键词: 个体客户满意度, 生鲜品配送, 车辆路径问题, 双目标优化, ε-约束法