一种应用于物料配送路径选择的改进CW算法

发布时间：2018-02-08 14:33

本文关键词： 节约算法带时间窗的车辆路径问题分割配送蜂群优化算法层次分析法　出处：《吉林大学》2017年硕士论文　论文类型：学位论文

【摘要】：21世纪初,物流产业成为推动经济全球化的重要服务行业。在国民经济水平的快速发展和宏观调控的逐步改善下,中国的物流市场需求逐渐增加,产业水平保持较快发展。但中国物流产业的总成本仍是居高不下,根据《全国物流运行情况通报》得知,2014年社会物流总费用是10.6万亿元,2015年达到了10.8万亿元,而2016年1-11月的总费用为9.6万亿元。由此可见,物流行业的配送成本仍然过高。因此,减少物流产业的配送成本问题尤为重要。1959年,由Ramser和Dantzig提出的车辆路径问题(Vehicle Routing Problem,简称VRP),一直是业内研究的热点领域问题,其目标是尽可能减少路径配送成本,得到最优路径。根据各类约束条件可将VRP问题进行分类,如带车辆容积约束的VRP问题,带时间窗约束的VRP问题,单车场或多车场的VRP问题等。而本文主要针对带时间窗的车辆路径问题(With Time Windows Vehicle Routing Problem,简称VRPTW)求解物流行业中可供选择的最优路径。现如今,解决VRPTW问题的算法也数不胜数,主要基于两个方面的算法:精确算法和启发式算法。本文在经典启发式算法节约算法(CW算法)的基础上进一步做出改进,在硬时间窗约束的条件下,加入分割配送思想,不仅提高了算法的精确度和可行性,减少了配送总运输成本,还增加了车辆的载重率,提高了算法针对VRPTW问题的实效性。本文针对VRPTW问题,在原有CW算法中加入时间约束,使配送车辆必须在固定时间范围内送达货物,否则客户拒绝接收货物,即在CW算法中不仅对车辆载重控制,又添加了对时间的控制,多角度地接近现实问题。为将分割配送应用到CW算法中,文中定义了分割配送反应值这一概念,而为求解该反应值,本文介绍了蜂群优化算法(Bee Colony Optimization Algorithm,简称BCO),该算法中提到了货物对车辆的刺激值,该刺激值与车辆的运输里程c和运输时间t成正比,而运输里程和运输时间两种影响因素对问题结果存在一定的间接影响,因此采用层次分析法(Analytic Hierarchy Process,简称AHP)求出两种影响因素的权重,并作为因子a和b左右其影响程度。将以上思路结合在一起,得到分割配送反应值的计算公式H=△L/c~at~b(△L为CW算法中的节约值),从而按照反应值H从大到小的顺序决定哪个客户需求优先被分割,再结合原有CW算法的解题步骤,得到VRPTW的最优解。为验证本文提出的改进CW算法的可行性和实用性,将改进CW算法应用到具体实例中,得到了问题的满意解。同时与经典CW算法对比分析,得知改进后算法的精确度更高,实用性更强,车辆装载率更大。又进一步与其他学者的改进CW算法对比分析,得出本算法更适用于配送中心固定成本高于行驶成本的硬时间窗约束的VRP问题。
[Abstract]:In 21th century, logistics industry became an important service industry to promote economic globalization. With the rapid development of national economy and the gradual improvement of macro-control, the demand of logistics market in China gradually increased. However, the total cost of China's logistics industry is still high. According to the National Logistics Operation Bulletin, the total cost of social logistics was 10.6 tillion yuan in 2014 and 10.8 tillion yuan in 2015. From 2016 to November, the total cost was 9.6 tillion yuan. Thus, the cost of distribution in the logistics industry is still too high. Therefore, it is particularly important to reduce the cost of distribution in the logistics industry. The vehicle Routing problem proposed by Ramser and Dantzig has always been a hot topic in the field of research. Its goal is to reduce the cost of routing distribution as much as possible and to obtain the optimal route. According to various constraints, the VRP problem can be classified. For example, VRP problem with vehicle volume constraint, VRP problem with time window constraint, In this paper, the problem of vehicle routing with Time Windows Vehicle Routing problem is mainly used to solve the optimal path in logistics industry. Nowadays, there are too many algorithms to solve the problem of VRPTW. Based on two main algorithms: precise algorithm and heuristic algorithm. This paper further improves the classical heuristic algorithm based on the saving algorithm (CW algorithm), and adds the idea of segmentation and distribution under the condition of hard time window constraint. It not only improves the accuracy and feasibility of the algorithm, reduces the total transportation cost of distribution, but also increases the load rate of the vehicle, and improves the effectiveness of the algorithm for the VRPTW problem. In this paper, time constraints are added to the original CW algorithm for the VRPTW problem. The delivery vehicle must deliver the goods within a fixed time range, otherwise the customer refuses to receive the goods, that is, in the CW algorithm, not only the vehicle load control, but also the time control is added. In order to apply partitioned distribution to CW algorithm, the concept of split distribution response value is defined, and the response value is solved. In this paper, bee Colony Optimization algorithm is introduced. In this algorithm, the stimulation value of cargo to vehicle is mentioned, which is directly proportional to the transportation mileage c and the transport time t of the vehicle. The influence factors of transportation mileage and transportation time have some indirect influence on the result of the problem, so Analytic Hierarchy process (AHPP) is used to calculate the weight of the two factors. And as a factor a and b about its influence degree. The formula for calculating the response value of the partition distribution is obtained, H = L / C / C / T / B (L is the saving value in the CW algorithm), and then according to the order of the response value H from large to small to determine which customer needs to be partitioned first, and then combine the solution steps of the original CW algorithm. In order to verify the feasibility and practicability of the improved CW algorithm proposed in this paper, the improved CW algorithm is applied to a concrete example and the satisfactory solution of the problem is obtained. At the same time, it is compared with the classical CW algorithm. It is known that the improved algorithm has higher accuracy, better practicability and higher vehicle loading rate. Furthermore, it is compared with the improved CW algorithm proposed by other scholars. It is concluded that this algorithm is more suitable for the VRP problem with fixed cost higher than driving cost in distribution center.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：F259.2;TP18

【相似文献】