基于遗传算法的配送中心路径优化研究

任成渝，高贺云，王 霄 REN Chengyu,GAO Heyun,WANG Xiao

（1.西安中车永电捷力风能有限公司，陕西 西安 710018；2.陕西工业职业技术学院，陕西 咸阳 712000）

(1.Xi'an Jieli Electric Power Electronic Technology Co.,Ltd,Xi'an 710018,China;2.Shaanxi Polytechnic Institute,Xianyang 712000,China)

1 研究背景

伴随着物流技术的不断发展，人们对物流的效率问题日渐重视，时间成本成为制约物流发展的主要因素之一。为有效提高物流效率降低时间成本，增加客户对物流服务的满意度，合理安排配送时间是配送中心发展的当务之急，带时间窗车辆路径问题（Vehicle Routing Problem With Time Window,VRPTW）的研究，变得尤为重要[1]。

2 VRPTW模型的构建

在配送路径优化过程中，引入时间窗的概念，不仅可以有效地贴合配送的时间需求，同时在VRPTW问题的研究过程中，成本的设定中，函数表示不仅考虑了运行成本，其中还包括了恰当时间到客户所造成时间等待、以及服务时间[2]。

2.1 基本假设

据实际调研分析，对VRPTW分析过程中进行如下假设[3]：

（1）各需求点的地理位置坐标以及货物需求量已知；

（2）不同的客户同时满足需求且配送时间区间已知；

（3）运输车辆信息已知；

（4）配送过程中各需求点经过有且仅有一次。

2.2 惩罚函数

由实际情况分析，采用软限制时间窗，在客户特定的时间窗基础上，适当扩大配送区间，超出此区间，客户可拒绝签收货物，故设定极大惩罚函数，即p（t），避免超时间窗配送情况的发生，保证配送车辆在特定的时间区间到达[4]。

2.3 数学模型

建立数学模型，主要考虑两方面成本，即时间成本最小和车辆数最少，不仅提高车辆配送效率，同时节省车辆，降低车辆相关的费用。数学模型如下所示：

其中：0表示配送中心，i（i=1,2,3,…,h）为客户编号，s（s=1,2,…,k）车辆编号。事件发生取值为1，否则为0，式（1） 为目标函数，cij表示运输成本，xijs表示车辆s由点i驶向点j；式（2） 和式（3） 中，yis表示客户点i的货运任务由车辆s来完成；式（4）中，qs表示车辆s的最大承重量；式（5）中保证了每个客户点仅能由一辆车完成，而所有运输任务则由k辆车协同完成。

3 案例分析

对蒲城某配送中心10家客户，进行调研分析，各客户的需求量为gi，服务时间ti和服务时间窗口a,［］b以及配送中心与各客户间的距离如表1所示。车辆的载荷为10t，合理优化配送路线使总成本最小。

表1 配送任务特征描述

3.1 算法参数设置

根据本文的模型，在传统遗传算法的基础上选择合适的参数：a：运行单位时间成本取值8；b：启用单位时间成本取值60；P：等待单位时间成本取值0.5；q：延误单位时间成本取值为1.5。遗传算法运行参数L：染色体长度取值50；N：种群规模取值100，pc：交叉概率取值为0.7；pm：变异概率取值0.04；Gen：终止进化代数取值100。车辆载重均为10t，车辆数s=4。

3.2 结果分析

为验证解的有效性，本文对算例进行50次测试取得平均值，并采集实际运行数据进行比较，见表2。

上述遗传算法算例实验结果的最优解为使用4辆车，共生成由4条路径组成的最优配送路径组合，最小成本为12 518元，相比采集数据14 251元提高了13.8%。其中0代表配送中心，其他数字代表客户，其行车方案为：0—2—9—0，0—7—8—0，0—1—3—10—0，0—4—5—6—0。

表2 实验结果

图1 GA多次运行均值收敛图

图1 为运行多次均值收敛图，可以看出，在运行340代时趋于稳定，收敛效果好，运算速度快。

4 结论

本文根据实际调研数据分析，建立带时间窗数学模型，并运用遗传算法求解，通过多次实验选择合适参数，并将计算结果与实际采集数据进行比较，验证所建模型和算法的可行性以及在解决蒲城某配送中心路径优化问题上具有一定优势。