基于改进蜂群算法的模糊需求冷链物流车辆路径优化

姜婷

摘要针对基本人工蜂群算法容易早熟收敛等问题，提出了3种邻域生成策略，并对当前解进行局部搜索和进化。仿真试验表明，该算法在求解相关问题上具有有效性，对求解用户模糊需求下的冷鲜品冷链物流车辆路径优化问题具有一定的参考价值。

关键词改进蜂群算法；模糊需求；邻域生成策略；冷链物流车辆路径优化

中图分类号TS391文献标识码A文章编号0517-6611（2017）21-0213-03

Optimization of Coldchain Logistics Vehicle Routing with Fuzzy Demand by an Improved Artificial Bee Colony Algorithm

JIANG Ting

（Department of Information Engineering， Anhui Economic Management College， Hefei， Anhui 230059）

AbstractAiming at the premature convergence problem of the basic artificial bee colony algorithm， 3 neighborhood generation strategies were proposed， and the local search and evolution of the solution were carried out. Simulation test results showed that the proposed algorithm was effective in solving related problems， and had a certain reference value for solving the coldchain logistics vehicle routings optimization problem of cold and fresh goods under the fuzzy demand of users.

Key wordsImproved bee colony algorithm；Fuzzy demand；Neighborhood generating strategy；Coldchain logistics vehicle routings optimization

隨着我国居民生活水平的提高，人们对冷鲜品的需求不断增大。冷鲜品对运输和储存环境的要求较为严格，容易腐坏变质，物流费用占冷鲜品总成本的比例较高。因此，如何提高冷链运输效率具有较高的研究价值，冷链车辆路径优化是其中一个关键的研究领域。该问题是一个NP（非确定多项式）难题，很多学者采用启发式算法进行求解并取得较好效果。韩印等[1] 采用综合节约算法求解了考虑道路状况的冷链路径优化问题。潘东静[2] 采用遗传算法对需求模糊下的农产品冷链车辆路径进行了优化。曹倩等[3]改进了遗传算法，在选择操作前根据非劣解水平进行排序，并利用拥挤程度对同级的不同个体进行排序。陈梦等[4] 在冷链物流路径优化模型中加入制冷成本和货损成本，采用遗传算法进行了优化和求解。白焘等[5] 基于人工蜂群算法求解了冷链物流配送车辆路径。王淑云等[6] 将K-means聚类算法、蚁群算法和随机动态规划算法相结合，构建并求解了具有配送时限要求的冷链品多温共配路径优化模型。王咪等[7] 将2-Opt算法与免疫遗传算法相结合，求解了考虑道路颠簸影响的冷链物流配送车辆路径。

人工蜂群（Artificial bee colony，ABC）算法由Karaboga[8]提出。该算法鲁棒性强、不需要梯度信息，比较容易编码及实现，在求解优化问题方面具有较好的效果[9-11]。在求解冷链物流车辆路径时，用户的需求往往呈现出一定的模糊随机性，在一个可能的范围内浮动，因此可以采用三角模糊数表示。笔者针对冷鏈物流的特点，对离散蜂群算法进行了邻域设计，求解了带时间窗的用户需求模糊条件下的冷链物流车辆路径问题。

1带时间窗的模糊需求冷链物流车辆路径数据模型

1.1问题描述

冷鲜品车辆路径问题可描述为：现有1个配送中心，K辆冷藏车，每辆车最大载重为Q；n个客户，每个客户的配送需求用三角模糊数描述为di（d1i，d2i，d3i），i=1，2，…，n。求解如何安排车辆行驶路线，能使总成本最低，客户满意度最高。

1.2模型建立

1.2.1参数说明。

为方便描述模型，对相关参数做以下说明：

Cij为客户i的直线距离（i≠j）；

P为冷鲜品单位价格；

F为单位距离的行驶费用；

[ai，bi]为客户i要求服务的时间窗；

tki为车辆k到达客户点i的时间；

