基于蚁群算法的车辆路径规划问题求解研究

发布时间：2018-02-17 03:52

本文关键词： 车辆路径规划蚁群算法自适应　出处：《吉林大学》2015年硕士论文　论文类型：学位论文

【摘要】：随着电子商务的发展，其便利快捷的购物特性，让越来越多的人们选择网上购物这种方式，电商在人们生活中占据越来越重要的位置。由于其远距离特性，因此需要物流行业在其中起着配送的作用。由于在物流业务中，快递普遍成本过高并且效率低下，因此提高运送效率和降低快递成本对于降低网购成本具有很大的现实意义，车辆路径规划问题（Vehicle Routing Problem，VRP）是公认的解决物流配送问题求解最低货物成本的理论模型。货物配送服务的关键是服务速度和质量，在一个给定的期间内，一组客户和一组车辆，这些车辆被分配到一个或更多集运点。通过对一个车队来进行约束操作并使用适当的公路网络，VRP问题的解被称为确定的一组路线，每个车辆的起点和终点都在自己的集运点。如此，，所有的客户都被满足，所有的操作约束都被满足，并且整体的运输费用最低。在过去的数十年中对快递优化方案正在逐渐增加，大量现实实例证实，使用大量的计算机程序应用于规划分配计划中，可以在整体运输成本中产生大量的节约（通常较不做规划节约5%-20%）。很容易看出来，这些节约在整体行业成本中是很重大的，事实上，运输过程包括生产和分配系统的全过程。并且运输成本也是最终成本的相关因素。车辆路径规划问题的研究可以减少很大一部分物流开销。到目前为止，出现了很多求解车辆路径问题的算法，有精确算法(accurate algorithm）和启发式算法(heuristicsalgorithms）。其中,精确算法用来求解问题最优解的方式是严格的数学方法，启发式算法则利用对状态空间的位置评价来找到较好的位置，再基于这个位置进行搜索，直到找到目标为止。随着问题规模不断地扩大，精确算法的计算量越来越大，还不能直接用来解决实际问题。启发式算法则可以根据不同的问题要求来求解问题。基于VRP问题的本质，不太可能使用精确的方法求解VRP的大规模的实例。因此，大部分方法都依赖于启发式方法来获取近似解。许多方法已经被用到了这个领域中，其中有选择使用标准优化技术的算法，例如，蚁群算法、遗传算法、模拟退火和约束编程。我们在这里关注于元启发式算法，主要是蚁群算法。蚁群算法是启发式算法中主流的一种算法。由Marco Dorigo于1992年受到蚂蚁觅食行为启发而提出，将其应用到了组合优化问题中。通过实验结果表明，蚁群算法可以找到相对较好的解，而且具有很强的鲁棒性。在本文中，我们基于已有的研究成果，将自适应思想与最大最小蚂蚁系统相结合。在每次搜索循环的过程中，我们可以自适应的决定精英蚂蚁的数量。只要在搜索的过程中，达到了一定的要求，我们就可以把它当作精英蚂蚁，将它的信息素保留下去。在更新一条路径上的信息素时，考虑两点之间的距离，而不是均匀的将信息素释放在路径在。提出奖励惩罚制度，将蚂蚁当前走过的路径与上一次的最优路径进行比较，对蚂蚁进行等级划分，将排名靠前的蚂蚁所在的路径上的信息素予以增强，排名靠后的蚂蚁所在的路径上的信息素予以减少。通常，可以寻找到较优解。
[Abstract]:With the development of electronic commerce, its convenient shopping, let more and more people choose online shopping this way, electricity providers occupy an increasingly important position in people's life. Because of the characteristics of long distance, so the logistics industry plays a role. The distribution in the logistics business, the high cost of universal express and low efficiency, so as to improve transport efficiency and reduce the cost for the express has great practical significance to reduce the cost of online shopping, vehicle routing problem (Vehicle Routing, Problem, VRP) is a theoretical model to solve the matter as flow distribution problem solving minimum cost of the goods and delivery of the goods. The key is the speed and quality of service, in a period given that a group of customers and vehicles, these vehicles are assigned to one or more cargo. According to a team of constraints and make the operation With the appropriate highway network, the solution of the VRP problem is called a group of routes to determine the starting point and end point of each vehicle in its own container. So, all customers are satisfied, all the operating constraints are satisfied, and the overall transportation cost minimum. In the past ten years the number of Express optimization scheme is increasing gradually, confirmed that a large number of practical examples, the use of computer programs in the application of planning and allocation plan, can produce a large number of savings in the overall transport costs (usually do not plan to save 5%-20%). It is easy to see that these savings are significant in the overall cost in the industry, in fact, the transport process include the whole process of production and distribution system. And the related factors of transportation cost and final cost.
Study of vehicle routing problem can be reduced to a large part of logistics cost. So far, there has been a lot of vehicle routing problem solving algorithm, accurate algorithm (accurate algorithm) and heuristic algorithm (heuristicsalgorithms). Among them, the exact algorithm to solve the problem of optimal solution is a rigorous mathematical method, the heuristic algorithm is the use of position the evaluation of state space to find a better position, then search based on this position, until you find the target so far. As the problem scale continues to expand, the exact algorithm of calculation is more and more big, also can not be directly used to solve practical problems. The heuristic algorithm can request to solve the problem according to different problems.
The essence of VRP problem based on the example of large scale are less likely to use the method to solve VRP accurately. Therefore, most methods rely on heuristic methods to obtain approximate solutions. Many methods have been used in this field, which have the option to use standard optimization algorithms, such as ant colony algorithm, genetic algorithm, simulation annealing and constraint programming. We focus on meta heuristic algorithm here is the ant colony algorithm. Ant colony algorithm is a heuristic algorithm of mainstream algorithm. By Marco Dorigo in 1992 was inspired by the foraging behavior of ants is proposed, its application to combinatorial optimization problems. The experimental results show that the ant colony algorithm can find the relative a better solution, but also has strong robustness.
In this paper, we based on the existing research achievements, the adaptive thought and max min ant system combined. In each cycle of search process, we can determine the number of adaptive elite ants. As long as in the search process, meet the certain requirements, we can regard it as the elite ants. It's keeping. The pheromone updates a pheromone path, considering the distance between two points, and not even the pheromone release in the path. In the proposed penalty system, the current through the ant path compared with the optimal path at a time, carry on the classification of ants, will on the path where the ranking of the ant pheromone on the path to be enhanced, ranked by the ant's pheromone on be reduced. Usually, you can find a better solution.

【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP18

【相似文献】