Research On The Split Delivery Vehicle Routing Problem With Customer Satisfaction

In the growing trend of urban distribution demand which has the feature of "small batch,multi-batch,high-efficiency",the split delivery vehicle routing problem(SDVRP)has gradually increased more application in reality,owing to its advantages such as better reducing transportation costs,reducing the vehicles used,and effectively reducing traffic congestion and environmental pollution to a certain extent compared with the traditional vehicle routing optimization,which making SDVRP and its expansion issues become one of the research hotspots of vehicle routing problem.At present,the mathematical modeling of the traditional split delivery vehicle routing problem is generally based on the assumption that customer’s demand can be split arbitrarily and infinitely,which ignores the differences in actual willingness of different customers for split delivery,and not consider the inconvenient impact of each split on customer’s receiving goods,as well as what measures should be taken to alleviate the dissatisfaction caused by the inconvenience.What’s more,it’s only an approximate ideal description of the actual problem,so the result obtained is likely to deviate greatly from the actual wishes of customers,and even lead to customer churn,resulting in a contradiction with the logistics distribution enterprises’ pursuit to reduce cost.In order to make the split delivery vehicle routing problem more suitable for practical application,the customer’s willingness for split delivery should be grasped as fully as possible before carrying out the SDVRP research.Inspired by this,this thesis proposes a research on the split delivery vehicle routing problem which takes into account customer satisfaction(SDVRP-CS).First,based on a review of literature research on SDVRP and customer satisfaction both at domestic and abroad,and a detail introduction to the relevant theories of SDVRP and customer satisfaction,the main factors affecting customer satisfaction in SDVRP are analyzed,and the corresponding quantitative methods are put forward.Next,the SDVRP-CS model with stochastic customers who are willing to split delivery(Model Ⅰ),in which the minimum total distribution cost as objective function,is established through introducing customer’s split compensation cost and willing to split delivery into the traditional SDVRP;the SDVRP-CS model with a limited number of split delivery(Model Ⅱ),aiming to minimize the total distribution cost,is established through adding customer’s split compensation cost and the acceptable maximum number of split delivery into the traditional SDVRP.Combining the former two models with a new hybrid time windows introduced,the SDVRP-CS model with new hybrid time windows(Model Ⅲ)is established,with the maximum average customer time satisfaction and the minimum total distribution cost as the dual-objective function.Then,according to the characteristics of these models,the corresponding improved tabu search algorithm are designed to solve them.Finally,based on the well-known Solomon benchmark instance set and combining the characteristics of the model,four types of R,RC,C1,and C2 instances with different customer locations from Solomon instance set are chosen to generate the Model Ⅰand Model Ⅱtest examples by adjusting the customers’ demands and some other modifications;Solomon R109 instance,in which customer location is in random uniform distribution,is selected to generate the Model Ⅲ test example by some specific designs.Experiments on these test examples are conducted on MATLAB software with the help of corresponding algorithm,these experiments mainly studying the influence that the changes of some factors(such as the proportion of stochastic customers,the limited number of split delivery,and split compensation cost,etc.)bring to the results,and analyzing the advantages and disadvantages of each model compared to the traditional VRP and SDVRP model.The results show that the SDVRP-CS model in this thesis can not only achieve lower total distribution costs than the traditional VRP,but also better guarantee or improve customer satisfaction than the traditional SDVRP,and the solving algorithm has good robustness and convergence.To be specific,Model Ⅰexperiment concludes that when the proportion of stochastic customers reaches 20%,the cost savings of model compared to the traditional VRP can reach nearly half of that when it reaches 100%;Model Ⅱexperiment shows that when the acceptable maximum number of split delivery is limited to 1,the cost saving effect of model compared to the traditional VRP can reach nearly 80% or above of that when there is no limit;Model Ⅲ experiment shows that when the split compensation cost exceeds 30% of the fixed cost of using a vehicle,the optimal planning scheme will give up the split delivery for customer demand.On the basis of these experiment results,some useful insights are drawn for logistics distribution enterprises to develop the split delivery routing vehicle routing problem in reality.