Research For Split Delivery Vehicle Routing Problems Based On Ant Colony Algorithms

Nowadays,the rapid development of the world economy has greatly promoted the development of logistics and transportation.As an important part of the economy of various countries,the logistics industry has attracted people's attention.At present,the development level of logistics determines the development level of a country.It can improve a country's GDP and guide the development direction of national economy.Reducing transportation costs which is to make the shortest transportation path can effectively improve the efficiency of the logistics industry.The traditional vehicle routing problem(VRP)is to study the problem of transportation path minimization.Because it requires that each customer's demand must be delivered by one transport vehicle,when the demand of some customers is greater than the vehicle capacity,it will not meet the needs of all customers.In order to solve this problem,the relevant scholars began to consider to split customer's demand,and proposed the Split Delivery Vehicle Routing Problem(SDVRP).In the process of SDVRP research,it is found that the goods consumption during transit is not taken into account.Therefore,we add the route consumption to the constraint condition and put forward Split Delivery Vehicle Routing Problem with Goods Consumed during Transit(SDVRP-GCT).SDVRP-GCT can not only be applied to logistics distribution,but also to other problems in daily life.Based on the SDVRP problem,this paper analyzes the current research situation and short board of the traditional SDVRP problem,combines the SDVRP problem with the real world logistics scene,proposes a more realistic SDVRP-GCT problem,and designs three extended algorithms based on ant colony algorithm to solve SDVRP and SDVRP-GCT.The data sets used in this paper includes: SDVRPLIB datasets,largescale datasets in VRP web and tourism planning dataset collected in mathematical modeling website.Firstly,these three extended algorithms are applied to SDVRP,and the results of the three algorithms are compared with the optimal solutions provided by data sets.The results show that these three extended algorithms can improve the existing optimal solutions,which shows that these three extended algorithms proposed in this paper have good performance in solving SDVRP problems.Then,we assume that the commodity consumption of vehicles during transit is proportional to the path length.The SDVRP benchmark data sets is transformed into SDVRP-GCT data sets,and these three extended ant colony algorithms are applied to the transformed SDVRPGCT data sets.The experimental results show that our algorithms performed well in different types of data sets.In addition,we carry out experiments on four large-scale data sets in VRP web,and the experimental results show that our algorithms have good stability and still perform well when the nodes scale is large.Finally,these three extended ant colony algorithms is applied to the tourism route planning problem,which proves that the SDVRP-GCT problem has a wide range of application in real life.To sum up,the main research work of this paper includes: studying the background and model of SDVRP,putting forward and modeling SDVRP-GCT problem;extending three ant colony algorithms,which can solve SDVRP and SDVRP-GCT problem at the same time;designing experiments,which prove that the three extended ant colony algorithms in this paper can effectively solve SDVRP and SDVRP-GCT problem;finally,the living tourism planning problem is modeled as SDVRP-GCT problem,and solved by three extended algorithms proposed in this paper,which proves that this work has a wide application prospect in real life.