θ1为在ai之前到达客户点等待的单位时间成本；

θ2为在bi之后到达客户点单位时间的罚金成本；

φ1为运输过程中的货损比例。

φ2为开启车门导致的货损比例。

yik=1，客户i由车辆k配送0，其他

xijk=1，车辆k从i访问j0，其他

1.2.2构建模型。

模型构建要求在满足客户需求、时间窗、车辆载重等条件下，求出物流总成本最低时的车辆行驶路径。总成本包括运输成本、货损成本和违反时间窗的惩罚成本。

（1）运输成本。

为简化计算，运输成本由车辆行驶里程决定，记作cy，计算公式如下：

cy=Kk=1ni=0nj=0Fcijxijk（1）

ni=0d3iyik≤Q，k（2）

Kk=1yik=1，i（3）

ni=1xijk=yjk，j，k（4）

i，j∈Sxijk≤|S|-1，S∈{1，2，…，L}，k（5）

其中，公式（1）为总运输成本；公式（2）保证客户最大需求量不得超过车辆载重能力；公式（3）、（4）保证每一个客户只能被1辆车访问1次；公式（5）用于消除子回路。

（2）货损成本。

与普通商品不同，冷鲜品在运输过程中会有一定程度的货损可能，货损成本由此产生。货损成本包括运输时间累积产生的损耗及打开车门造成的损耗。货损成本记为CS，计算公式如下：

cs=PKk=1ni=1yik（φ1cij+φ2di）（6）

（3）违反时间窗的惩罚成本。

违反时间窗的服务会造成惩罚成本。采用软时间窗，来计算惩罚成本。当在指定配送时间[ai，bi]到达时，无惩罚成本；当配送时间早于ai，或者晚于bi，都要进行一定程度的惩罚。惩罚成本记为Cf，每个点的计算公式如下：

cfi=θ1i（ai-tki），tkiθ2i（tki-bi），tki>bi（7）

Cf=ni=1cfi（8）

（4）建立目标函数。根据上述不同成本的分析，建立目标函数如下：

MINC=Cy+Cs+Cf（9）

2人工蜂群算法及其改进

2.1基本人工蜂群算法

人工蜂群算法的设计思想模仿了蜜蜂的采蜜行为，蜜源代表优化问题的可行解，通过蜂群的搜索行为进行优化。蜂群中蜜蜂比例和分工情况如下：采蜜蜂占蜂群的50%，与蜜源数目相等，在其初始位置的邻域范围搜索新蜜源；观察蜂也占蜂群的50%，根据采蜜蜂所在蜜源质量决定是否跟随，并在邻域范围搜索新蜜源；侦察蜂由采蜜蜂转化而来，如果蜜源质量经过limit次开采后还没有提高，则该蜜源被放弃，采蜜蜂转为侦察蜂，在全局范围内搜索新的蜜源。

观察蜂根据蜜源质量进行选择的概率公式为：

Pi=fiNi=1fi（10）

其中，fi为蜜源i的适应度，N为蜜源的个数。观察蜂根据蜜源适应度以概率Pi选择蜜源。采蜜蜂和观察蜂搜索新蜜源的方式是相同的，在邻域内搜索并比较新旧蜜源适应度，采用贪婪机制进行更新，即如果新位置的蜜源优于原位置的蜜源，则替换之，否则保留原来位置的蜜源。已知原蜜源位置xij，产生新蜜源位置vij的公式为：

vij=xij+ij（xij-xkj）（11）

2.2邻域生成策略

在求解复杂问题时，人工蜂群算法容易出现搜索能力不足、早熟收敛等缺点。针对人工蜂群的不足，在引领蜂、跟随蜂的局部搜索阶段采用3种邻域，生成指定数量的新解序列，所指的位置均为随机生成。邻域策略描述如下：

①交换邻域生成策略（SWAP）。随机选择原始解的2个位置的数据，并进行互换；

