基于改进蚁群算法的物流配送车辆路径优化方法

濮明月，张彦如

(1.安徽新华学院 商学院，安徽 合肥 230088；2.合肥工业大学 机械工程学院，安徽 合肥 230009)

物流配送是物流系统中的重要环节，在企业配送过程选择一个合理的路径规划能够降低物流成本，提高自身的核心竞争力，尤其是生鲜等容易腐败产品的运送，冷链运输成本较高，如果路径规划不当，会造成很大的货损和较高的运输成本，因此对物流配送车辆路径进行优化十分必要[1-2].

在传统的路径优化方法中，仅仅考虑到运输过程中的成本和损耗，忽略了客户时间窗约束产生的惩罚成本，导致物流路径的优化效果并不理想，因此设计一种基于改进蚁群算法的物流配送车辆路径优化方法.引入时间窗的惩罚机制，科学、合理地解决物流配送路径优化问题，对物流配送车辆路径进行合理规划，尽量减少配送过程中的惩罚成本和货损成本，压缩运输损失.

1 物流配送车辆路径优化方法

1.1 蚁群算法的改进

蚁群算法实际上是模仿蚂蚁的觅食行为来寻找最优路径，基于蚁群的个体数量庞大，它们之间通过信息素进行沟通，为同伴传递信息，大量的蚂蚁形成一个反馈系统，因而具有较高的效率和时间复杂度，有效解决了寻找食物的问题[3-4].研究的是物流车辆的路径优化，主要目标是缩短配送距离，降低成本，为企业创造更高的利润.蚁群算法是一种基于种群的进化算法，将其应用在路径优化中，刚开始所有的蚁群会选择不同的路径寻找食物，在搜索过程中，蚁群会靠信息素进行沟通，选择较优的路径进行二次食物寻找，如此反复迭代，会寻找到一条最优路径，其路径搜索过程如图1所示.

图1 蚁群觅食路径择优过程

蚁群算法具有很好的搜索能力，但是它的初始信息速匮乏，收敛速度比较慢，因此将蚁群算法和遗传算法相结合，提出改进的混合蚁群算法进行迭代求解.结合蚁群算法，得到路径优化问题的算法流程，如图2所示.

图2 改进蚁群算法流程

以上算法的改进主要体现在信息素的更新步骤上.

主要待解决问题的目标为路径的最优解.为更新信息素，假定蚁群中的蚁群数量为n，物流配送终点客户z和x的距离为dzx，且设定为客户之间的亲密程度，即为可见度.在某时刻t的某蚁群到z客户之间的不可逆移动概率计算公式为：

(1)

公式(1)中，B为蚁群没有达到的客户集合，根据这个过程的不断调整，得到路径的信息素更新结果为：

(2)

公式(2)中的β为信息残留程度.

在路径信息素的更新基础上，建立在基因编码上进行遗传算法的选择、交叉和编译3个遗传操作.采用模仿染色体编码的方法对配送路径进行编码，得到一组自然数组成的配送方案编码，选择的核心思想是复制，复制继承父代中的最优解继续改进，避免优质解丢失，交叉可以产生新个体，增加多样性，防止早熟停滞，对最优个体进行变异操作，保存最优解.

1.2 基于改进蚁群算法的物流配送车辆路径优化建模

路径优化问题中，主要包括物流配送中心、需求地点、货物、车辆、约束条件和目标函数等要素构成.在实际的物流配送过程中，会存在一个车辆实际载重问题，假设在一次配送过程中，有K辆车共同配送到N个需求地点，第i个地点对于运送货物的需求量为mi，每辆车的最大载重设为Q，需求点i到需求点j的距离表示为dij，车辆的平均行驶速度为s，需求点i要求货物到达的最早时间表示为ai，要求货物到达的最晚时间表示为bi，第i辆车的配送路线上需求点的数量表示为nk，那么研究问题最优蚁群目标函数可以表示为：

(3)

若第k辆车从需求点i行驶到了到需求点j，那么xijk的值为1，否则为0[5-6].针对上述的目标函数做出假设，设定的配送中心仅有一个且位置确定不变，配备足够的产品和物流配送车辆，所有的配送车辆都需要送配送中心出发，最后再返回配送中心，方便对物流车辆进行下一次的调度管理，所有的需求点位置已知且固定不变，根据上述条件，能够得到目标函数的约束条件为：

(4)

公式(4)中L为客户总数.在配送过程中，若第k辆车完成需求点i的配送服务，那么yik的取值为1，否则为0[7-8].在约束条件中，对配送过程进行相关的配送约束，约束条件中的第1个约束公式表示每个需求点有且仅有1次配送服务，也就是说只能由一辆车进行配送；第2个约束公式表示每辆车的配送路线上所有需求点的货物需求量总和不能超过车辆的最大载重；第3个公式表示配送车辆的出发地点都必须在配送中心；第4个公式表示配送车辆完成配送后都必须回到配送中心.

