最大最小蚁群算法求解SDVRP和SDWVRP问题的研究

发布时间：2018-06-01 16:35

本文选题：可拆分 + 车辆路径问题　；参考：《东北大学》2014年硕士论文

【摘要】：当今经济快速的发展,企业为了获得更多的经济效益,已不仅仅局限于提供产品本身,同时开始着眼于利用附加服务来吸引更多的客户,在此背景下,物流配送服务大面积兴起。车辆路径问题作为物流配送的关键环节,是其重要的组成部分和研究方向。但是由于传统车辆路径问题约束了每个顾客点必须由一辆车进行服务,而在实际物流配送过程中为了节约成本,经常存在将一个顾客点的需求拆分由一辆以上的车辆进行服务的情况,这启发本文针对于可拆分的车辆路径问题(SDVRP)进行研究。与此同时,考虑到问题建模中忽略了货物重量对运送车辆数和总运输费用的影响,因此求得的最优路径可能并非实际车辆数和费用最少的路径。因此,我们又将车辆的载重量加入到目标中,提出了带货物权重的车辆路径问题(SDWVRP)。这里的货物权重是个广义的概念,不仅仅局限于货物载重量,还可以表示还可以代表运输过程中货物的优先程度,紧急程度,以及顾客点的优先级和重要程度。而相应的模型目标除了可以代表运输过程中的总费用,还可以作为运输过程中总碳排放量、易腐食品的损失量、危险品的风险值、物流运送效力、满意度值、顾客总旅行时间和顾客点的优先程度等。本文主要以物流配送问题为研究背景,具体研究工作包括：研究了SDVRP问题的背景和数学模型,设计了最大最小蚁群算法和禁忌搜索算法求解SDVRP司题,通过比较两算法的求解效果,证明对于SDVRP问题模型来说,最大最小蚁群算法求解效果较优,并在两算法求解结果的基础上,分析出使用可拆分模型比不使用可拆分模型可以获得更大的经济效益。实验数据选取于VRP BENCHMARK实例库中的实例,以地理位置分布类型和货物权重类型对实例进行划分,构成7种实例分布组合,通过对以上实例进行测试分析,我们考察了在何种地理位置分布和货物权重分布类型下,SDVRP建模效果更明显。并且,通过对MMAS算法参数进行全因子分析,得出了最适合求解SDVRP问题的算法参数。在SDVRP问题的基础上,将顾客点货物权重可能对路径规划产生的影响考虑到问题中,我们提出了SDWVRP问题模型,并且根据问题自身特点,设计出改进的最大最小蚁群算法用于求解SDWVRP问题。通过对SDWVRP模型与SDVRP模型的比较,讨论将货物权重考虑到问题求解中的必要性和可行性,指出对于不同类型实例来说,SDWVRP模型均有较好的表现。同时指出,在货物权重相差较大和地理位置较为分散时,考虑货物权重因素的建模效果更好。通过对SDWVRP模型与WVRP模型的比较,说明考虑拆分策略对问题求解的意义,经过对大量实例的测试分析,证明可拆分策略可以更明显的减少运输过程中使用的运输车辆数,进而降低运输总费用,减少企业总成本。综上,通过实验测试可以说明,考虑可拆分和货物权重的模型求解效果,会受到顾客点地理位置分布类型和权重分布类型的影响,特定的地理位置和权重分布组合可以得到更好的求解效果。
[Abstract]:With the rapid economic development today, in order to obtain more economic benefits, enterprises have not only limited the product itself, but also focus on the use of additional services to attract more customers. In this context, the logistics and distribution service has sprung up in a large area. Vehicle routing problem is the key link of logistics distribution, and it is an important part of its component part. But because of the traditional vehicle routing problem, each customer point must be served by a car, and in order to save the cost in the actual logistics distribution process, there is often a situation of splitting the demand of a customer point by more than one vehicle. This inspires this article for the disassembled vehicle road. At the same time, considering the effect of the weight of the goods on the number of vehicles and the total cost of transportation, the optimal path may not be the path to the actual number of vehicles and the least cost. Therefore, we add the vehicle's load to the target and propose a vehicle with the weight of the goods. The vehicle routing problem (SDWVRP). The weight of the goods here is a generalized concept, not limited to the weight of the cargo, but also represents the priority, the urgency, the priority and the importance of the customer's points in the transportation process, and the corresponding model targets can represent the total cost of the transport process, as well as the total cost of the transportation process. It can be used as the total carbon emissions in the process of transportation, the amount of perishable food, the risk value of dangerous goods, the effectiveness of logistics transportation, the value of satisfaction, the customer's total travel time and the priority of the customer points. This paper mainly takes the logistics distribution as the research background, and the specific research work includes the background and mathematical model of the SDVRP problem. The maximum minimum ant colony algorithm and tabu search algorithm are considered to solve the SDVRP problem. By comparing the results of the two algorithm, it is proved that the maximum minimum ant colony algorithm is better in solving the SDVRP problem model. On the basis of the results of the two algorithm, it is found that the use of the split model can be better than that without the use of the split model. The experimental data are selected in the example of the VRP BENCHMARK case base, the geographical location distribution type and the weight type of the goods are divided into 7 instances. By testing and analyzing the above examples, we examine the SDVRP modeling under the location distribution and the distribution of goods weight. The effect is more obvious. Furthermore, through the full factor analysis of the MMAS algorithm parameters, the most suitable algorithm parameters for solving the SDVRP problem are obtained. On the basis of the SDVRP problem, the effect of the possible weight of the customer point goods on the path planning is taken into consideration. The SDWVRP model is proposed and the design is designed according to the characteristics of the problem. The improved maximum and minimum ant colony algorithm is used to solve the SDWVRP problem. By comparing the SDWVRP model with the SDVRP model, the necessity and feasibility of taking the weight of the goods into consideration in the problem solving are discussed. It is pointed out that the SDWVRP model has better performance for different types of examples. By comparing the SDWVRP model with the WVRP model, it shows the significance of considering the dismantling strategy to solve the problem, and through a large number of examples, it is proved that the dismantling strategy can reduce the number of transportation vehicles used in the transport process, and then reduce the transportation. Overall cost, reduce the total cost of the enterprise. In summary, the experimental test can show that the effect of the model solving effect considering the disassembly and the weight of the goods will be influenced by the location distribution type and the weight distribution type of the customer point, and the specific geographical location and the weight distribution combination can get better results.
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：U116.2;F252

【参考文献】