基于改进蚁群算法的危险化学品运输路径优化
2023-03-23杜玟谛张虹
杜玟谛 张虹
北京信息科技大学信息管理学院 北京 100192
危险化学品运输中的事故具有低概率、高危害的特性，一旦发生就会对生命和财产安全带来极大的威胁，造成不必要的经济损失和社会影响。目前我国危险化学品物流中存在重复运输、运力的选择不当、运输的半径过大[1]、管理效能不足和从业人员素质比较低等问题，物流运输过程主要依赖于线下，整体管理覆盖面比较窄，水平也较低。京F公司现有的运输模式就是依赖第三方物流公司，运输过程中的安全监管面临很大的困难，同时使用第三方物流公司的成本也较高。所以，对于路径的长度以及过路费的计算需要专业的地图软件进行快速的计算和预测。
近年来，国内外学者对蚁群算法的路径优化问题和危险品运输路径优化的问题已开展了一些研究。例如，杨锦冬[2]等提出了车辆分配和装载的双目标路径优化；魏航[3]等解决了时变条件下多式联运有害物品运输的最短路问题；Karkazis[4]等对运用分支定界的算法危险品运输路径的优化模型进行了研究；Akgun[5]等对考虑天气系统影响的危险品运输路径选择问题进行了研究。
1 问题描述与模型构建
1.1 危险化学品运输问题描述
由于危险化学品的特殊性，大量危险化学品在运输过程中存在潜在的风险，运输车辆在发生事故后对人们的生命财产及周边环境的安全构成极大威胁。所以，面对越来越多的关于危险化学品运输车辆的事故，有些道路在最近几年开始禁止危险化学品运输车辆的通行，导致运输路径经常变化对成本的预测造成了很大的困难。目前百度地图等导航软件已经增加了危险化学品车辆的备案和导航服务，司机可以使用导航软件提供的从配送中心到每一个顾客彼此之间的一到三条路线，躲避修路、封路等不确定因素造成的禁行风险。同时可以较为准确地估算出从配送中心到每一个顾客彼此之间的距离和所要缴纳的过路费。
对危险化学品的运输过程进行研究，要从货物装载至车辆开始，使用符合指定条件并经过检查的合规的专用运输车辆，运输过程要保证安全和及时，同时要保证送到客户指定位置，如客户仓库等。我们可以把危险化学品的运输问题看成一个配送中心的物流运输问题，危险化学品进入仓库后被相应数量的运输车全部配送至客户指定位置，从同一个仓库出发，在满足每个客户提出的需求后又返回该仓库。在保证运输安全的情况下，根据客户指定的位置坐标、需求量、高速过路费等数据，以包括运营总成本最低为目标，求解出一个从仓库出发并满足所有客户需求的物流配送优化方案。
(1)危险化学品仓库和客户指定的位置坐标已知，仓库为本企业自己的仓库，不需要租赁费用，每个客户的危化品需求量已知，每条路径的高速过路费已知，这些已知的条件已确定且不会再改变。
(2)运输路径的起点为危险化学品的仓库，当运输车完成运输任务后返回到仓库，形成一个完整的物流运输路线。
(3)企业的同种类型运输车辆足够多且满足客户的需求，车辆的油耗、司机的食宿费用、车检罐检及保险费用、路径上的限重等参数已知，车辆为每个客户的配送量都小于自身限重。
(4)在运输过程中，为客户提供服务时，除卸货情况外没有其他装卸活动。
(5)每辆车都可以配送多个客户点，且只允许1辆车出发和到达1次。
(6)危险化学品运输不允许混装，除限重外不考虑道路因素对车辆的影响，每辆危险化学品运输车容量有限，危险化学品运输车辆夜晚禁行。
1.2 模型构建
1.2.1 基本蚁群算法
蚁群算法来自蚂蚁寻找食物，蚂蚁会在其经过的路线上留下自己的信息素，它们依靠信息素来进行彼此的信息交流，从而找到到最优的路径。其中一条路径爬行过的蚂蚁越多，则该条路径留下的信息素也就越多，当后续有蚂蚁寻找路径时，它们选择这种路径的概率就越高，当途经的蚂蚁足够多时，信息素最多的路径就是最优路径。
1.2.2 容量受限车辆路径模型
容量受限的车辆路径模型是指：在满足一个顾客只能由一辆车对货物进行配送的前提下，配送中心派遣若干运输车辆为顾客配送货物，每辆车都从配送中心出发，当该条路径上所有的顾客配送结束后返回配送中心，规划出总成本最小的运输路径。
使用蚁群算法求解容量受限的车辆路径问题可以通过有向图G=(V，A)来进行描述，其中V={0，1，2，…，n，n+1}表示所有节点的集合，0和n+1表示配送中心，1，2，…，n表示顾客，A表示客户之间、客户与配送中心间的有向弧集合。问题规定在有向图G上，每一条配送路线必须都从0这个节点开始，在n+1这个节点结束。
容量受限的车辆路径问题[6]的模型如下。其中，Δ+(i)表示从节点i出发的所有弧的集合，Δ-(j)表示回到节点j的所有弧的集合，N=V
(1)
(2)
(3)
(4)
(5)
(6)
(7)
xijk∈{0，1}∀k∈K，∀(i，j)∈A
(8)
目标函数(1)表示最小化车辆行驶的总距离；约束(2)表示每个顾客只能被分配到其中一条路径；约束(3)～(5)限制配送车辆k在路径上的流量；约束(6)表示初始在配送中心时，配送车辆的k装载量不可以大于最大装载量；约束(7)淘汰不经过配送中心的子回路，其中集合S为集合N的子集。
2 改进蚁群算法求解步骤
2.1 改进蚁群算法
2.1.1 下一个顾客访问概率
计算出从配送中心0转移到下一个顾客的概率，蚂蚁k从i点转移到j点的概率计算公式如下：
(9)
2.1.2 轮盘赌法
蚁群算法中为了保证蚂蚁选择路径的随机性，在选择路径时概率大的路径被选择的概率大，但同时概率小的路径也有可能被选中，而不是直接选择概率大的路径，这样就不会所有的蚂蚁到这里都做出同样的选择，导致算法失去随机性。
为了避免算法失去随机性，在选择路径时使用轮盘赌的方法来选择。将每条路径的概率看作是轮盘的一个扇面，旋转轮盘，指针停在哪一个扇面上就选择对应概率的路径，通过使用一个[0，1]之间的随机数rand来模拟指针停止时指向的扇面。
2.1.3 信息素浓度更新方式
信息素浓度的更新方式是蚁群算法收敛效率的重要因素。更新信息素浓度主要有这几方面：第一，信息素浓度与此路线的长度有很大关系，为了防止该算法局部收敛过早，不能过多积累信息素，所以对信息素浓度的更新是很重要的；第二，信息素会随着时间的推移而逐渐蒸发，该条路线上的信息素浓度就会降低；第三，该条路线的所有蚂蚁经过时都会释放信息素，因为蚁群算法具有正反馈性，该条路线越短蚂蚁越多，信息素也就越多。为了将最优路径从全部的路径中最快找到,文献[7]通过寻找当次迭代中的最优路径和最差路径，加强最优路径上的信息素，同时减弱最差路径上的信息素释放量，按照式(10)方式的更新信息素，防止过快收敛导致算法陷入局部最优。
(10)
上式中Lbest表示此次迭代中的最优路径长度，Lworst表示此次迭代中的最差路径长度，Q为信息素浓度的常数。针对以上改进的信息素更新方式，将提出的信息素浓度更新的方案与基本蚁群算法相结合，从而提出一种新的改进蚁群算法。
2.1.4 运输成本
(11)
其中，cost表示运输成本；tollijk表示货车k从节点i到节点j所需的过路费；OP为当前油价；salaryk表示货车k对应的司机等工作人员的工资及餐补。
2.2 求解步骤
STEP1：设m为蚂蚁的数目，maxgen为最大迭代次数，s为配送中心，α为信息素重要程度因子，β为启发函数的重要程度因子，ρ为信息素挥发因子，Q为蚂蚁构建一次完整路径所释放的信息素总量。
STEP2：输入配送中心和n个顾客的坐标数据。输入依据地图软件测算出的配送中心与n个顾客彼此之间的距离和所要花费的过路费。
STEP3：初始化信息素矩阵和蚂蚁路径记录表，初始迭代次数计数器gen=1。
STEP4：判断迭代次数gen是否大于最大迭代次数maxgen。如果gen大于等于maxgen，则执行STEP8；如果gen小于maxgen，则执行STEP5。
STEP5：从第一只蚂蚁开始，根据轮盘赌法和转移概率计算公式，求出每一只蚂蚁下一个访问的顾客，并记录至路径记录表，构建蚂蚁的行走路线。
STEP6：将完整路径转换为配送方案，并计算出每种方案的总距离，从而计算出每种方案的总成本。
STEP7：在m只蚂蚁所规划的方案中找到最好的一个方案，更新此方案所包含的线路上的信息素，并将迭代次数gen增加1，执行STEP4。
STEP8：输出最佳配送方案。
3 实证分析
本文使用matlab2020a进行仿真实验，以京F公司的危险化学品运输的路径优化问题，说明本文中将新的信息素更新方法融入基本蚁群算法后，形成的改进蚁群算法在解决危险化学品车辆路径问题时的可行性和有效性。
3.1 利用基本蚁群算法求解
基本蚁群算法求解时的参数设置为迭代次数Maxgen=100，最大装载量C=40，蚂蚁数量m=50，信息素重要程度因子α=1，启发函数重要程度因子β=5，信息素挥发因子ρ=0.85，信息素浓度常数Q=5。
利用基本蚁群算法求解京F公司的容量受限的危险化学品运输路径问题时，得到的结果如下(图1、图2)所示：
图1 普通蚁群算法最优路径
图2 普通蚁群算法迭代次数
使用基本蚁群算法求解京F公司的容量受限的危险化学品运输路径问题，车辆使用数目为3辆，车辆行驶总距离为6479km，总成本为80830元。
3.2 利用改进蚁群算法求解
改进蚁群算法求解时的参数设置同上。利用改进蚁群算法求解京F公司的容量受限的危险化学品运输路径问题时，得到的结果如(图3、图4)所示：
图3 改进蚁群算法最优路径
图4 改进蚁群算法迭代次数
使用改进蚁群算法求解京F公司的容量受限的危险化学品运输路径问题，车辆使用数目为3辆，车辆行驶总距离为6211km，总成本为75040元。
将两种方法的结果进行对比，基本蚁群算法的路径为：车辆1：0→5→6→8→7→11→4→0；车辆2：0→12→9→3→1→2→0；车辆3：0→10→0。在第49次迭代时，得到了最优解，车辆行驶总距离为6479km，总成本为80830元。改进蚁群算法的路径为：车辆1：0→10→8→4→6→7→11→0；车辆2：0→12→9→3→1→2→0；车辆3：0→5→0。在第23次迭代时，得到了最优解，车辆行驶总距离为6211km，总成本为75040元。
本文改进的蚁群算法使得运输总成本比基本蚁群算法降低了5790元，行驶总距离降低了268km，最优解迭代次数减少了26次。不管是在行驶距离、计算效率还是在总成本上都有较大的优势。
4 结论
由于运输过程中可能出现路况变化等问题，变更运输路线的情况变得越来越常见，司机们也开始熟练运用专业地图软件进行导航，从而规避堵车等原因临时交通管制等风险。由于危险化学品运输车辆的容量有限，而客户的需求总量又比一辆车的容量多，随着现有道路对大型危险化学品运输车辆的限制越来越多，危险品运输车辆的运输路径优化变得越来重要。本文使用的改进蚁群算法可以更快收敛，更快地计算出总距离最短、总成本最少的路径，可以有效运用于解决京F公司的危险化学品运输问题。
