基于改进蚁群的物流配送路径优化调度方法

杜 静

（晋中职业技术学院电子信息学院 山西 晋中 030600）

0 引言

物流配送路径调度是物品配送过程中一个非常重要的环节，作用是对物品配送路径进行合理的规划和设计，根据设计好的路径将物品配送到目的地。物流配送路径调度关系到物流配送成本、物品运输质量、运输安全以及物流配送服务质量，最理想的物流配送路径为路程最短、配送时间最短、物品运输过程中不会发生损坏、路况最好，要想达到理想的物流配送路径需要对其进行合理的优化调度。目前现行的调度方法是采用传统蚁群算法对配送信息进行分析，得出优化调度策略，该方法在实际应用中求解出的优化调度策略并非最优解，实施蚁群算法求出的优化调度策略后物流配送成本比较高，并且超出物流配送成本预算，为此提出基于改进蚁群的物流配送路径优化调度方法研究[1]。

1 基于改进蚁群的物流配送路径优化调度方法

此次在传统方法基础上对蚁群算法进行改进，得到一个新的调度思路，首先建立物流配送路径调度数学模型，对物流车辆运输路径进行选择和制定过程进行描述；然后以时间最短、成本最低、运输车辆行驶安全性越高为目标，建立优化目标函数，对模型进行优化；为了便于改进蚁群算法求得最优解，对设计的优化目标函数设定约束条件，包括物流配送成本约束、车辆数量约束，以及车辆行驶距离约束和客户节点数量约束；最后根据目标点自适应调整启发函数，对蚁群算法进行改进，并利用改进后的蚁群算法对目标函数进行求解，得出最优物流配送路径优化调度策略[2-3]。

1.1 建立物流配送路径调度数学模型

物流配送路径调度是指物品运输车辆从物流配送区发出，将物品运输到客户指定地点，然后再返回到物流配送区，这一过程利用数学模型描述[4]。由于物流配送路径与物品运输距离具有一定的线性关系，可以利用这一线性关系得出物流配送最短路径，以此降低物流运输成本。客户对物流配送时间具有一定的要求，其用公式表达为：

公式（1）中，Tis表示物流配送规定时间窗在配送地点i的起始时间；i表示物流配送路径终点，即物流配送最终地点；xi表示物流配送终点的决策变量；di表示物流运输车辆在运输过程中在某一地点停留或者延误的时间；Tie表示物流配送规定时间窗在配送地点i的终止时间，即物流配送最晚规定时间，上述公式为物流配送路径调度数学模型的时间描述[5]。建立物流配送路径调度数学模型如下：

式中，F表示物流配送路径调度数学模型，k表示物流配送路径中为多个用户配送货物，H表示物流配送路径路段组成的集合，G表示由交通节点和用户节点组成的网络路径节点集合，J表示物流配送路径的容积，D表示物流配送路径规定货物载重。该模型为后续改进蚁群算法求解模型，为优化目标函数和约束条件的设计提供基础。

1.2 设计优化目标函数

在上述数学模型基础上建立优化目标函数，对模型进行优化。影响物流配送路径调度的因素主要为配送时间、安全性、配送成本、路况，根据物流配送路径优化调度需求，设定3个优化目标分别为物流配送时间最短、成本最低、运输车辆行驶安全性最高，由于在实际中是无法实现物流配送路径都能满足以上3个条件，根据重要性在后续求解中将物流运输成本放在第一位，其次是时间最短和运输车辆行驶安全性最高。

（1）配送成本最低优化目标函数：物流配送成本主要由物流配送距离、物流配送车辆等因素决定，因此该优化目标函数用公式表示为：

公式（3）中，minX表示配送成本最低优化目标函数；X0表示物流配送区开设费用；Q表示物流配送区到客户节点之间的距离，即配送车辆行驶路程；P表示目前市场上燃油平均价格；R表示物流配送成本与配送车辆行驶路程的转换矩阵；α表示物流配送交通道路条件对车辆行驶影响而产生的额外费用。

（2）配送时间最短优化目标函数：物流配送时间的长短与车辆行驶速度和路况等因素决定，假设物流配送时间为t，以时间最短建立优化目标函数：

式中，t1表示车辆从物流配送区到客户节点，卸完货后返回到物流配送区，两段行驶路途上所用的总时间；t2表示配送车辆到达客户节点卸货时间。rij表示车辆从物流配送路径节点i到节点j行驶时间；Nij表示决策变量；S表示车辆行驶平均速度；ϖ表示物流配送路径节点i到节点j之间路况条件对车辆正常行驶的影响系数；qijk表示车辆运输能力与客户获取需求量之间的转换系数，通常情况下该系数取值为1.5[6]。o表示物流配送货物总量；p表示卸货工人卸货效率；z表示卸货人数。

（3）配送安全性最高优化目标函数：以车辆行驶安全系数最高为目标建立函数如下：

公式（5）中，η表示车辆行驶安全系数；ψ表示物流配送车辆从节点i到节点j安全通过概率；α表示物流配送路径中各个道路交通事故发生概率。

