故障车辆救援中的多场站点弧混合路线问题研究

发布时间：2018-06-10 06:15

本文选题：车辆救援 + 弧路线问题　；参考：《南京农业大学》2015年硕士论文

【摘要】：在已有带容量荷载的弧路线问题中,车辆从场站出发,按照一定的行驶规则,服务所有的客户,最终回到场站。而在以故障车辆救援为(Rescue ofbreakdown vehicles,RBV)背景的研究中,共有两类客户,分别为点客户(Node Customer)和弧客户(Arc Customer)。其中点客户仅需要送油、送电等不需要移动故障车辆的服务;弧客户则需要救援车辆将故障车辆从故障现场拖至相应维修点的服务,并且每位客户拥有各自的响应时间要求。本文在这样的背景下,提出了一种故障车辆救援中的多场站点弧混合路线问题(Multi-depot arc-node routing problem in the rescue of breakdown vehicles,MDANRPRBV)。在此问题中,车辆需要从数个场站中出发,在车辆最大工作时间的约束下,按照每个客户不同的响应时间需求,对两类客户提供不同的服务,最终完成后回到出发时的场站,目标是找出运行费用最小的路线安排。由于该问题属于NP-hard问题,本文提出用萤火虫算法求解。首先,利用一种基于轮盘赌的节约算法,构建出萤火虫算法的初始解种群集合;其次基于优化方向与步长的思想对解的特征值进行定义,设计确定步长的方法,最后采用贪婪式的移除-插入算法对亮度低的萤火虫进行改进并获得最优化的解。本文首先利用小规模的测试算例,利用CPLEX软件得到算例的解和最优目标值,与本文提出的算法得到的解和最优目标值进行比较,验证了数学模型的正确性。随后,本文利用经典集散货物运输问题(Pickup and Delivery Problem,PDP)实验算例进行修正与完善,构建出适用于本文的实验数据,将本文提出的萤火虫算法与贪婪式的移除-插入算法以及CPLEX软件在2小时内得到的最好解进行比较,验证算法有效性。实验结果表明,本文提出的萤火虫算法在解决中等规模的MDANRPRBV问题时,优化结果与贪婪式的移除-插入算法相比,解的平均质量有6.57%的改进;萤火虫算法的优化结果比CPLEX的得到的优化结果平均改进6.69%,且解的方差维持在20左右,说明算法稳定性较强。算法平均运行时间为20.23分钟,远低于CPLEX软件2小时的运算时间。本文提出的算法可以为道路救援企业决策者提供理论支持,使企业在保证客户满意度的基础上,降低运营成本,提高救援效率。
[Abstract]:In the existing arc route problem with capacity load, the vehicle starts from the station, serves all the customers according to certain driving rules, and finally returns to the station. There are two types of customers, one is Node customer, the other is Arc customer. Some customers only need to send oil, power transmission and other services do not need mobile vehicles; arc customers need to rescue vehicles from the fault site to the service of the corresponding maintenance point, and each customer has their own response time requirements. Based on this background, this paper presents a multi-site arc hybrid route problem in vehicle rescue with multi-depot arc-node routing problem in the rescue of breakdown vehicle (MDANRPRBV). In this problem, the vehicle needs to start from several stations, under the constraint of the maximum working time of the vehicle, according to the different response time needs of each customer, provide different services to the two types of customers, and return to the starting station after the final completion. The goal is to find out which route is the least expensive. Since the problem belongs to NP-hard problem, this paper proposes a firefly algorithm to solve the problem. Firstly, the initial solution population set of the firefly algorithm is constructed by using a saving algorithm based on roulette. Secondly, the eigenvalue of the solution is defined based on the idea of optimization direction and step size, and the method of determining the step size is designed. Finally, the greedy removal-insertion algorithm is used to improve the low brightness firefly and obtain the optimal solution. In this paper, a small scale test example is first used to obtain the solution and optimal target value of the example by using CPLEX software, which is compared with the solution and the optimal target value obtained by the proposed algorithm, and the correctness of the mathematical model is verified. Then, the experimental example of Pickup and delivery problem (PDP) is used to modify and perfect the experimental data, which is suitable for this paper. The proposed firefly algorithm is compared with the greedy removal-insert algorithm and the best solution obtained by CPLEX software within 2 hours. The validity of the algorithm is verified. The experimental results show that the average quality of the solution is improved by 6.57% compared with the greedy removal and insertion algorithm in solving the medium scale MDANRPRBV problem. The optimization result of the firefly algorithm is 6.69 better than that obtained by CPLEX, and the variance of the solution is about 20, which indicates that the algorithm is stable. The average running time of the algorithm is 20.23 minutes, which is much lower than that of CPLEX software in 2 hours. The algorithm proposed in this paper can provide theoretical support for the decision-makers of road rescue enterprises, and make enterprises reduce operating costs and improve rescue efficiency on the basis of ensuring customer satisfaction.
【学位授予单位】：南京农业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U472;U492.22

【参考文献】