基于混合蟻群算法的船廢收運路線優(yōu)化研究
發(fā)布時間：2018-08-31 15:33
【摘要】：近年來隨著船舶水運事業(yè)快速發(fā)展在帶來巨大的經(jīng)濟效益的同時,也帶來了嚴重的河流水域污染問題。本文針對船廢收集效率極低的現(xiàn)象,研究相關(guān)政策促使船廢全部上岸,采用環(huán)衛(wèi)車進行陸運收集至中轉(zhuǎn)站(車輛路徑問題),最終采用水運由中轉(zhuǎn)站運往老港等垃圾處理點。根據(jù)這一模式制定合理的船廢收運路線,通過研究算法優(yōu)化模型,降低船廢收運路線成本,實現(xiàn)改善環(huán)境和降低經(jīng)濟成本的目的。本文將解決車輛路徑問題(Vehicle Routing Problem,VRP)的前沿元啟發(fā)算法的優(yōu)缺點進行對比分析,最終選取在解決組合優(yōu)化問題上有顯著優(yōu)勢的蟻群算法,來優(yōu)化環(huán)衛(wèi)車輛收運船廢垃圾的路線。通過調(diào)查內(nèi)河船舶垃圾收運現(xiàn)狀及參考國內(nèi)外大量文獻資料,并結(jié)合船廢垃圾特點,建立不同約束條件下的三個收運模型:有容量限制的車輛路徑問題,帶中轉(zhuǎn)的垃圾收集車輛路徑問題,帶時間窗的多車場多車型車輛路徑問題。采用混合蟻群算法進行模型求解。具體工作如下:首先,采集船廢收運系統(tǒng)中垃圾量與分布坐標,收集設(shè)施和中轉(zhuǎn)設(shè)施等基礎(chǔ)數(shù)據(jù)。通過船訊網(wǎng)對內(nèi)河船廢分布信息進行采集;根據(jù)13條免費收集航線垃圾收運信息,采用Excel進行處理預(yù)測各分布點的垃圾量。其次,對現(xiàn)有中轉(zhuǎn)站和環(huán)衛(wèi)車場車型等服務(wù)設(shè)施進行調(diào)研,建立相應(yīng)的中轉(zhuǎn)站設(shè)施優(yōu)化模型,降低收運成本。根據(jù)行政區(qū)域和水網(wǎng)密度情況,選取不同的運輸模式,如陸上中轉(zhuǎn)運輸模式、陸上直接運輸模式或水陸集裝運輸模式。再次,對蟻群算法進行改進研究,將其應(yīng)用在以上三個模型中,進行收運路線優(yōu)化。主要從以下四個方面進行算法改進:(1)引入節(jié)約算子思想,平衡啟發(fā)算子,從全局考慮,避免局部最優(yōu)。(2)添加負反饋機制的局部信息素更新,擴大搜索范圍;并采用正反饋機制的全局信息素更新方式,引導(dǎo)搜索方向。(3)為避免停滯,基于Ant-Q System和蟻群算法經(jīng)典收斂曲線,動態(tài)調(diào)整參數(shù)設(shè)置,在搜索過程中動態(tài)調(diào)整狀態(tài)轉(zhuǎn)移概率,達到確定性和隨機性選擇平衡,使得收斂方向正確的同時,加快收斂速度。(4)結(jié)合軌跡式啟發(fā)算法——變鄰域搜索算法(Variable Neighborhood Search,VNS),來擴大搜索范圍,提高解的穩(wěn)定性。為驗證每一種改進算法的有效性,本文采用國際上公認的VRP問題庫典型案例(solomon’s instances)進行仿真實驗和分析。改進后的蟻群算法,在規(guī)模相對不大的CVRP問題中具有良好的優(yōu)化效果和較強的魯棒性。對大規(guī)模的問題,采用Kmeans算法先聚類,后轉(zhuǎn)化為小規(guī)模問題,也取得了較好的效果。最后,本文根據(jù)上海市某區(qū)水域內(nèi)垃圾收集點的相關(guān)數(shù)據(jù),建立多車場多車型車輛路徑模型,通過改進的蟻群算法進行模型求解,得出上海市某區(qū)的船廢收運環(huán)衛(wèi)車路線調(diào)度方案,實現(xiàn)經(jīng)濟效益和環(huán)境效益。
[Abstract]:In recent years, with the rapid development of shipping and waterway, it has brought great economic benefits, but also brought serious pollution problems of river waters. In view of the phenomenon of very low efficiency of ship waste collection, this paper studies the related policies that urge all shipwrecks to disembark, collect by land by using sanitation vehicles to transit station (vehicle routing problem), and finally use water transportation from transit station to waste disposal point such as old port. According to this model, the reasonable ship waste collection route is established, and the cost of the ship waste collection route is reduced by studying the optimization model of the algorithm, and the purpose of improving the environment and reducing the economic cost is achieved. In this paper, the advantages and disadvantages of the frontier meta-heuristic algorithm for solving the vehicle routing problem (Vehicle Routing Problem,VRP) are compared and analyzed. Finally, the ant colony algorithm, which has a significant advantage in solving the combinatorial optimization problem, is selected to optimize the route of collecting and transporting waste garbage from sanitation vehicles. By investigating the current situation of garbage collection and transportation of inland waterway ships and referring to a large number of documents at home and abroad and combining with the characteristics of ship waste garbage, three models of collection and transportation under different constraints are established: the vehicle routing problem with limited capacity. The problem of garbage collection vehicle routing with transit and multi-vehicle routing problem with time window. Hybrid ant colony algorithm is used to solve the model. The main work is as follows: firstly, the basic data of garbage quantity and distribution coordinates, facilities and transit facilities are collected. The information of inland river ship waste distribution is collected through ship communication network, and according to the garbage collection and transportation information of 13 free collection routes, Excel is used to deal with and predict the amount of garbage at each distribution point. Secondly, the existing service facilities such as transfer station and car sanitation yard are investigated, and the corresponding optimization model of transit station facilities is established to reduce the cost of collection and transportation. According to the density of administrative area and water network, different transport modes are selected, such as land transit mode, land direct transport mode or water and land container transport mode. Thirdly, the ant colony algorithm is improved and applied to the above three models to optimize the transportation route. The algorithm is improved from the following four aspects: (1) introducing the idea of economizing operator, balancing heuristic operator, and avoiding local optimum from the global perspective; (2) adding local pheromone updating of negative feedback mechanism to expand the search scope; And the global pheromone updating method of positive feedback mechanism is adopted to guide the search direction. (3) in order to avoid stagnation, based on the classical convergence curve of Ant-Q System and ant colony algorithm, the parameters are dynamically adjusted, and the state transition probability is dynamically adjusted during the search process. It achieves the balance of deterministic and random selection, makes the convergence direction correct, and accelerates the convergence speed. (4) combining the locus heuristic algorithm-variable neighborhood search algorithm (Variable Neighborhood Search,VNS), to expand the search range and improve the stability of the solution. In order to verify the effectiveness of each improved algorithm, (solomon's instances), a typical case of the internationally recognized VRP problem base, is used for simulation and analysis. The improved ant colony algorithm has good optimization effect and strong robustness in the relatively small scale CVRP problem. For large scale problems, Kmeans algorithm is used to cluster first, then to transform into small scale problems, and good results are obtained. Finally, based on the data of garbage collection points in a certain area of Shanghai, a multi-vehicle path model is established, and the model is solved by improved ant colony algorithm. The route scheduling scheme of ship waste collection and sanitation vehicle in a certain district of Shanghai is obtained, and the economic and environmental benefits are realized.
【學(xué)位授予單位】：東華大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：U698.7;TP18
[Abstract]:In recent years, with the rapid development of shipping and waterway, it has brought great economic benefits, but also brought serious pollution problems of river waters. In view of the phenomenon of very low efficiency of ship waste collection, this paper studies the related policies that urge all shipwrecks to disembark, collect by land by using sanitation vehicles to transit station (vehicle routing problem), and finally use water transportation from transit station to waste disposal point such as old port. According to this model, the reasonable ship waste collection route is established, and the cost of the ship waste collection route is reduced by studying the optimization model of the algorithm, and the purpose of improving the environment and reducing the economic cost is achieved. In this paper, the advantages and disadvantages of the frontier meta-heuristic algorithm for solving the vehicle routing problem (Vehicle Routing Problem,VRP) are compared and analyzed. Finally, the ant colony algorithm, which has a significant advantage in solving the combinatorial optimization problem, is selected to optimize the route of collecting and transporting waste garbage from sanitation vehicles. By investigating the current situation of garbage collection and transportation of inland waterway ships and referring to a large number of documents at home and abroad and combining with the characteristics of ship waste garbage, three models of collection and transportation under different constraints are established: the vehicle routing problem with limited capacity. The problem of garbage collection vehicle routing with transit and multi-vehicle routing problem with time window. Hybrid ant colony algorithm is used to solve the model. The main work is as follows: firstly, the basic data of garbage quantity and distribution coordinates, facilities and transit facilities are collected. The information of inland river ship waste distribution is collected through ship communication network, and according to the garbage collection and transportation information of 13 free collection routes, Excel is used to deal with and predict the amount of garbage at each distribution point. Secondly, the existing service facilities such as transfer station and car sanitation yard are investigated, and the corresponding optimization model of transit station facilities is established to reduce the cost of collection and transportation. According to the density of administrative area and water network, different transport modes are selected, such as land transit mode, land direct transport mode or water and land container transport mode. Thirdly, the ant colony algorithm is improved and applied to the above three models to optimize the transportation route. The algorithm is improved from the following four aspects: (1) introducing the idea of economizing operator, balancing heuristic operator, and avoiding local optimum from the global perspective; (2) adding local pheromone updating of negative feedback mechanism to expand the search scope; And the global pheromone updating method of positive feedback mechanism is adopted to guide the search direction. (3) in order to avoid stagnation, based on the classical convergence curve of Ant-Q System and ant colony algorithm, the parameters are dynamically adjusted, and the state transition probability is dynamically adjusted during the search process. It achieves the balance of deterministic and random selection, makes the convergence direction correct, and accelerates the convergence speed. (4) combining the locus heuristic algorithm-variable neighborhood search algorithm (Variable Neighborhood Search,VNS), to expand the search range and improve the stability of the solution. In order to verify the effectiveness of each improved algorithm, (solomon's instances), a typical case of the internationally recognized VRP problem base, is used for simulation and analysis. The improved ant colony algorithm has good optimization effect and strong robustness in the relatively small scale CVRP problem. For large scale problems, Kmeans algorithm is used to cluster first, then to transform into small scale problems, and good results are obtained. Finally, based on the data of garbage collection points in a certain area of Shanghai, a multi-vehicle path model is established, and the model is solved by improved ant colony algorithm. The route scheduling scheme of ship waste collection and sanitation vehicle in a certain district of Shanghai is obtained, and the economic and environmental benefits are realized.
【學(xué)位授予單位】：東華大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：U698.7;TP18
【相似文獻】
相關(guān)期刊論文 前10條
1 鄧自立 ,周永聲;RS算法及其在管理工程中的應(yīng)用[J];華南工學(xué)院學(xué)報;1984年03期
2 劉彩云;陳忠;;一種蟻群算法的并行實現(xiàn)[J];長江大學(xué)學(xué)報(自科版)理工卷;2007年04期
3 楊康;沈術(shù)倫;楊瑛;;對通用最大熵譜分析算法程序的改進[J];沈陽工業(yè)學(xué)院學(xué)報;1993年01期
4 王一帆;劉士新;陳迪;;求解多技能人力資源約束的項目調(diào)度問題的兩階段算法[J];東北大學(xué)學(xué)報(自然科學(xué)版);2014年02期
5 殷劍宏;羅s，
本文編號：2215416
本文鏈接：http://sikaile.net/kejilunwen/daoluqiaoliang/2215416.html
