基于混合蚁群算法的船废收运路线优化研究
发布时间：2018-08-31 15:33
【摘要】：近年来随着船舶水运事业快速发展在带来巨大的经济效益的同时,也带来了严重的河流水域污染问题。本文针对船废收集效率极低的现象,研究相关政策促使船废全部上岸,采用环卫车进行陆运收集至中转站(车辆路径问题),最终采用水运由中转站运往老港等垃圾处理点。根据这一模式制定合理的船废收运路线,通过研究算法优化模型,降低船废收运路线成本,实现改善环境和降低经济成本的目的。本文将解决车辆路径问题(Vehicle Routing Problem,VRP)的前沿元启发算法的优缺点进行对比分析,最终选取在解决组合优化问题上有显著优势的蚁群算法,来优化环卫车辆收运船废垃圾的路线。通过调查内河船舶垃圾收运现状及参考国内外大量文献资料,并结合船废垃圾特点,建立不同约束条件下的三个收运模型:有容量限制的车辆路径问题,带中转的垃圾收集车辆路径问题,带时间窗的多车场多车型车辆路径问题。采用混合蚁群算法进行模型求解。具体工作如下:首先,采集船废收运系统中垃圾量与分布坐标,收集设施和中转设施等基础数据。通过船讯网对内河船废分布信息进行采集;根据13条免费收集航线垃圾收运信息,采用Excel进行处理预测各分布点的垃圾量。其次,对现有中转站和环卫车场车型等服务设施进行调研,建立相应的中转站设施优化模型,降低收运成本。根据行政区域和水网密度情况,选取不同的运输模式,如陆上中转运输模式、陆上直接运输模式或水陆集装运输模式。再次,对蚁群算法进行改进研究,将其应用在以上三个模型中,进行收运路线优化。主要从以下四个方面进行算法改进:(1)引入节约算子思想,平衡启发算子,从全局考虑,避免局部最优。(2)添加负反馈机制的局部信息素更新,扩大搜索范围;并采用正反馈机制的全局信息素更新方式,引导搜索方向。(3)为避免停滞,基于Ant-Q System和蚁群算法经典收敛曲线,动态调整参数设置,在搜索过程中动态调整状态转移概率,达到确定性和随机性选择平衡,使得收敛方向正确的同时,加快收敛速度。(4)结合轨迹式启发算法——变邻域搜索算法(Variable Neighborhood Search,VNS),来扩大搜索范围,提高解的稳定性。为验证每一种改进算法的有效性,本文采用国际上公认的VRP问题库典型案例(solomon’s instances)进行仿真实验和分析。改进后的蚁群算法,在规模相对不大的CVRP问题中具有良好的优化效果和较强的鲁棒性。对大规模的问题,采用Kmeans算法先聚类,后转化为小规模问题,也取得了较好的效果。最后,本文根据上海市某区水域内垃圾收集点的相关数据,建立多车场多车型车辆路径模型,通过改进的蚁群算法进行模型求解,得出上海市某区的船废收运环卫车路线调度方案,实现经济效益和环境效益。
[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.
【学位授予单位】：东华大学
【学位级别】：硕士
【学位授予年份】：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.
【学位授予单位】：东华大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U698.7;TP18
【相似文献】
相关期刊论文 前10条
1 邓自立 ,周永声;RS算法及其在管理工程中的应用[J];华南工学院学报;1984年03期
2 刘彩云;陈忠;;一种蚁群算法的并行实现[J];长江大学学报(自科版)理工卷;2007年04期
3 杨康;沈术伦;杨瑛;;对通用最大熵谱分析算法程序的改进[J];沈阳工业学院学报;1993年01期
4 王一帆;刘士新;陈迪;;求解多技能人力资源约束的项目调度问题的两阶段算法[J];东北大学学报(自然科学版);2014年02期
5 殷剑宏;罗s，
本文编号：2215416
本文链接：https://www.wllwen.com/kejilunwen/daoluqiaoliang/2215416.html
