家电配送问题的优化

王华 蔡延光 汤雅连 朱君

(广东工业大学 自动化学院，广州510006)

随着互联网技术的快速发展，电子商务的兴起，网购已经成为一种潮流，各企业也把它视为一种新的销售平台，不论是嫁接淘宝商城，还是自建网上商城，从店商到电商是时下各企业发展的必然趋势，家电行业同样如此。未来随着网购形式的逐渐成熟，整个家电行业的网购市场是令人期待的。消费者选择网购的最大因素是价格便宜，随着消费者的成熟，他们开始更多的关注产品的质量、电商品牌、物流等服务体验。所以电商企业提高物流配送的效率也变得越发重要。随着网购客户群体的迅速发展壮大，买家的服务要求日趋细致和多样化，快递公司将为客户提供灵活周到的快递服务。快递公司在送货时，不仅要考虑运输费用，还要考虑商品的体积、重量等参数，这样就形成了家电配送优化问题，其本质也是车辆路径问题(Vehicle Routing Problem，VRP)。VRP［1］自1959年Dantzig 和Ramser 首先提出以来就引起了人们的高度重视。VRP 的实用性强，应用广泛。

王连峰等人［2］基于模糊可信性理论建立了多目标模糊期望值模型，提出了一种改进的约束多目标粒子群优化算法求解战场物资配送中带硬时间窗车辆路径问题的多重模糊性，实验结果表明了模糊的合理性和算法的有效性;陈迎欣［3］应用改进蚁群算法求解车辆路径优化问题，验证了改进蚁群算法的有效性和可行性;谭云恩等人［4］应用蚁群算法求解军事车辆配送的路径优化问题，证明了算法的有效和实用;施彦等人［5］应用集成协同PSO 算法求解车辆路径问题，理论分析和实验表明所采用的编码方式结合改进的集成协同PSO 算法可以有效解决车辆路径问题;何小年等人［6］应用禁忌搜索算法求解物流配送车辆路径模型，实验结果表明该算法比遗传算法、模拟退火算法、蚁群算法及其混合算法具有明显的优势，能很好地适应现代物流对配送环节快速、低成本的要求。目前，带车辆容积约束的家电配送问题研究不多见，而该问题模型在现实生活中普遍存在，所以具有实际研究意义，并采用混沌人工鱼群算法求解家电配送的优化问题。

1 家电配送问题描述及数学模型的建立

1.1 问题描述

家电配送问题是指对于一系列需求点，给定快递公司位置、货车数量、客户数量、客户位置、客户需求量，配送时需考虑货车的载重和容积，组织适当的运输路线，达到总成本最少的目的。

1.2 建立数学模型

1.2.1 定义参数

客户数:i = 1，2，…，l;客户需求产品重量/kg:gi;客户需求产品体积/L:vi;客户i 与j 之间的距离/km:dij;货场额定载重/kg:qc，且gi＜qc;货车额定容积/L:V，且vi＜V;车辆数:k = 1，2，…，K;车辆k 将从点i 送到点j 的单位运价/(km·h－1):cijk; 第k 辆车服务的客户个数:nk;启用车辆的固定成本/元:ck;货车速度/(km·h－1):v ;快递员工资/(元·h－1):w。

1.2.2 定义间接参数

1)一辆货车的行驶里程sk/km:sk=

2)所有货车完成任务行驶的总里程S总/km:S总=

3)一辆货车配送商品花费的时间T/h:Tk=;

5)所有快递员的工作时间和等于所有货车所花费的时间T/h:Tc= T;

6)快递员工资和Sc/元:Sc= Tcw。

1.2.3 定义变量

1.2.4 建立数学模型

目标函数:

约束条件:

目标函数式(3)表示总运输成本最低，由运输成本、车辆启用成本和快递员工资三部分构成;式(4)和式(5)为决策变量;式(6)表示车辆完成任务后，回到原车场;式(7)表示当某辆车配送客户的个数大于等于1 时，则参与了配送服务，否则，没有参与配送;式(8)表示所有客户都被服务到;式(9)表示每次配送都不能超过车辆的载重;式(10)表示货车每天配送商品的体积不超过货车容积;式(11)表示保证每辆车服务的客户总数小于等于总客户数。

2 混沌人工鱼群算法

