论文部分内容阅读
摘 要：在现代化物流管理中，物流配送车辆的路径优化成为物流配送的重要环节，通过有效利用现有的资源，在不同的约束条件下对车辆路径进行优化以降低配送成本，实现物流科学化。本文先简述蚁群算法的基本思想，再分析经典蚁群算法实现路径优化的重要数学模型，再在此基础上对蚁群算法进行多方面改进，以实现满载率和运输距离结合的路径最优。最后通过实例计算，验证了使用改進后的蚁群算法能很好满足新的使用场景。
关键词：物流配送;路径规划;满载率;改进的蚁群算法
一、引言
随着信息技术的发展，现代物流作为一种先进的管理技术被称为“第三个利润源泉”，逐渐在世界各国形成产业化，并在国民经济中发挥着越来越大的作用。物流配送是物流中直接与消费者相连的重要环节，如何在车辆数量等限制条件下，根据不同优化目的进行有效的配送路径优化成为国内外学者的一个研究热点。
针对配送车辆最优路径的多目标问题，陈雪娇等提出了基于进化计算的双旅行商优化问题，利用遗传算法克服局部最优解，成功实现高效多目标优化。多种车型的组合优化也是多目标配送问题的研究热点，朱泽国等结合链表思想并对遗传算法进行改进，发现随着相关不确定参数的变化，尽管运输成本上升但对多车型配送满载率的影响较小。袁晓建等研究了带时间窗和同时送取货的车辆路径问题，建立相应的数学模型，并通过改进量子进化算法等方式得到更好的解。
本文以提高车辆的满载率和减小行驶路程为优化目标，对实现路径最短化的蚁群算法进行改进，提高算法效率，更好地应用求解现实问题，期望在满足限制条件的情况下找到满载率和行驶路程都能得到最优化的配送路径，提高物流配送的效率。
二、优化的蚁群算法
1.蚁群算法的基本思想
蚁群算法是一种源于自然界中生物世界的新的仿生类随机型搜索算法。人们在观察蚂蚁的行为特征时，发现存在一种称为信息素的物质，在一些重要的路径中信息素的浓度会较其他的路径更大。这是由于每只蚂蚁在行驶过程中都会分泌出信息素，在一些重要的路径上经过的蚂蚁数量较多，信息素的残留量较大，随后的蚂蚁根据信息素的浓度就会更容易选择这些重要的道路。这样子整个蚁群就会逐渐从多路径行驶转变成单一最优路径的行驶，使得行驶路径得到优化。1992年，意大利学者Dorigo在其博士论文中提出了蚂蚁系统（Ant System， AS），该系统是最早的蚁群优化算法，该算法模拟蚂蚁觅食过程中通过蚂蚁个体之间的信息素积累以及一定时间的正反馈，不断更新收敛直至找到最短路径。蚁群算法具有自组织性、分布式计算的特点，并有很强的鲁棒性，能与其他算法融合。本文基于改进的蚁群算法对物流配送路径进行优化，取得了较好的实际效果。
2.一般物流配送问题的蚁群算法的描述
一般的物流配送路径问题可以这样描述：存在单一配送中心、多个客户点和多辆载重限定的配送货车，配送中心和各个客户点的坐标以及相应的配送量确定。配送车辆一律由配送中心出发，完成任务后返回配送中心。要求确定配送中心每辆车的配送方案使得在满载率和路径两个方面都能得到最优，并满足相应的约束条件：每辆车配送的货运量不应超过车辆的载重量;每辆车只能服务一条路线，即每个客户只有一辆车进行配送;配送车辆一次运行路线距离在运行里程限制范围内。运用蚁群算法求解配送路径优化问题的基本流程如下：
（1）对各参数进行初始化设置。设开始时间t=0，最大迭代次数为Nmax，初始时刻每条路径上的信息素τij（0）=0，并设置的初值，同时建立禁忌列表tabuk，保证初始阶段表中没有任何的客户点。
（2）将m个蚂蚁随机放置在n个配送点，每个客户点最多分布一个蚂蚁，将m个蚂蚁所在客户点的信息存入禁忌列表，并更新循环次数。
（3）对于每一只蚂蚁，需要从禁忌列表中选出没有经历过的点，并根据概率转换公式，以轮盘赌算法选择下一个客户点，将所选的客户点加入禁忌列表，直到蚂蚁遍历完所有的客户点结束本轮蚂蚁的循环活动。
（5）判断是否到达最大的循环次数，若到达，则该次配送的最短路径被找出;否则，清空禁忌列表，跳转到步骤（1）重复工作。
（6）得到最优解后，输出结果，绘制出物流配送的最优路线。
3.算法的改进
根据以上的分析，对概率转换规则和信息素更新规则进行改进以实现满载率和路径相结合的路径最优。蚁群算法在很多优化类问题中表现出较强的解决能力和发展潜力，但是也存在计算量过大，搜索时间过长，容易陷入局部最优解等缺点。因此本文也通过融合其他算法，更改信息素的收敛速度，对蚁群算法进行相应的改进，加快其收敛速度并提高其全局搜索的能力。
（1）概率转换规则的改进
（3）2-opt局部优化
在蚁群算法的基础上利用2-opt算法进行优化，该算法会随机选取两个点，选取两点之间的路径并对路径进行翻转，若新路径的配送距离总长小于老路径，那么新路径就会替代老路径成为最短的路径，进一步实现了算法的优化。2-opt算法的频繁使用会使得蚁群算法的计算时间变长，极大地影响计算效率。因此只在每一次迭代结束之后，寻找该次迭代的最优解进行2-opt算法的优化，并进行一次信息素的更新，挥发系数小于首次信息素更新，以免加快收敛速度、陷入局部最优。
三、实例仿真
本文对两个实例分别用改进的蚁群算法进行计算比较。
实验1：某配送中心向8个配送点进行派件，配送车辆均为最大载重量为8T的派送车，基本配送距离为10KM，具体位置和派送量如下表，求最优配送路线。
由于实验1路径的复杂程度相对比较低，本文取蚁群的迭代次数为10次，取α=1，β=2，γ=3，信息素的挥发速度rho=0.1，每条路径的初始信息素为Q=1。随机求解十次，获得结果分布较为简单，在满载率为91.67%下，出现行驶距离79.40和80.32两种情况，且以79.40为主，实验结果较为理想。 实验2：某物流中心有5台配送车辆，车辆的最大载重均为8T，一次配送的最大行驶距离都为50KM，需要向20个客户送货，物流中心和20个客户的坐标及其客户的需求量随机产生，其中，物流中心的坐标为（1415KM，1310KM），要求合理安排车辆的配送路线，使配送总里程最短。
实验2路径的复杂程度相对较高，加大蚁群的迭代次数至100，取α=1，β=2，γ=3，信息素的挥发速度rho=0.1，每条路径的初始信息素为Q=1。随机求解十次，结果如表3所示。
根据实验可以看出，在未采用满载率和路径综合考虑的蚁群算法时，可以获得行驶距离最优解为108.6，满载率为74%。使用后可以获得最理想的实验结果为行驶距离110.4，满载率为98.75%。相较之下，虽然改进后行驶距离略长于改进前，但是满载率得到大幅度提高，实验结果非常理想。结果如下图，得到最优路径为：
四、结束语
物流配送路径优化是现代物流中的重要环节，尤其是随着当今社会经济的快速发展，用于对物流配送的需求更加多样化，如何有效利用现有的资源对车辆路径进行优化以减少企业的配送成本，提高企业的经济效益，是物流行业发展的目标。本文从物流配送问题出发，以经典的蚁群算法为基本，对蚁群算法的概率转换规则和信息素更新方式进行改进，并融合2-opt算法进行优化，提高了算法的效率。通过实例验证了改进的蚁群算法能够切实有效解决新的配送要求。
参考文献：
[1]陈雪娇.基于进化计算的多目标优化问题求解[D].西南大学，2020.
[2]朱泽国，广晓平，郭敏.不确定环境下的多车型物流配送路径优化[J].交通科技与经济，2021，23（02）：6-12.
[3]袁晓建，张岐山，吴伶，江义火.带时间窗和同时送取货的车辆路径问题模型及算法[J].福州大学学报（自然科学版），2020，48（05）：566-572.
[4]DORIGO M， MANIEZZO V， COLNMI A. Ant system： optimization by a colony of cooperating agents[J].IEEE Transactions on Systems， Man， and Cybernetics-part B，1996，26（1）： 29-41.
[5]ANIEZZO V， CARBONARO A. Ant colony optimization： an overview[C]∥C Ribeiro et al. Essays and Surveys in Metaheuristics[M].Kluwer Academic Publishers，2002.
作者簡介：金菊婷，浙江农林大学，新文科求真实验班;戴丹，浙江农林大学信息工程学院，副教授
关键词：物流配送;路径规划;满载率;改进的蚁群算法
一、引言
随着信息技术的发展，现代物流作为一种先进的管理技术被称为“第三个利润源泉”，逐渐在世界各国形成产业化，并在国民经济中发挥着越来越大的作用。物流配送是物流中直接与消费者相连的重要环节，如何在车辆数量等限制条件下，根据不同优化目的进行有效的配送路径优化成为国内外学者的一个研究热点。
针对配送车辆最优路径的多目标问题，陈雪娇等提出了基于进化计算的双旅行商优化问题，利用遗传算法克服局部最优解，成功实现高效多目标优化。多种车型的组合优化也是多目标配送问题的研究热点，朱泽国等结合链表思想并对遗传算法进行改进，发现随着相关不确定参数的变化，尽管运输成本上升但对多车型配送满载率的影响较小。袁晓建等研究了带时间窗和同时送取货的车辆路径问题，建立相应的数学模型，并通过改进量子进化算法等方式得到更好的解。
本文以提高车辆的满载率和减小行驶路程为优化目标，对实现路径最短化的蚁群算法进行改进，提高算法效率，更好地应用求解现实问题，期望在满足限制条件的情况下找到满载率和行驶路程都能得到最优化的配送路径，提高物流配送的效率。
二、优化的蚁群算法
1.蚁群算法的基本思想
蚁群算法是一种源于自然界中生物世界的新的仿生类随机型搜索算法。人们在观察蚂蚁的行为特征时，发现存在一种称为信息素的物质，在一些重要的路径中信息素的浓度会较其他的路径更大。这是由于每只蚂蚁在行驶过程中都会分泌出信息素，在一些重要的路径上经过的蚂蚁数量较多，信息素的残留量较大，随后的蚂蚁根据信息素的浓度就会更容易选择这些重要的道路。这样子整个蚁群就会逐渐从多路径行驶转变成单一最优路径的行驶，使得行驶路径得到优化。1992年，意大利学者Dorigo在其博士论文中提出了蚂蚁系统（Ant System， AS），该系统是最早的蚁群优化算法，该算法模拟蚂蚁觅食过程中通过蚂蚁个体之间的信息素积累以及一定时间的正反馈，不断更新收敛直至找到最短路径。蚁群算法具有自组织性、分布式计算的特点，并有很强的鲁棒性，能与其他算法融合。本文基于改进的蚁群算法对物流配送路径进行优化，取得了较好的实际效果。
2.一般物流配送问题的蚁群算法的描述
一般的物流配送路径问题可以这样描述：存在单一配送中心、多个客户点和多辆载重限定的配送货车，配送中心和各个客户点的坐标以及相应的配送量确定。配送车辆一律由配送中心出发，完成任务后返回配送中心。要求确定配送中心每辆车的配送方案使得在满载率和路径两个方面都能得到最优，并满足相应的约束条件：每辆车配送的货运量不应超过车辆的载重量;每辆车只能服务一条路线，即每个客户只有一辆车进行配送;配送车辆一次运行路线距离在运行里程限制范围内。运用蚁群算法求解配送路径优化问题的基本流程如下：
（1）对各参数进行初始化设置。设开始时间t=0，最大迭代次数为Nmax，初始时刻每条路径上的信息素τij（0）=0，并设置的初值，同时建立禁忌列表tabuk，保证初始阶段表中没有任何的客户点。
（2）将m个蚂蚁随机放置在n个配送点，每个客户点最多分布一个蚂蚁，将m个蚂蚁所在客户点的信息存入禁忌列表，并更新循环次数。
（3）对于每一只蚂蚁，需要从禁忌列表中选出没有经历过的点，并根据概率转换公式，以轮盘赌算法选择下一个客户点，将所选的客户点加入禁忌列表，直到蚂蚁遍历完所有的客户点结束本轮蚂蚁的循环活动。
（5）判断是否到达最大的循环次数，若到达，则该次配送的最短路径被找出;否则，清空禁忌列表，跳转到步骤（1）重复工作。
（6）得到最优解后，输出结果，绘制出物流配送的最优路线。
3.算法的改进
根据以上的分析，对概率转换规则和信息素更新规则进行改进以实现满载率和路径相结合的路径最优。蚁群算法在很多优化类问题中表现出较强的解决能力和发展潜力，但是也存在计算量过大，搜索时间过长，容易陷入局部最优解等缺点。因此本文也通过融合其他算法，更改信息素的收敛速度，对蚁群算法进行相应的改进，加快其收敛速度并提高其全局搜索的能力。
（1）概率转换规则的改进
（3）2-opt局部优化
在蚁群算法的基础上利用2-opt算法进行优化，该算法会随机选取两个点，选取两点之间的路径并对路径进行翻转，若新路径的配送距离总长小于老路径，那么新路径就会替代老路径成为最短的路径，进一步实现了算法的优化。2-opt算法的频繁使用会使得蚁群算法的计算时间变长，极大地影响计算效率。因此只在每一次迭代结束之后，寻找该次迭代的最优解进行2-opt算法的优化，并进行一次信息素的更新，挥发系数小于首次信息素更新，以免加快收敛速度、陷入局部最优。
三、实例仿真
本文对两个实例分别用改进的蚁群算法进行计算比较。
实验1：某配送中心向8个配送点进行派件，配送车辆均为最大载重量为8T的派送车，基本配送距离为10KM，具体位置和派送量如下表，求最优配送路线。
由于实验1路径的复杂程度相对比较低，本文取蚁群的迭代次数为10次，取α=1，β=2，γ=3，信息素的挥发速度rho=0.1，每条路径的初始信息素为Q=1。随机求解十次，获得结果分布较为简单，在满载率为91.67%下，出现行驶距离79.40和80.32两种情况，且以79.40为主，实验结果较为理想。 实验2：某物流中心有5台配送车辆，车辆的最大载重均为8T，一次配送的最大行驶距离都为50KM，需要向20个客户送货，物流中心和20个客户的坐标及其客户的需求量随机产生，其中，物流中心的坐标为（1415KM，1310KM），要求合理安排车辆的配送路线，使配送总里程最短。
实验2路径的复杂程度相对较高，加大蚁群的迭代次数至100，取α=1，β=2，γ=3，信息素的挥发速度rho=0.1，每条路径的初始信息素为Q=1。随机求解十次，结果如表3所示。
根据实验可以看出，在未采用满载率和路径综合考虑的蚁群算法时，可以获得行驶距离最优解为108.6，满载率为74%。使用后可以获得最理想的实验结果为行驶距离110.4，满载率为98.75%。相较之下，虽然改进后行驶距离略长于改进前，但是满载率得到大幅度提高，实验结果非常理想。结果如下图，得到最优路径为：
四、结束语
物流配送路径优化是现代物流中的重要环节，尤其是随着当今社会经济的快速发展，用于对物流配送的需求更加多样化，如何有效利用现有的资源对车辆路径进行优化以减少企业的配送成本，提高企业的经济效益，是物流行业发展的目标。本文从物流配送问题出发，以经典的蚁群算法为基本，对蚁群算法的概率转换规则和信息素更新方式进行改进，并融合2-opt算法进行优化，提高了算法的效率。通过实例验证了改进的蚁群算法能够切实有效解决新的配送要求。
参考文献：
[1]陈雪娇.基于进化计算的多目标优化问题求解[D].西南大学，2020.
[2]朱泽国，广晓平，郭敏.不确定环境下的多车型物流配送路径优化[J].交通科技与经济，2021，23（02）：6-12.
[3]袁晓建，张岐山，吴伶，江义火.带时间窗和同时送取货的车辆路径问题模型及算法[J].福州大学学报（自然科学版），2020，48（05）：566-572.
[4]DORIGO M， MANIEZZO V， COLNMI A. Ant system： optimization by a colony of cooperating agents[J].IEEE Transactions on Systems， Man， and Cybernetics-part B，1996，26（1）： 29-41.
[5]ANIEZZO V， CARBONARO A. Ant colony optimization： an overview[C]∥C Ribeiro et al. Essays and Surveys in Metaheuristics[M].Kluwer Academic Publishers，2002.
作者簡介：金菊婷，浙江农林大学，新文科求真实验班;戴丹，浙江农林大学信息工程学院，副教授