油耗最小化车辆路径问题：模型与算法

发布时间：2018-01-19 20:08

本文关键词： 燃油消耗车辆路径问题贪婪算法蚁群算法物流配送　出处：《青岛大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着世界经济全球化和一体化的发展,全球已进入信息化时代,然而工业社会给人们的生活环境带来的危害已经初露端倪,环境和气候问题严重威胁着地球上生物的生存和繁衍。特别是在全球电子商务迅猛发展的大背景下,物流行业倍受社会各阶层的重视,同时对物流配送提出了更高的要求,更加追求服务的质量,要求快速、准确、订单跟踪时时更新等,进而推动了物流的发展。针对物流配送业的油耗成本问题,以最小化燃油消耗为目标,在分析和比较了现有燃油消耗模型的基础上,以最新汽车理论能耗模型为基础,通过分析和简化部分车辆行驶参数,建立了相应的低燃油车辆路径问题模型(Low Fuel Capacitated Vehicle Routing Problem,LF-CVRP)。首先,考虑到蚁群算法在VRP领域中具有的各项优点,设计了以最小化油耗为目标的蚁群算法(Ant Colony Optimization-LF-CVRP,ACO-LF-CVRP),并选用27个具有能力约束的标准车辆路径问题算例进行仿真;其次,考虑到虽然蚁群算法计算结果比较准确,但是存在计算时间时间过长的缺点,不适于现代信息实时更新的要求,设计了以最小化油耗为贪心规则的贪婪算法(Greedy Optimization Algorithm,GOA-LF-CVRP),并与ACO-LF-CVRP仿真结果的计算速度、总距离、总油耗、使用车辆数等方面对GOA-LF-CVRP和ACO-LF-CVRP进行对比分析;最后,综合改进与分析了油耗模型及贪婪算法。说明LF-CVRP模型及GOA-LF-CVRP算法组成的求解策略,可以快捷、有效地计算油耗及配送路线,满足现代物流配送路线实时更新的要求,为物流配送业提供绿色的决策方案。
[Abstract]:With the development of globalization and integration of the world economy, the world has entered the information age. However, the harm brought by the industrial society to people's living environment has already begun to emerge. Environment and climate problems seriously threaten the survival and reproduction of organisms on the earth, especially in the context of the rapid development of global electronic commerce, the logistics industry has been attached great importance to by all levels of society. At the same time, the logistics delivery put forward higher requirements, more pursuit of service quality, demand for speed, accuracy, order tracking and updating, and so on, thus promoting the development of logistics. In order to minimize fuel consumption, based on the analysis and comparison of existing fuel consumption models, and based on the latest vehicle theoretical energy consumption model, some vehicle driving parameters are analyzed and simplified. The low Fuel Capacitated Vehicle Routing Problem is established. First of all, considering the advantages of ant colony algorithm in the field of VRP. Ant Colony Optimization-LF-CVRP (ACO-LF-CVRP) is designed to minimize fuel consumption. And 27 examples of standard vehicle routing problem with capacity constraints are selected for simulation. Secondly, considering that the result of ant colony algorithm is accurate, but the computation time is too long, it is not suitable for the requirement of real-time updating of modern information. A greedy Optimization algorithm named greedy Optimization algorithm (GOA-LF-CVRP) is designed. The GOA-LF-CVRP and ACO-LF-CVRP are compared with the results of ACO-LF-CVRP simulation in terms of calculation speed, total distance, total fuel consumption and the number of vehicles used. Finally, the oil consumption model and greedy algorithm are comprehensively improved and analyzed. It is shown that the solution strategy composed of LF-CVRP model and GOA-LF-CVRP algorithm is quick. It can effectively calculate fuel consumption and distribution route, meet the requirement of real-time updating of modern logistics distribution route, and provide a green decision scheme for logistics distribution industry.
【学位授予单位】：青岛大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：F252;TP18

【参考文献】