Optimization Research Of Ship Waste Collection And Transportation Route Based On Hybid Ant Colony Algorithm

In recent years,ship water carriage industry has been developing rapidly,which not only brings in enormous economic benefits,but alsoleads to serious river pollution problems.In view of the extremely low collection efficiency of ships waste,the thesis has researched relevant policies to promote all the waste will be put to the shore.The ship wastewere collected by sanitation trucks,then transported to the transfer station,finally ship waste were transported from transfer station to the waste disposal sites,for example Laogang.A reasonable route model of the ship waste collection and transportation was built according to this pattern,which was further optimizedby studying algorithm in order to reduce the cost of ship waste collectionand achieve the goal of improving the environment and reducing the economic cost.In this thesis,ant colony algorithm(ACA),which has signif icant advantages in solving combinatorial optimization problems,is selected to optimize the route of ship waste collection and transportation by comparing the merits and demerits of the frontier meta-heuristics algor ithms for solving vehicle routing problem.Based on the investigation of the current status of inland waterway waste collection and transportation,and with reference to a large number of literatures at home and abroad,three collection and transportation models under different constraints were established according to the characteristics of ship waste,namely,vehicle routing problem w ith limited capacity(CVRP),waste collection vehicle routing problem with intermediate facilities(WCVRP-IF),multi-depot heterogeneous vehicle routing problem with soft time windows(MDHVRPTW).Finally,the hybrid ant colony algorithmis adopted to solve the models.Main research work of the thesis is as follows.Firstly,basic data of the ship waste collection and transportation systemis collected,such as the amount of ship waste and distribution coordinates,collection facilities and transfer facilities and so on.The information of waste distribution of inland waterway is collected by ship information network,on the other hand,the amount of waste can be predictedby processing the informationof the 13 inland waterways for free collecting and transportating ship wastevia Excel.Secondly,survey the transfer stations and sanitation depots,vehicle types and other service facilities so far.According to this survey,the optimization model of transfer facilities is established in order to reduce the cost of collection and transportation.Different pattern,for example,the land transport transit,land transportation and land and water transport,can be selected according to the administrative area and density of rivers.Thirdly,the improvement of ant colony algorithm is researched,which is appliedto solve the above three models and optimize the routing.Four aspects of algorithm improvements are as follows.(1)The idea of economizing operator(C-W)is introduced,which can balance the heuristic operator and avoid local optimization from the overall consideration.(2)Add local pheromone update of the mechanism of negative feedbackto perform a deep exploration of the most promising regions of the solution space;and use global pheromone update mode of positive feedback mechanism to guide the right search direction.(3)In order to avoid stagnation,the selection strategy combining deterministic and stochastic selection is adopted to change the parameter setting according to Ant-Q System and the classical convergence curve of ant colony algorithm,and the state transition probability is dynamically adjusted during the searching process.(4)A novel tracking algorithm,variable neighborhood search algorithm(VNS),is used to extend the search range andimprove the stability of the solution.In order to verify the effectiveness of this algorithmimproved,the internationally recognized VRP problem library typical case(solomon’s instances)is used to carry out simulation experiment and analysis.The improved ant colony algorithm has good optimization effect and strong robustness in CVRP problem with relatively small scale.For the large-scale problem,the Kmeans algor ithm,which clusters firstly and converts to small-scale problems,also achieves good results.Finally,based on the data of the ship waste collection points in one District,this thesisestablishes the MDHVRPTW model,and solves the model by the improved ant colony algor ithm,and obtains the plan of the ship waste collection and transportation in this District,realizing the economic and environmental benefits.