基于蚁群算法的城市物流配送路径优化问题的研究

【作者】 弓晋丽；

【导师】 陈焕江；

【作者基本信息】 长安大学 ， 载运工具运用工程， 2007， 硕士

【摘要】 为了实现物流在城市范围内的合理发展和物流中心的合理布局,形成高效、畅通、网络化的物流体系,许多城市已经开始进行城市物流系统规划。在城市物流系统过程中,物流配送网络优化是一个非常重要的环节。构建合理化的城市物流配送网络是现代城市物流系统的核心内容,不仅直接影响到物流系统能否良好运行,而且对城市交通运输系统、城市环境系统以及城市规划系统有重大影响。在物流配送网络优化问题中,需要决策的问题是如何寻找一组费用最小的车辆路线,将货物配送到每个客户手中,即车辆路径问题(VRP)。综合考虑实际中客户的时间要求后,就形成了带时间窗的车辆路径问题(VRPTW)。VRPTW的目标是实现在规定时间窗内以最小的成本为各个客户服务。蚁群算法(ACS)能够同时在多个区域和解空间中实现多样化搜寻,已被成功应用在多种类型的NP—hard问题的求解中,并获得了较好的效果。本文提出了一种综合2—opt和动态插入两种不同类型的区域化搜索方法进行最优解优化的改进蚁群算法,用来解决VRPTW问题,并通过56个Solomon问题进行了实例验证。计算结果表明改进的蚁群算法与其它文献中的算法相比具有优越性,同时也表明改进的算法优于原算法。更多还原

【Abstract】 Nowadays, logistics is becoming more and more important in economy. Many cities in our country have realized the importance of pushing the development of logistics properly and effectively. In order to realize the proper development in the city and overall arrangement in logistics center of logistics, many cities have made the logistics system layout of cities. This can lead to an effectively, unblocked and networked logistics system. In the course of establishing the system, logistics delivery is the core of the city logistics system, because it does not only have an large effect on if the system can be work well but also the transportation system of the city traffic, urban environment system and urban planning system.In the management of delivery, a problem needs being decided frequently is how to seek an most saving vehicle route and give the goods to every customer, which is called the VRP. When added the time facture, it will become the "The Vehicle Routing Problem with Time Windows (VRPTW)". The objective of VRPTW is to serve a set of customers within their predefined time windows at minimum cost. Ant Colony System algorithm (ACS) that is capable of searching multiple search areas simultaneously in the solution space is good in diversification. It has been successfully applied to many NP-hard problems. An improved Ant Colony System algorithm (IACS) with two different types of local search: 2-opt and insertion move is proposed in this paper. The algorithm has been tested on 56 Solomon benchmark problems. The results show that our IACS is competitive with other meta-heuristic approaches in the literature. The results also indicate that such an algorithm outperforms the original heuristic alone.更多还原