基于改进蚁群算法的鲜活农产品配送路径优化

詹长书，李正娇

（东北林业大学 交通学院，黑龙江 哈尔滨 150040）

基于改进蚁群算法的鲜活农产品配送路径优化

詹长书，李正娇

（东北林业大学 交通学院，黑龙江 哈尔滨 150040）

根据鲜活农产品“易腐”等自身特点、客户的消费特点以及目前鲜活农产品配送中存在的问题，基于VRP理论，构建物流配送路径优化模型，应用改进的蚁群算法对模型进行求解，满足顾客对时间、质量的要求，降低配送成本，提高顾客满意度。

最大最小蚁群算法；鲜活农产品；配送；路径优化

1 引言

遗传算法对模型进行优化求解。本文采用改进的蚁群算法求解配送优化模型，获得最优解。

目前，我国农产品存在流通损耗严重，配送成本高等问题。为了提高服务水平，降低运费成本和损失成本，在新鲜农产品配送系统中，需要采取更有效的配送策略，实现低成本、高效率的物流配送。

国内针对鲜活农产品配送的研究有很多，如杨磊[1]、李雅萍[2]等构建了鲜活农产品配送优化模型，分别应用遗传算法等对其进行求解，通过算例对构建的模型进行验证。向敏[3]、庄景明[4]分别构建了电子商务下和鲜活农产品回收路线的配送优化模型，应用遗传算法与改进的

2 模型构建

2.1 模型描述与假设

鲜活农产品的配送过程为：由鲜活农产品的加工配送中心根据各用户的需求量进行配送。为降低成本实现利益最大化，对配送中心作如下假设：

（1）每个客户地理位置和需求量已知；

（2）每条配送路径上各客户的货物需求量之和在车辆最大载重量范围内；

（3）每个客户仅由一辆配送车辆服务，且配送量不超过车载量限制；

（4）货物必须在客户指定时间窗内送到；

（5）配送中心农产品储存充足，可以满足客户的需要；

（6）车辆配送速度已知；

（7）仅考虑时间因素对品质的影响。

2.2 符号定义

对各相关参数变量用数学符号进行如下定义：

V0：配送中心；

m：拥有车辆数；

dij：从需求节点i到需求节点 j距离；

vij：从需求节点i到需求节点 j行驶速度；

τij=：配送车辆从需求节点i行驶到需求节点 j所花的时间；

wik：车辆k到节点i时处理配送任务所需要时间；

qi：需求点i的需求量；

si：节点i处货物到达所允许的最早开始时间；

ei：节点i处货物到达所允许的最迟开始时间；

cij：从需求节点i到需求节点 j的运输成本；

2.3 鲜活农产品的变质函数

Dave和Shiue[5-6]等通过对物品的变质速度研究，指出具有随机生命周期的易腐物品的变质速率常用指数形式表示。鲜活农产品变质函数 Q(t)=Q0∙K∙e-βt中 Q0为其完好时的质量，K为变质常数，β为敏感系数，若 β的取值小，说明鲜活农产品对时间敏感度相对大，t为运输时的时间。在本文中，用新鲜农产品的指数变质函数描述其质量随时间和温度的变化。

2.4 模型构建

首先建立以下变量：

则鲜活农产品配送路线优化问题的数学模型为：

式（1）为目标函数，由两项组成，第一项为运输成本，第二项为损耗成本。式（2）指配送车辆数小于配送中心车辆总数。式（3）指车辆配送完成任务后返回配送中心。式（4）与式（5）指每个客户仅被一辆车服务。式（6）指客户所需货物需求量之和小于车的载重量。式（7）指配送车辆运输与等待之和小于时间约束。式（8）指在规定时间窗内进行配送。式（9）指考虑变质情况下应从配送中心发出的配送量。

3 改进遗传算法设计

应用改进后的最大最小蚂蚁算法（MMAS）对建立的配送模型进行求解。MMAS是德国学者Stutzle[7]等提出的方案，其算法步骤如下。

Step1：变量初始值设置。初始时刻Δτij=0。每条路径上的信息素值为τij=1，迭代次数nc←0,k←1，车辆行驶时间T_solu=0。车辆剩余载重Q_net=Q，尚未满足需求的需求点集合V_net={V1,V2,…,Vn}为较大正数。

