Vehicle Routing Problem of Multi-trips for Perishable Product Delivery with Considering Individual Customer Satisfaction
With a rise in the perishable product e-commerce and upgrading of consumption,the volume of perish-able 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 distribu-tion.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 inquis-itive 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 transpor-tation 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 algo-rithm 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 compre-hensive 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 con-ducted 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.
国家科技期刊平台
NSTL
万方数据
