Research On Stochastic Vehicle Routing Problem With Split Delivery

Distribution is one of the key scientific issues in logistics,and it is a key problem in logistics management and service.With the intensification of the competition and the slowdown in economic growth,the business volume and the profit of distribution are both on a downward trend.These compel the companies to introduce new technologies for the vehicle scheduling and the distribution management to improve the operational efficiency,the customer satisfaction and the core competitiveness.The split delivery has received more attention during the past decade,in which some cusomers can be serviced by more than one vehicle to reduce the number of the vechicles used and the travel cost,and to improve the distribution efficiency.In practice,the location of the customers,the presence of the customers' demand,the demand of customers,and the travel time,the service time et.al.may be all uncertain.With the development of the computer technology and the communation technology,the research on the stochastic vehicle routing problem has received more attention.But research on the vehicle routing problem with split delivery and stochastic informations is scant,which is awaiting further ameliorations and modifications.Concerning on different stochastic elements,the SDVRP with stochastic customers,the SDVRP with stochastic demand,the SDVRP with stochastic travel and service time were reasrearched in this paper.Firstly,two different cases of the stochastic customers,the random presence of the customers' demand and the stochastic location of the customers,were analysed.For the first situation,the vectors of the presence of the customers' demand were introduced into the stochastic programming model with recourse.An adaptive large neighborhood search by considering the split delivery based on the recouse policy in which skipping the customers without demand was designed.We modified the split insertion operator,and carried out tests on the modified classical instances.The results showed that,in most of the instances,the cost of split delivery is lower than unsplit-delivery;and the number of the delivery customers were not affected by the ratio between the number of the stochastic customers and the number of all customers.For the second situation,a multi-objective model was formulated.An improved iterated local search by transforming four objectives to single objective which is a combination of the four onjectives was designed to solve the problem.The test results showed that the split delivery has an impact on the solutions and better solutions could obtain under split delivery.Secondly,two different models on the vehicle routing problem with split delivery and stochastic demands was formulated: the stochastic programming model with rescourse and the two level Markov Decision Process model.For the first model,an improved particle swarm optimization was designed.The coding and decoding process,the route split process were designed to tackle the problem in which some customers may appear more than once because of split delivery;the velocity updating and the position updating process were designed to tacle the different length of the swarm.The test results show that the splitPSO have good performance even though the computation efficiency is low.For the second model,a partially reoptimization policy based on the dynamic decomposition was used to solve the problem.The dynamic decomposition and served by another vehicle as the recourse policy used.The tests showed the feasibility and efficacy of the model and the algorithm.Thirdly,two stochastic programming models with recourse are formulated respectively for the vehicle routing problem with split delivery and stochastic travel time,and for the vehicle routing problem with split delivery,stochastic travel time and simultaneously pick-up and delivery.For the first problem,the waiting time under soft time windows was considered.An improved particle swarm optimization with an adaptive selection in the velocity updating process to tackle the different length of the velocity vectors and the position vectors was proposed.An improved path relinking process to replace the updating of the position to tackle the information loss during the transformation between the continuous space and the discrete space was used.The results showed that,the all-in cost increases and the splitted customers becomes more under the consideration of waiting time.The all-in cost decreases,the number of vehicle,and the rarion of the waiting time all decreases because of the split delivery.For the second problem,an improved iterated local search in which local search operators were modified for simultaneously pick-up and delivery was proposed.Better solutions were obtained because of the split delivery in most of the medium scale instances and large scale instances.With the level of stochastic factors getting higher,the value of the objective growed;but the number of split customers were not affected.Finally,based on the actual distributation problem,research on the split delivery vehicle routing problem with dynamic and stochastic travel time was conducted.In the light of the stochastic and dynamism of the problem,a Markov Dedision Process is formulated.The post decision policy based on the approximately dynamic programming were used to solve the problem.The results showed that the post-decision policy used in this paper made a balance between the efficiency and the computation burden,and that the cost with the split delivery was better than the ones without split delivery.