基于聚类分析和种子进化算法的车辆路径优化算法

冀德刚，魏俊萍，贾 鹂

（1.河北农业大学 理学院，河北 保定 071001；2.保定市科学技术信息研究所，河北 保定 071000）

1 引言

物流优化方案[1-6]是一个涉及多方面、多系统的组合优化方案，包含客户系统、仓储系统、运输系统等诸多方面的优化。而运输系统优化是物流运输配送过程中的重要环节，也是控制物流营运成本的核心内容[7-12]。如果配送车辆路径合理，不但能够减少送货时间，降低物流成本，同时还能够使客户达到较高的满意度，实现物流管理科学化的目标，因此本文只讨论车辆路径优化问题。

2 VRP模型

为了描述问题方便，定义如下变量：M代表车辆总数，N代表客户数量；Burk代表配送车辆k的最大限载量；Vonk代表配送车辆k的最大装载容积；Carijk代表车辆k从i客户到j客户的配送基础费用（i=1,2,...,N；j=1,2,...,N；k=1,2,...,M）；λTL代表运输延时调整系数（λTL∈[1,+∞]）；CuWi代表客户i的货重；CuVi代表客户i的货物体积。

目标函数表示车辆的总费用等于每辆配送车的总费用乘以惩罚因子，惩罚因子随着运输时间的增长而不断增大，具体大小需要预先设定。惩罚因子较大时，该目标函数转化为带时间窗路径优化函数（本文没有考虑带时间窗路径优化的问题，故在数值计算时λTL=1）。

约束条件：

其中式（4）、（5）保证每个客户的货物都得到配送；式（6）保证每个客户只由一辆车送达货物；式（7）保证一条线路上的所有客户货物总重不超过配送车辆最大载重量；式（8）保证一条线路上的所有客户货物总体积不超过配送车辆最大载容量；式（9）、（10）为约束条件。

3 车辆路径优化算法设计思路

基于物流运输的实际情况，考虑到物流系统优化的诸多要求，把整个优化过程分成两个阶段：

（1）分割区域：考虑到在物流配送中一个特定区域只能由一台车来完成，因此对于一个具体的城市，有必要对整个区域进行划分。首先把每一个指定的客户看成一个二维的点，把区域内的公路看成线，这样通过点与线就可以把整个区域组成一个连通网，把每两点间公路距离定义为两点间距离。其次通过k-means聚类，把近距点划为同一区域，这样就完成了整个区域的划分。

（2）优化方法：使用智能算法对每个区域中的配货路线进行优化，最终形成最优配送方案。具体优化时，先让优化个体在局部区域深度搜索后，再进行聚类分组之间的二次优化，搜寻全局最优值。

两阶段法的设计从实际的物流配送出发，同时在不同区域分别确定局部最优解，然后不同区域间再次优化，很大程度上降低了算法的输入量，使算法的求解速度有效提高。

4 基于聚类和种子进化算法的复合算法

4.1 K-means聚类

K-means算法原理：首先从样本数据中随机选取K个点作为初始聚类中心；其次计算每一个样本到聚类中心的距离（本文使用欧氏距离），把距离每个中心最近的样本点归为该中心所在的类。接下来计算新形成的每一个类中所有样本数据的平均值作为新的聚类中心，直到相邻两次的聚类中心不再发生变化，此时K-means聚类结束[13]。

4.2 种子进化算法(SOA：Seed Optim ization Algorithm)

种子进化算法思想源于豆科植物种子的传播规律。它的整体思路如下：首先把待优化的车辆运输区域看成土地，那么最优值就应该在土地最肥沃的区域取得。在这种思想下，可以用目标函数值来确定每个区域土地的肥沃程度。土地贫瘠，则目标函数值低，土地肥沃，则目标函数值高。显然如果经过传播后的种子所落区域是肥沃土地，那么它生长和传播的机会就会很大；否则，传播的可能性就很小。经过反复搜索，植株会在最肥沃的土地上被找到，此时优化问题的目标函数就取得最优值。这样反复执行的过程经过抽象最终形成一种进化算法-种子进化算法。种子进化算法中散射现象是最核心的部分，整个算法中的搜索机制由散射来完成[14]。

