基于遗传算法物流配送最佳路径问题研究

王伟夏 康洪波 吴光雨 杨冀祥 张 进

(河北建筑工程学院，河北 张家口 075000)

1 引 言

随着社会的发展，物流行业水平的提高，物流配送的效率成为整个物流行业的焦点.物流配送的效率一方面决定着配送成本与经济利益相关；另一方面也会影响客户的置信度，与企业社会效益相关.因此构建智能化的最优物流配送体系具有重要的意义.

物流配送是指根据用户的订货需求和配送货物车辆的相关数据，以物流配送成本最优化为目标，确定配送货物的车辆以及该车辆的行驶路线.问题的核心是在一定的限定条件下，如何确定车辆的数目和车辆的行驶路线，使得物流配送路径最佳，物流配送成本最小.

本文依托第十一届中国大学生服务外包创新创业大赛企业命题A12号赛题所提供物流问题，通过建立物流配送最佳路径的数学模型，采用遗传算法对配送路径进行优化，得到最佳路径.同时，为加强算法的收敛性和鲁棒性，对初始种群进行优化改进，提高了交叉和变异的效率.

2 物流配送最佳路径的数学模型

赛题给出物流问题图形表示如图1所示.问题描述为：图1所示为设定配送网络，P为配送中心，其余A-I为客户的接货点，所有客户的位置距离固定，各边上的数字为公里数，括号内的数字为各需求点的需求量，单位为吨.假设配送中心有限重为2吨和5吨的两种类型货车，并制约车辆一次配送路线距离不超过35公里，总时间不能超过8小时.每个派送点只由一辆车服务一次，每辆车只能服务一条路线，车辆一律由配送中心出发，配送完所有货物后返回配送中心，求需要的车辆数，最优路径及配送时间.

图1 物流问题图形

根据对赛题的分析可知，本赛题的物流配送最佳路径问题可以描述为：从单一起点出发，配送多个终点后再回到起点，每个需求点的位置和需求量一定，根据车辆数量、承载限制、运行里程限制、运行时间等条件选择最优运输路径，使成本最小化，配送订单最大化，并满足以下条件：

(1)每条分配路线上总需求量不高于货车的载重量.

(2)每条分配路线的行驶长度不高于货车单次最远行驶距离.

(3)每个配送点只由一辆车服务一次，每辆车只能服务一条路线.

(4)若两配送点之间不可达，返回配送中心再向另一配送点进行配送.

基于以上优化目标和约束条件，研究并设计了物流配送最佳路径的数学模型.

用一赋权有向图G=(R,E,d)来表达搜索配送顺序模拟路径.R={R0,R1,…Rn}为所有需求点集合.R0为配送中心，R1,R2,…Rn为所有需求点.E={(Ri,Rj)|Ri,Rj∈R;i≠j}为虚拟路段集合.假设配送中心共有V辆车，Qk(k=1,2,..V)表示车辆k限定载重，M为所有车辆单次最远行驶距离.dijk为车辆k从Ri到Rj的距离.货物需求点Ri给定了需求量qi.建立物流配送最佳路径的数学模型：

决策变量

s.t.

上述模型中，(1-1)为目标函数；(1-2)、(1-3)为决策变量；(1-4)为车辆一次运行路线小于货车配送的最远行驶距离；(1-5)为分配路线上总需求量不高于货车的载重量；(1-6)、(1-7)为每个配送点只由一辆车服务一次；(1-8)每辆车只能服务一条路线；(1-9)由配送中心出发服务完所有规定路线后返回配送中心，形成回路.

3 最佳物流方案遗传算法初始种群设计及改进

3.1 初始种群构建

根据数学模型，本问题初始种群采取随机生成路径的方法.

首先根据题意构建配送网络二维数组itemList，如下所示.

itemList=[[0,'P',12,8,0,0,0.0],

[1,'A',10.3,9.7,1.7,1,0.085],

[2,'B',8.4,9.5,0.8,1,0.085],

[3,'C',7.5,8.2,1.3,1,0.085],

[4,'D',8.5,6.5,2.8,1,0.085],

[5,'E',11,6.2,1.9,1,0.085],

[6,'F',15,6.5,3.5,1,0.085],

[7,'G',13.8,7.8,0.9,1,0.085],

[8,'H',15.2,9.3,0.3,1,0.085],

[9,'I',12.3,10.3,1.2,1,0.085],

[10,'O',10,7.2,0.0,0,0.0]]

数组共有11行，第一行表示物流中心，最后一行表示转折点路线，其余行为配送点；每一行第一列为序号；第二列为配送点或物流中心名称；第三列和第四列为通过网络图形距离值解构出的模拟坐标值；作为仿真绘图的依据；第五列为配送点货物量；第六列为卸货次数；第七列为卸货时间.