2.1 求解思路

人工鱼群算法［7］是模拟鱼群的行为进行随机的搜索，主要利用人工鱼的觅食、聚群、追尾等行为，利用局部最优信息逐步达到全局寻优的目的。为了提高人工鱼群算法的全局搜索能力，克服基本人工鱼群算法精度低、后期收敛慢、复杂度较高等特点，本文主要是采用基于混沌搜索和反馈策略的混沌人工鱼群算法解决服饰物流运输调度问题。

2.2 混沌搜索

混沌搜索［1］具有随机性、遍历性和确定性，由混沌搜索产生初始种群克服了生成大量非可行解的缺陷，加速染色体向最优解收敛。文中选用Logistic 映射［8－9］，如式(12)所示。式中，i 表示混沌变量的序号，i = 1，2，…，r;u 表示种群序号，u = 0，1，…，n =0;βi表示混沌变量，0 ≤βi≤1 ;μi表示吸引子。当μi= 4 时，Logistic 映射完全处于混沌的状态，此时的混沌变量βi具有很好的遍历性。假设迭代次数为300，初值为0.6，得到Logistic 映射的概率分布图，如图1 所示。

图1 Logistic 映射的概率分布图

2.3 混沌人工鱼群算法求解步骤

鱼群中，每个个体的位置向量X =(x1，x2，…，xn)，X 为寻优决策变量;人工鱼个体i 与个体j 间的距离表示为di，j=;人工鱼当前所在位置的食物浓度为Y = f(X)，即为目标函数值;Visual 表示人工鱼的感知距离;step 表示人工鱼的感知距离;δ 为拥挤度因子;α 为衰减因子，Pf为反馈概率;Try_ num 表示人工鱼每次移动的最大试探次数。在寻优过程中，X 中元素的顺序表示配送的访问顺序，也就是一个潜在的解，其适应值可以衡量解X 的优劣程度。由于混沌搜索具有随机性、遍历性和确定性，所以混沌搜索要比随机搜索好。

1)反馈策略。

每条人工鱼执行完移动操作后会检验自身状态与公告牌的状态，若自身状态优于公告牌状态，则用自身状态代替原公告牌状态，这样公告牌就可以记录下历史最优状态。基于这一思路，为人工鱼定义一个新行为——反馈行为，即人工鱼向公告牌记录的最优状态移动，人工鱼以一定的概率执行该行为。

对人工鱼群算法进行改进，设置反馈概率Pf，人工鱼以概率Pf执行随机行为，以概率1－Pf执行反馈行为。优化过程开始时赋予Pf一个较大的数，随着优化过程的进行Pf按式(13)逐渐减小，α 为反馈概率的衰减因子。

2)觅食行为。

设人工鱼i 当前状态为Xi，在其感知范围内随机选择一个状态Xj，如式(14)。

其中，rand()是一个介于0 和1 之间的随机数，若Yi＞Yj，则向该位置和全局最优位置Xbest_af的向量和方向前进一步;反之，再重新随机选择状态Xj，判断是否满足前进条件，若满足，则按式(15)前进一步;若不满足则继续试探，反复尝试Try_ num 次后，如果仍不满足前进条件，则按式(16)随机移动一步。

3)聚群行为。

人工鱼探索当前邻域内(即dij＜Visual)伙伴数目nf及中心位置Xc。如果Yc·nf＜δ·Yi，表明伙伴中心有较多食物且不太拥挤，那么按式(17)朝伙伴的中心位置和全局最优位置Xbest_af的向量和方向前进一步，否则执行觅食行为。

4)追尾行为。

人工鱼探索当前邻域内(即dij＜Visual)的伙伴中Yj为最小的伙伴Xj。如果Yj·nf＜δ·Yi，表明伙伴Xj具有较高的食物浓度并且其周围不太拥挤，那么式(18)朝Xj的方向和全局最优位置Xbest_af的向量和方向前进一步，否则执行觅食行为。

5)随机行为。

随机行为是为了在更大范围内寻觅食物或同伴，随机选择一个状态，然后向该方向移动。

混沌人工鱼群算法的步骤如下:

Step1:进行初始化设置:人工鱼的感知距离Visual、人工鱼的感知距离Step、拥挤度因子δ、衰减因子α、反馈概率Pf、人工鱼每次移动的最大试探次数Try_ num 和最大迭代次数MAXGEN;

