论文部分内容阅读
在已有带容量荷载的弧路线问题中,车辆从场站出发,按照一定的行驶规则,服务所有的客户,最终回到场站。而在以故障车辆救援为(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小时的运算时间。本文提出的算法可以为道路救援企业决策者提供理论支持,使企业在保证客户满意度的基础上,降低运营成本,提高救援效率。