②前插邻域生成策略（INSERT）。随机选择原始解的1个位置数据，将其取出并插入到随机位置；

③倒转邻域生成策略（INVERSE）。在原始解随机选择一段数据，将其中的所有数据进行逆序排列。

3算法设计

3.1问题编码及初始化

采用自然数的编码方式，0表示配送中心，1～n表示客户。每辆车从配送中心出发，最后返回配送中心，所以每辆车的运送路线以0作为开始和结束。采用PFIH方法构造初始解。

3.2算法流程

①对蜂群进行初始化并设置相关算法参数，主要包括蜂群规模、最大迭代次数和邻域列表长度等；

②引领蜂采用“2.2”部分设计的邻域生成策略产生随机产生指定数量的新解，采用贪婪算法更新，并将原始解替换为适应度最高的解；

③采用公式（10）计算跟随蜂选择蜜源的概率，接着跟随蜂采用与步骤②相同的方式替换原解；

④记录每次迭代产生的局部最优解；

⑤计算解的更新情况，如果达到limit次仍未改变，则丢弃之，并由侦察蜂在全局范围内搜索新解；

⑥将此次迭代局部最优解与目前的全局最优解进行比较，如果适应度高则取代之，否则保留；

⑦判断是否满足终止条件，如果满足则输出最优解，算法结束，否则转步骤③。

4算例验证及结果分析

为验证文中算法的有效性，设计1个测试用例，有1个配送中心和2辆冷链车辆，客户数为8，车辆最大载重为8。配送中心、客户点之间的距离，各客户点的时间窗和需求如表1～2所示，采用Matlab R2013a编程并进行测试。试验参数设置如下：种群规模设置为80，最大迭代次数为60，邻域列表长度為6，算法运行10次。

5结语

笔者分析了冷鲜品物流的车辆配送路径问题的数据模型，提出了一种改进的离散人工蜂群算法进行求解。为避免基本人工蜂群求解优化问题的不足，设计了新的邻域生成策略进行局部搜索，通过实例验证了该算法的有效性和稳定性，对于求解用户模糊需求下的冷鲜品冷链物流车辆路径优化问题具有一定的参考价值。

参考文献

[1] 韩印，师攀.基于道路状况的冷链物流配送路径优化[J].物流科技，2015，38（6）：90-93.

[2] 潘东静.具有模糊需求的农产品冷链物流车辆配送路径优化研究[J].安徽农业科学，2015，43（5）：334-335，370.

[3] 曹倩，邵举平，孫延安.基于改进遗传算法的生鲜农产品多目标配送路径优化[J].工业工程，2015，18（1）：71-76.

[4] 陈梦，曾阳，唐驿，等.食品冷链物流配送路径优化问题研究[J].物流工程与管理，2015，37（1）：145-147.

[5] 白焘，李鸣，严良涛.蜂群算法在冷链物流配送车路径规划中的应用[J].湖北农业科学，2016，55（22）：5958-5962.

[6] 王淑云，孙虹.随机需求下冷链品多温共配路径优化研究[J].工业工程与管理，2016，21（2）：49-58.

[7] 王咪，杨孔雨.基于2-Opt免疫遗传算法的冷链配送路径优化问题研究[J].物流技术，2016，35（7）：72-76.

[8] KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Kayseri：Eroiyes University，Engineering Faculty，Computer Engineering Department，2005.

[9] SINGH A.An artificial bee colony algorithm for the leafconstrained minimum spanning tree problem[J].Applied soft computing，2009，9（2）：625-631.

[10] PAN Q K，TASGETIREN M F，SUGANTHAN P N，et al.A discrete artificial bee colony algorithm for the lotstreaming flow shop scheduling problem[J].Information sciences，2010，181（12）：2455-2468.

[11] XU C F，DUAN H B.Artificial bee colony（ABC）optimized edge potential function（EPF）approach to target recognition for lowaltitude aircraft[J].Pattern recognition letters，2010，31（13）：1759-1772.