同时还设定了一个距离矩阵dis，如下所示.

dis=[[0,5,8,7,∞,4,12,9,12,6,5],

[5,0,4,∞,∞,∞,∞,∞,∞,3,∞],

[8,4,0,3,∞,∞,∞,∞,∞,∞,∞],

[7,∞,3,0,4,∞,∞,∞,∞,∞,5],

[∞,∞,∞,4,0,3,∞,∞,∞,∞,2],

[4,∞,∞,∞,3,0,10,∞,∞,∞,2],

[12,∞,∞,∞,∞,10,0,4,7,∞,∞],

[9,∞,∞,∞,∞,∞,4,0,5,∞,∞],

[12,∞,∞,∞,∞,∞,7,5,0,9,∞],

[6,3,∞,∞,∞,∞,∞,∞,9,0,∞]

[5,∞,∞,5,2,2,∞,∞,∞,∞,0]]

设定初始车队共有12辆车，载重2吨的为6辆[0～5]，载重5吨的为6辆[6～11].初始种群构建流程为：首先遍历配送点，从第一个配送点开始，依次为配送点分配车辆.为每一个配送点分配车辆时流程如图2所示，随机生成一辆车，将该点货物放入该车，计算该车载重量是否超重，如果超重，退出重新分配车辆，如果不超重，计算该车的行驶里程数，包括三个方面：①从物流中心出发的，包括该车已送达货物的所有配送点的里程数的和；②该车到达的上一个配送点至当前分配的配送点的里程数；③当前配送点回到物流中心的里程数.当这三个里程数之和不超过额定总行驶路程时，分配继续，否则，退出本次循环，重新分配.

图2 算法流程图

如果里程数满足条件，进入继续分配环节，进一步校验行驶时间是否满足条件，校验过程和里程数校验一致，分为三个方面：①从物流中心出发的，包括该车已送达货物的所有配送点的所用时间的和；②该车到达的上一个配送点至当前分配的配送点所需的时间；③当前配送点回到物流中心所需的时间.当这三个时间数之和不超过额定时间数时，分配完成，否则，退出本次循环，重新分配.

根据以上的算法设计以及相应的代价函数得到以下初始种群路线以及该路线所需要花费成本(随机运行两次结果)，图中数组中为空的表示该辆车未分配，依次为第0辆车送第4个配送点和第9个配送点的货.

3.2 初始种群优化

从图3可知，目前初始种群的构建存在两个问题，第一：中间有经过物流中心的情况；第二：由于分配过于分散，所以占用车辆过多，每辆车的满载率低，造成代价值很高.因此，需要对初始种群进行优化.

图3 初始种群构建图

优化分为两个方面：第一，校验本次路径分配方案中每一辆车中除首尾为0时(0表示物流中心)，如果还存在0，则该路径丢弃；第二，对于第二个问题，解决办法为，在设定的n个初始路径中，对每辆车进行满载率评定，只要某个路径中存在三辆满载率小于50%的车辆，则该路径丢弃.

4 仿 真

仿真数据初始种群数为1000，进化次数为100，设置种群中最优概率为0.3，即种群前30%为最优，弱者存活率0.5，变异率0.1.

选择运算：根据计算成本从小到达进行排序，选定前500个所为方案路径，再从中选出前30%适应强的染色体添加到parents中，剩余70%数据中根据0.5的弱者存活概率查找幸存染色体添加到parents中，得到parents.

交叉运算：根据选择运算生成的parents进行交叉，生成两个随机数k从parents中寻找两个父节点，随机生成两个随机数确定交叉片段，最后得到children.

变异运算：根据交叉运算生成的children进行变异，以0.1的变异率生成三个随机数进行交叉最后形成child.

根据以上设定进行仿真，仿真次数两次，遗传算法结果如下图4和图17所示。(图5-16为第一次仿真单个车辆具体路线图，图18-29为第二次仿真单个车辆具体路线图)

图4 遗传算法第一次仿真结果图

图5 车1路线图 图6 车2路线图 图7 车3路线图

图8 车4路线图 图9 车5路线图 图10 车6路线图

图11 车7路线图 图12 车8路线图 图13 车9路线图

图14 车10路线图 图15 车11路线图 图16 车12路线图

图17 遗传算法第二次仿真结果图

图18 车1路线图 图19 车2路线图 图20 车3路线图

图21 车4路线图 图22 车5路线图 图23 车6路线图

图24 车7路线图 图25 车8路线图 图26 车9路线图

图27 车10路线图 图28 车11路线图 图29 车12路线图

5 总 结

仿真结果表明，依据物流配送最佳路径的数学模型，以改进的遗传算法，可以快速有效地求得物流配送最佳路径优化问题的最优解.而根据实际问题对遗传算法优化，可以有效地提高遗传算法的收敛性和鲁棒性.