1.3 设立约束条件

为了有效控制物流配送成本，物流企业在对货物配送之前都需要对物流配送成本进行预算，因此设定的成本约束条件为：物流配送成本不得超过成本预算，用公式表示为：

公式（6）中，X0表示物流配送成本预算。货物在配送中可以使用一台车辆为多个客户进行货物配送，如果配送货物量比较多，可以由多台车辆对货物进行配送，但是不能超过物流配送区未配送车辆数量，即：

公式（7）中，k表示货物配送客户数量；yk表示客户货物由y辆车完成配送任务；y0表示物流配送区未配送车辆数量；yp表示物流配送需要使用的车辆数量。运输车辆从物流配送区出发达到客户节点，没完成一次物流配送任务，参与到物流配送活动中的车辆行驶距离不能超出物流配送最大路径，即：

公式（8）中，L表示物流配送最大路径；fi表示车辆从物流配送区中心到第一个客户节点的距离；ai表示物流配送路径上两个相邻客户节点的距离。对于物流配送客户数量的约束为：物流配送路径上客户节点数量不能超过总的客户数量，同时每辆车负责的客户数量不能小于总的客户数量即：

公式（9）中，κ*表示物流配送路径上客户节点数量；κ表示物流配送总的客户数量；κ0表示每辆车负责的客户数量。利用上述约束条件对优化目标函数进行约束。

1.4 基于改进蚁群的目标函数求解

根据设定的约束条件对上文设计的优化目标函数进行求解，可以得出多个物流配送路径优化调度策略，建立解集Y，利用改进蚁群算法对解集Y中所有优化调度策略进行分析，求出最优解输出。

假设路径上每个配送车辆为一个蚁群，将蚁群寻找食物的路径定义为物流配送路径，路径上每个客户阶段为蚁群觅食的食物节点，蚁群按照每个策略中物流配送路径进行觅食运动。蚂蚁在某一时刻从节点i到节点j移动的概率定义为：

公式（10）中，Pij(t)表示蚂蚁在某一时刻从节点i到节点j移动的概率；ξij表示在时刻t时路径从节点i到节点j上残留的信息素浓度；υij表示蚂蚁后续移动节点的启发函数；α表示启发函数对蚂蚁移动方向改变概率的影响权值；β表示蚁群移动路径上信息素浓度对移动方向改变概率的影响权值[7]。在传统蚂蚁算法中蚂蚁移动路径上两个相邻节点的启发权值差异不明显，导致传统蚁群算法搜索效率比较低。考虑到该问题对蚂蚁算法进行改进，已知蚂蚁最终移动节点位置，得到路径上其他节点到目的节点的距离f，按照f值大小对路径节点的启发权值进行自适应调整，以此提高蚂蚁算法的搜索效率[8]。每条觅食路径上都含有一定的信息素，信息素被限定在特定区间内，每条路径上的信息素初始化为区间上限τmax，通过对路径上的信息素进行不断更新，淘汰掉信息素较少的路径，其更新规则为：

公式（11）中，M表示路径上蚁群数量；χ表示路径节点的启发权值；δ表示路径信息素挥发系数；∆τBEST表示蚁群在该路径中遍历食物节点后所经路径的总长。利用上述公式对路径上信息素进行更新，按照更新后信息素的多少对路径进行排序，去除掉排在最后一个路径。然后再用上述公式对路径信息素进行更新，直到路径列表中只剩下一条路径为止[9]。

2 实验论证分析

实验以某物流公司为实验对象，该物流公司配送区域共8个，并且包含7个销售点。此次实验收集了上个月1000多条配送信息，信息内容包括配送区中心位置、销售点位置、配送量、配送时间、配送车辆数量、配送车辆行驶速度等，具体数据见表1。

表1 物流配送信息表

以表1中数据作为物流配送路径优化调度计算依据，得出每次配送路径优化调度策略。此次实验分8次完成，将每次优化调度后物流配送成本进行记录，将其作为检验此次设计方法有效性的指标，并将其与成本预算和传统方法配送成本进行对比分析，见表2。

表2 两种方法应用下物流配送成本对比 单位：元

从表2中数据分析可以得出以下结论：应用此次设计方法物流运输成本没有超出成本预算，可以将物流配送成本控制在预算之内，最低配送成本低于预算26.45%，这是因为此次设计方法，是在原有的物流配送路径调度模型基础上，以成本最低为目标建立优化目标函数，并利用约束条件对目标函数求解进行约束，最后使用改进后的蚁群算法求出最优策略，使物流配送成本得到有效控制。而应用传统方法得出的优化调度策略的实施，物流配送成本远远超出成本预算，最高超出成本预算46.15%，相比较设计方法物流配送成本偏高。

3 结语

此次利用改进后的蚁群算法对物流配送路径优化调度进行计算分析，形成一套新的调度方法，实现了对传统方法的优化和创新，通过实验论证了该方法可以有效将配送成本控制在预算之内，对降低物流企业配送成本，保证物流配送安全性以及提高物流配送服务水平具有一定的现实意义。