Step2:计算每条人工鱼的适应度值，将最优的人工鱼状态记入公告牌;

Step3:对每条人工鱼进行评价，对其要执行的行为进行选择，包括觅食行为、群聚行为、追尾行为，若执行后的状态优于当前状态，则向更优状态的方向前移一步，然后转至Step5;

Step4:随机产生一个数，若rand()＜Pf，则执行随机行为，否则执行反馈行为;

Step5:最优人工鱼执行混沌搜索;

Step6:更新公告牌和反馈概率;

Step7:若满足循环结束的条件则输出结果，否则转至步骤(3)。

3 仿真实验

某区域内订单中的货物信息如表1 所示。模型参数设定如表2 所示。

混沌人工鱼群算法参数设定:人工鱼群的个体数N = 20 ，每条人工鱼的初始位置随机产生，人工鱼的视野Visual = 2 ，人工鱼的步长step = 40 ，最大迭代次数max gen = 500 ，尝试次数Try_ num =20 ，拥挤度因子δ = 0.33 ，反馈概率Pf= 0.88 ，反馈概率的衰减因子α = 0.95 和执行吞食行为的阈值T_ value = 0.1 。标准遗传算法参数设定:初始化种群N = 20 ，最大迭代次数max gen = 500 ，交叉概率pc= 0.9 ，变异概率pm= 0.02 ，采用路径编码。

本文中的实验是在Intel(R)CoreTMi3 CPU 2.53GHz、内存为2.0G、安装系统为win7 的PC 机上采用Matlab R2010b 编程实现。对每个问题模型都运行算法20 次。

表1 订单中的货物信息表

表2 模型参数设定

结果分析:GA 和CAFA 求解家电配送问题模型的结果如表3 所示，GA 求解得到的最优解为1 062.202元，CAFA 求解得到的最优结果为986.401 元，所以CAFA 略优于GA。其最优路线网络图分别为图2 和图3。两种算法求解VRPVC 的一次优化过程如图4 所示，CAFA 在第8 代收敛，GA 在第17代收敛，可见CAFA 比GA 收敛快。

表3 两种算法求解VRPVC 的最优配送路线

图2 家电配送最优路线(GA－VRPVC)

图3 家电配送最优路线(CAFA－VRPVC)

图4 两种算法求解VRPVC 的一次优化过程

4 结语

对家电配送问题进行分析，构建了带容积约束的VRP 数学模型。混沌搜索被引入人工鱼群算法来提高算法的全局收敛性，反馈策略用来指导人工鱼的移动，这样就形成了混沌人工鱼群算法，应用该算法及标准的遗传算法对所建立的VRPVC 模型求解，证明了VRPVC 模型和CAFA 求解此类模型的有效性。

［1］汤雅连，蔡延光，郭帅，等.单车场关联物流运输调度问题的混沌遗传算法［J］.广东工业大学学报，2013，30:53－57.

［2］王连锋，宋建社，王正元，等.带硬时间窗的战场物资配送车辆路径优化［J］.系统工程与电子技术，2013，35(4):770－776.

［3］陈迎欣.基于改进蚁群算法的车辆路径优化问题研究［J］. 计算机应用研究，2012，29(6):2031－2034.

［4］谭云恩，张亮，杨霞，等.基于ACA 的军事物流车辆配送路径优化研究［J］.物流科技，2013，36(8):96－98.

［5］施彦，韩力群，陈秀新.基于集成协同PSO 算法的车辆路径优化仿真［J］.计算机仿真，2012，29(6):339－342.

［6］何小年，谢小良.带装载量约束的物流配送车辆路径优化研究［J］.计算机工程与应用，2009，45(34):236－238.

［7］江铭炎，袁东风.人工鱼群算法及其应用［M］.北京:科学出版社，2012.

［8］Hu W，Liang H，Peng C，et al. A hybrid Chaos－Particle swarm optimization algorithm for the vehicle routing problem with time window［J］.Entropy，2013，15(4):1247－1270.

［9］Yue Y X，Wen Z B，Yue Q X. Chaos Optimization Algorithm for Vehicle Routing Problem［J］. Advanced Materials Research，2012，538:2722－2726.