1.3 物流配送成本

在物流配送的过程中，为保证配送物品的新鲜与完整，配送的成本一般包括固定成本和变动成本.固定成本主要是指与车辆有关的购置费、折旧费以及开车司机和装卸工人的工资等，固定成本是在进行配送服务之前就已经产生了，与后续的配送路程没有关系，且固定成本是由配送车辆的数目决定的[9-11].变动成本包含的项目比较多，主要包括运输成本、货损成本、惩罚成本以及生鲜类商品需要冷链运输的制冷成本[12-13].对物流配送车辆路径进行优化的主要目的就是要降低变动成本，其中的运输成本主要是指商品在运输过程中所产生的费用，包括燃油费以及制冷费等与车辆行驶的距离和时间成正比，可以表示为：

(5)

式(5)中，B代表所有需求点的集合；U代表所有车辆的集合；Ck表示运输车辆单位里程的运输成本.当车辆k从需求点i行驶到需求点r时，zirk为1，否则为0,货损成本可以表示为：

(6)

式(6)中，ρ1表示配送产生的货损比例；ρ2表示卸货货损比例；C0表示单位商品的价值；tirk表示车辆k从需求点i到r的行驶时间.当车辆k完成对需求点r的配送时，yrk为1，否则为0.制冷成本可以表示为[14-15]：

(7)

式(7)中，α0表示车体劣化程度；E为热传导率；Sout、Sin分别表示车体的外、内表面积；Tout、Tin分别表示车体的外、内温度；p为制冷剂价格.运送的惩罚成本可以表示为：

C5=δC0Mi.

(8)

式(8)中，δ为惩罚因子；Mi表示需求点i的缺货数量.根据上述的成本计算公式，能够清晰地计算出物流配送过程中的固定成本和变化成本.对于路径的优化有很好的参考作用.

至此完成基于改进蚁群算法的物流配送车辆路径优化.

2 算例分析

2.1 数据来源

算例分析以某连锁生鲜经营企业的物流配送为例，选取生鲜作为算例中的配送产品，由配送中心对编号1-18门店进行冷却生鲜配送.目标是优化配送中心生鲜的车辆配送路径，将物流的配送成本降到最低.配送中心以及各个门店的地理位置如图3所示：

图3 配送中心和各个门店的地理分布图

图3中，标号为0的地标代表配送中心，标号1～18代表18家门店，配送中心在对各个门店进行生鲜产品配送时，要保证在规定时间内送达，且需要保证供应数量，否则会给该门店造成一定损失，配送要受到惩罚.因此在进行路径规划时，需要对生鲜商品需求量以及约定的服务时间窗进行设置，如表1所示.

表1 各门店生鲜商品需求量以及时间窗

2.2 实验结果分析

在分别对算例进行100次求解后，最终得到了传统文献[3]方法和所提方法的最优配送路径，如图4所示：

(a)文献[3]方法

(b)所提方法图4 不同配送路径对比

图4(a)为传统方法最终得到的最优路径；图4(b)为所提方法最终得到的最优路径.对这两种配送路径进行成本分析，如表2所示：

表2 路径成本分析

在路径分析中，考虑了5种成本进行路径优化，在实际应用中的约束效果更好，得到的最优路径能够明显的节省运输成本，提高收益；惩罚成本是从各个门店的视角出发，能够体现配送满意度.

在验证所提方法的成本约束基础上，为更直观测试不同方法的物流配送车辆路径的有效性，以耗时为实验指标进行实验结果输出.假定本次实验中所有物流运输车辆的车速一致，其耗时越低，则说明其路径越短，优化效果越好，具体实验结果如图5所示：

待配送门店数量/个图5 不同方法的路径耗时对比

由图5的实验结果可以看出，随着待配送门店数量的增多，两种方法的路径耗时不断增加.但是很明显，所提方法的耗时始终低于文献[3]方法，且门店数量达到300个以上时，耗时的增量较小.通过以上实验结果可以得出结论：使用设计的方法对物流配送车辆路径进行优化，在满足车辆容量约束、时间窗约束和惩罚约束的情况下，能够得到总成本最低的物流配送路径方案.

3 结 论

物流车辆的入境规划是物流配送的关键，基于传统路径规划方法的缺陷，将蚁群算法与遗传算法进行结合设计了一种新的物流车辆配送路径优化方法.实验结果表明，所设计方法对路径进行优化后，能够有效地降低变动成本.但是研究还有一些不足之处，建立的模型约束条件相对于实际情况考虑的不够全面，例如交通方面出现突发状况时，缺乏实际的调度能动性，在今后的研究中需要进一步解决.