4.3 车辆路径选择的复合优化算法

基于聚类和种子进化的车辆路径选择的复合优化算法（KMSOA:K-Means Seed Optimization Algorithm）设计分为两个阶段：（1）聚类；（2）优化算法求解。其流程图如图1、2所示。

图1 种子进化算法流程图

图2 父种选择流程

KMSOA算法首先把物流运输的区域利用K-means算法进行区域划分，然后计算每个父种对应的适应度函数值，依赖父种的适应度函数值来完成父种的选择和传播，如果满足终止条件则结束，否则生成下一代新的父种，然后再次进行区域划分，反复迭代执行。

5 数值实验

5.1 实验数据

为了验证本文算法的可行性及有效性，实验中采用与文献[15]相同的数据(见表1)，以便进行比较。

表1 实验数据

5.2 实验说明

距离：所有点之间只考虑直线距离，其他情况不予考虑，距离函数采用欧式距离：

KMSOA算法说明：

（1）聚类中K的取值：2到可调度的最多可用车量数。

（2）把优化目标函数定义为适应度函数，即式（3），惩罚因子λTL=1，不考虑时间窗，其中任意两点间的车辆配送费用即为两点间的欧氏距离。

（3）父种类别个数取20。

（4）距离限定标准：避免父类选择为种子的集中分布，距离的限定标准采用每两个种子之间距离的30%。

（5）算法执行最大次数取50次。

5.3 实验结果和分析

为了验证文中给定复合算法的有效性，把文中结果和文献[15]提出的混合遗传算法做比较，独立运行9次，结果见表2与表3。

表2 混合遗传算法求解结果

表3 KMSOA求解结果

表2、表3展示了在相同条件下混合遗传算法与本算法的对比，本文提出的KMSOA算法无论从平均值还是迭代次数来看，均优于混合遗传算法。实验数据再次说明文中给出算法能够降低算法的输入量，提高收敛速度，对物流运输中运输路径优化问题具有一定的可行性和有效性。

[1]F Alffedo,T Montan,R Galv.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computers&Operations Research,2006,33:595-619.

[2]朱志勇,刁洪祥.基于改进遗传算法的车辆路径问题研究[J].湘潭大学自然科学学报,2011,33(3):115-118.

[3]何未雨.物流配送最佳路径的最差-最优蚁群算法实现[J]甘肃科技纵横,2011,40(5):104-106.

[4]BOmbuki,B JRoss,E Hanshar.Multi-Objective Genetic Algorithms for Vehicle Routing Problem with TimeWindows[J].Applied Intelligence,2006,(24):17-30.

[5]姜贵山,姬长虹.周期性车辆路径问题在物流中的应用：案例研究[J].科学技术与工程,2010,10(11):2 694-2 697.

[6]E Taniguchi,N Ando.An Experimental Analysis on Probabilistic Vehicle Routing and Scheduling with ITS[J].Journal of the Eastern Asia Society for Transportation Studies,2005,(6):3 052-3 06l.

[7]G Alvarenga.A Hybrid Approach for the Dynamic Vehicle Routing Problem with Time Windows[A].Proceedings ofthe Fifth International Conference on Hybrid Intelligent Systems[C].2005.

[8]J Y Potvin,Y Xu,I Benyahia.Vehicle routing and scheduling with dynamic travel times[J].Computers&Operations Research,2006,33:1 129-1 137.

[9]宋远卓.物流配送中心搬运设备配置研究[D].成都:西南交通大学,2008.

[10]吕勇.蚁群优化算法及在网络路由中的应用研究[D].杭州:浙江大学,2006.

[11]李晨.基于免疫遗传算法的物流配送VRP问题研究[D].天津:天津理工大学,2009.

[12]胡田田.车辆路径问题的知识表示支持系统研究[D].大连:大连理工大学,2006.

[13]张建辉.K-means聚类算法研究及应用[D].武汉:武汉理工大学,2007.

[14]张晓明,王儒敬,宋良图.一种新的进化算法—种子优化算法[J].模式识别与人工智能,2008,21(5):677-681.

[15]郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学,2002,10(5):51-56.