Step2：根据车辆载重量和时间窗的限制，确定蚂蚁下一步可选择的转移点的结合V_allowd。判断V_allowd是否为空集，如果V_allowd是空集，置 k←k+1，T_solu=0，Q_net=Q ，V_allowd=V_net。

Step4：判断V_net是否为空集，如果不是转向步骤Step2；如果是空集，则所有需求点均被配送到货，则记录蚂蚁个数k←m。

Step5：对各边(i,j)进行信息素的更新：

本次蚂蚁在路径搜索中求得全局最优解长度：L(gb)=0.1≤ρ≤0.9。

Step6：对信息素上限与下限进行判定与调整：

Step7：对各边(i,j) ：设置 Δ τij←0；nc←nc+1。如果有改善，记录下当前所求得的解。

Step8：if   nc＜ N C（预定的迭代次数），重新迭代，否则跳出。

4 算例验证

某鲜活农产品配送中心向其覆盖范围内的12个超市进行配送，配送车辆的最大载重量为8t，行驶速度为50km/h。配送中心与12个超市的地理信息见表1，12个超市的需求量—时间窗—处理时间见表2，假设该鲜活农产品随时间的变质函数为：Qt=Q0∙e-t/200。

应用MATLAB软件进行求解，运行20次的结果分别为：2 168.1，2 147.5，2 156.0，2 142.1，2 143.2，2 142.1，2 146.5，2 142.1，2 142.1，2 159.7，2 142.1，2 142.1，2 142.1，2 143.2，2 120.5，2 160.7，2 142.1，2 142.3。所得的最优解为2 120.5。

车辆次序及载重量见表3，具体配送路线图如图1所示。算例最优化解的变化趋势如图2所示，变化趋势由波动较大逐渐趋向平缓趋向最优解。在运行20次后发现所得解的最差与最优结果相差较小，证明改进的蚁群算法是有效的。

表1 配送节点位置信息

表2 各客户的业务需求

图1 各车辆配送路线

图2 最优解趋势图

表3 优化结果分析

5 结论

利用改进后的MMAS算法求解，将鲜活农产品的“易腐”特性与时间因素结合起来构建鲜活农产品配送路径优化模型。通过实例验证建立的鲜活农产品配送路径优化模型和算法是可行的。本文的研究对于鲜活农产品企业进行车辆调度的安排有着较强的实用价值。

[1]杨磊,袁喜玲,张智勇.基于顾客满意度的鲜活农产品配送优化研究[J].物流技术,2014,(19):137-141.

[2]李雅萍.鲜活农产品冷链物流配送路径优化研究[J].价值工程,2013,(31):25-27.

[3]向敏,袁嘉彬,于洁.电子商务环境下鲜活农产品物流配送路径优化研究[J].科技管理研究,2015,35(18):166-171.

[4]庄景明.基于遗传算法的鲜活农产品收购路线优化研究[J].韶关学院学报,2012,33(8):24-28.

[5]Dave U,Pandya B.Inventory Returns and Special Sales in a lot-size System with Constant Rate of Deterioration[J].European Journal of Operational Research,1985,(19):305-312.

[6]Shiue Y C.An Inventory Model for Perishable Items in a lotsize System with Quantity Discounts[J].European Journal of Operational Research,1990,(45):260-264.

[7]T.Stützle,H H Hoos.Max-Min Ant System[J].Future Generation Computer Systems,2000,(16):889-914.

Optimization of Fresh Farm Produce Distribution Route Based on Improved Ant Algorithm

Zhan Changshu,LiZhengjiao
(School of Communication,Northeast Forestry University,Harbin 150040,China)

In this paper,in view of the characteristics of fresh farm produce,such as being perishable,the property of consumer behavior and the existing problems in the distribution of fresh farm produce at current stage,we built the corresponding logistics distribution route optimization model based on the VRP theory and solved it using the improved ant algorithm so as to meet the consumer's requirement for time and quality,lower distribution cost and improve customer satisfaction.

max&min ant algorithm;fresh farm produce;distribution;route optimization

F224.0;F762;F252.14

A

1005-152X(2017)09-0089-03

10.3969/j.issn.1005-152X.2017.09.020

2017-08-07

詹长书（1970-），男，东北林业大学副教授，研究生导师，研究方向：物流系统规划与设计；李正娇（1993-），女，东北林业大学交通学院物流工程硕士。