Research On Vehicle Routing Problem With Time Windows And Variable Adjustment Time

With the rise of e-commerce,logistics companies have exposed many deficiencies in dealing with vehicle routing problem.Most of the current vehicle routing problems are based on the minimum operating cost.When others deal with the time window,most of them use the measures to eliminate the cost of violating the time window.However,due to the asymmetry between the vehicle service time and the customer time window in the actual operation,the phenomenon of high customer complaints indicates that the penalty cost does not reflect customer satisfaction objectively.In the past,the scheduling situation does not consider the adjustment time generated by the adjustment work during the delivery process,so that it cannot be reflected.Therefore,the thesis proposes capacitated vehicle routing problem with time windows and variable adjustment time(CVRPTW-VAT).The main research contents are as follows:(1)In the actual working environment,the thesis considers the adjustment time caused by the vehicle in the process of routine maintenance,fuel replenishment,personnel retreat,etc.,the function between the adjustment time and the vehicle traveling distance is established.Meanwhile,the function between customer satisfaction and time window is established.The mathematical model of CVRPTW-VAT is established.The optimization goal is to minimize the vehicle traveling distance,maximize customer satisfaction,and minimize the number of vehicles,and the thesis aims to reduce the cost and ensure the service quality.(2)Scatter search(SS)algorithm for solving CVRPTW-VAT is designed,including the heuristic insertion algorithm based on vehicle capacity constraint and time window constraint to generate initial diverse solution,the elite selection and random selection to generate the reference set,the combination operator based on the arc combination algorithm,the repair operator based on the time window constraint,the heuristic algorithm based on the insertion of the best position as the improvement operator and the update reference set,etc.;Genetic algorithm(GA)is designed,including its combined crossover operator,mutation operator,etc.(3)The thesis uses SS algorithm to solve the capacitated vehicle routing problem(CVRP),the capacitated vehicle routing problem with time windows(CVRPTW),CVRPTW-VAT.In order to verify the feasibility of scheduling scheme of minimizing vehicle number,the scheduling scheme of constant vehicle number is established to compare with it,and then the experimental results are analyzed.The experimental results show that the SS algorithm solves the vehicle routing problem better than GA.