基于混合蟻群算法的船廢收運(yùn)路線優(yōu)化研究
發(fā)布時(shí)間：2018-08-31 15:33
【摘要】：近年來隨著船舶水運(yùn)事業(yè)快速發(fā)展在帶來巨大的經(jīng)濟(jì)效益的同時(shí),也帶來了嚴(yán)重的河流水域污染問題。本文針對(duì)船廢收集效率極低的現(xiàn)象,研究相關(guān)政策促使船廢全部上岸,采用環(huán)衛(wèi)車進(jìn)行陸運(yùn)收集至中轉(zhuǎn)站(車輛路徑問題),最終采用水運(yùn)由中轉(zhuǎn)站運(yùn)往老港等垃圾處理點(diǎn)。根據(jù)這一模式制定合理的船廢收運(yùn)路線,通過研究算法優(yōu)化模型,降低船廢收運(yùn)路線成本,實(shí)現(xiàn)改善環(huán)境和降低經(jīng)濟(jì)成本的目的。本文將解決車輛路徑問題(Vehicle Routing Problem,VRP)的前沿元啟發(fā)算法的優(yōu)缺點(diǎn)進(jìn)行對(duì)比分析,最終選取在解決組合優(yōu)化問題上有顯著優(yōu)勢(shì)的蟻群算法,來優(yōu)化環(huán)衛(wèi)車輛收運(yùn)船廢垃圾的路線。通過調(diào)查內(nèi)河船舶垃圾收運(yùn)現(xiàn)狀及參考國(guó)內(nèi)外大量文獻(xiàn)資料,并結(jié)合船廢垃圾特點(diǎn),建立不同約束條件下的三個(gè)收運(yùn)模型:有容量限制的車輛路徑問題,帶中轉(zhuǎn)的垃圾收集車輛路徑問題,帶時(shí)間窗的多車場(chǎng)多車型車輛路徑問題。采用混合蟻群算法進(jìn)行模型求解。具體工作如下:首先,采集船廢收運(yùn)系統(tǒng)中垃圾量與分布坐標(biāo),收集設(shè)施和中轉(zhuǎn)設(shè)施等基礎(chǔ)數(shù)據(jù)。通過船訊網(wǎng)對(duì)內(nèi)河船廢分布信息進(jìn)行采集;根據(jù)13條免費(fèi)收集航線垃圾收運(yùn)信息,采用Excel進(jìn)行處理預(yù)測(cè)各分布點(diǎn)的垃圾量。其次,對(duì)現(xiàn)有中轉(zhuǎn)站和環(huán)衛(wèi)車場(chǎng)車型等服務(wù)設(shè)施進(jìn)行調(diào)研,建立相應(yīng)的中轉(zhuǎn)站設(shè)施優(yōu)化模型,降低收運(yùn)成本。根據(jù)行政區(qū)域和水網(wǎng)密度情況,選取不同的運(yùn)輸模式,如陸上中轉(zhuǎn)運(yùn)輸模式、陸上直接運(yùn)輸模式或水陸集裝運(yùn)輸模式。再次,對(duì)蟻群算法進(jìn)行改進(jìn)研究,將其應(yīng)用在以上三個(gè)模型中,進(jìn)行收運(yùn)路線優(yōu)化。主要從以下四個(gè)方面進(jìn)行算法改進(jìn):(1)引入節(jié)約算子思想,平衡啟發(fā)算子,從全局考慮,避免局部最優(yōu)。(2)添加負(fù)反饋機(jī)制的局部信息素更新,擴(kuò)大搜索范圍;并采用正反饋機(jī)制的全局信息素更新方式,引導(dǎo)搜索方向。(3)為避免停滯,基于Ant-Q System和蟻群算法經(jīng)典收斂曲線,動(dòng)態(tài)調(diào)整參數(shù)設(shè)置,在搜索過程中動(dòng)態(tài)調(diào)整狀態(tài)轉(zhuǎn)移概率,達(dá)到確定性和隨機(jī)性選擇平衡,使得收斂方向正確的同時(shí),加快收斂速度。(4)結(jié)合軌跡式啟發(fā)算法——變鄰域搜索算法(Variable Neighborhood Search,VNS),來擴(kuò)大搜索范圍,提高解的穩(wěn)定性。為驗(yàn)證每一種改進(jìn)算法的有效性,本文采用國(guó)際上公認(rèn)的VRP問題庫典型案例(solomon’s instances)進(jìn)行仿真實(shí)驗(yàn)和分析。改進(jìn)后的蟻群算法,在規(guī)模相對(duì)不大的CVRP問題中具有良好的優(yōu)化效果和較強(qiáng)的魯棒性。對(duì)大規(guī)模的問題,采用Kmeans算法先聚類,后轉(zhuǎn)化為小規(guī)模問題,也取得了較好的效果。最后,本文根據(jù)上海市某區(qū)水域內(nèi)垃圾收集點(diǎn)的相關(guān)數(shù)據(jù),建立多車場(chǎng)多車型車輛路徑模型,通過改進(jìn)的蟻群算法進(jìn)行模型求解,得出上海市某區(qū)的船廢收運(yùn)環(huán)衛(wèi)車路線調(diào)度方案,實(shí)現(xiàn)經(jīng)濟(jì)效益和環(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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：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é)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：U698.7;TP18
【相似文獻(xiàn)】
相關(guān)期刊論文 前10條
1 鄧自立 ,周永聲;RS算法及其在管理工程中的應(yīng)用[J];華南工學(xué)院學(xué)報(bào);1984年03期
2 劉彩云;陳忠;;一種蟻群算法的并行實(shí)現(xiàn)[J];長(zhǎng)江大學(xué)學(xué)報(bào)(自科版)理工卷;2007年04期
3 楊康;沈術(shù)倫;楊瑛;;對(duì)通用最大熵譜分析算法程序的改進(jìn)[J];沈陽工業(yè)學(xué)院學(xué)報(bào);1993年01期
4 王一帆;劉士新;陳迪;;求解多技能人力資源約束的項(xiàng)目調(diào)度問題的兩階段算法[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年02期
5 殷劍宏;羅s，
本文編號(hào)：2215416
本文鏈接：http://www.sikaile.net/kejilunwen/daoluqiaoliang/2215416.html
最近更新
教材專著
