Algorithm Design And System Implementation For Vehicle Scheduling Problem With Split Deliveryand Time Windows

At present,most of the research on vehicle routing problem is constrained by the fact that only one vehicle can be used to deliver the demand of each customer.However,in the actual vehicle scheduling of city distribution logistics,some customers' demands are great,city distribution logistics enterprises need to split the demands of these customers and deliver them by multiple vehicles.In addition,customers have constraints on the delivery time of vehicles,and there is little research on the split-delivery vehicle routing problem with time windows.Therefore,it is very necessary to build a model for this kind of vehicle routing problem,and to design an efficient optimization algorithm to solve the problem,so as to improve the service,reduce the cost of transportation and the manual scheduling time of the city distribution logistics enterprises,which is of great practical significance.According to the actual situation of vehicle scheduling in city distribution logistics,this thesis studies the split delivery vehicle scheduling problem with time windows,and designs the corresponding solution under two constraints: the time windows and the split-delivery constraints.A penalty function is designed for the time windows constraint.It will cause waiting cost if the vehicle arrives early,and it will reduce customers' satisfaction if the vehicle arrives late.Therefore,the penalty coefficient of arriving late is larger than the penalty coefficient of arriving ahead of time.A split strategy is designed for the constraint of split delivery.The customers whose demands are greater than that of the vehicle load have higher priority to be delivered by splitting.The customer demand which can be delivered by on vehicle can satisfy the the time window by default.Remaining customer demands cannot be delivered by one vehicle after splitting and need to meet the delivery time window requested by customer.A hybrid algorithm of genetic algorithm and ant colony algorithm is proposed.First,a set of better solution sets is obtained by genetic algorithm with global search ability.Then the solution set is taken as the initial solution set of ant colony algorithm.Then further optimization is made by ant colony algorithm with the strong global convergence ability.Finally,the optimal solution of the problem is obtained.According to the Solomon standard data,doing experiments by comparing the genetic algorithm with the ant colony algorithm,proves that the hybrid algorithm is superior in this thesis.In this thesis,a vehicle scheduling system of city distribution logistics is designed.This system uses the improved genetic algorithm proposed in this thesis to realize the vehicle scheduling and route planning.The functions of website are developed using front-end technology like ASP.NET,Html,Css and j Query.The data are saved in SQL Server 2008 database.The code on algorithm server are programmed using C#language.The driver-side APP functions are developed using Cordova and Vue.js.Theresult of vehicle route planning is showed using Gaode Map API.The website is mainly used to create customer order information.The order contains customer address,customer longitude and latitude,commodity demand,delivery time windows and so on.The website sends the order information to the algorithm server through Json data.After the calculation on algorithm server,the website can get the information about whether the order has been split,the vehicle to which the order is assigned and the order of the vehicle scheduling.After passing the result back to the website through Json data,the dispatcher on the website will confirm the result and assign the delivery task to the driver-side APP.The driver will deliver the demands to customers according to information of the delivery task on driver-side APP.