基于k-means聚类和遗传算法求解选址——路径优化问题研究

物流工程与管理

LOGISTICS ENGINEERING AND MANAGEMENT

物流技术

doi ： 10.3969/j. issn .1674- 4993.2017.05.026

基于k -means 聚类和遗传算法求解选址一路径

优化问题研究

□豆训博，李莉

(农业大学机械交通学院，乌鲁木齐830052)

【摘要】文中主要内容包括:一是运用K - means聚类求解共同配送站点选址问题;二是采用遗传算法求解从分拨 中心到需求点的路径优化问题。后者分两个阶段实施：第一个阶段解决从分拨中心到共同配送站点的路径优化；第二 个阶段解决从共同配送站点到需求点的路径优化。通过实例分析和计算求解，结果表明该方法对于解决选址和路径优 化的双重问题具有很好的有效性。

【关键词】k -means聚类；遗传算法；选址-路径优化【中图分类号】F250

【文献标识码】B

【文章编号】1674-4993(2017)05-0071 -03

Solving Location - based k - means Clustering and Genetic Algorithm Research on

Path Optimization Questions

□ DOU Xun -bo，LI Li

(School of Mechanics&Transportation,Xinjiang Agricultural University,Urumqi 830052,China)

【Abstract】 The main contents include the use of K - means clustering One common distribution site location problem

solving；the second is the use of genetic algorithms path from a distribution center to demand point of optimization problems. The latter two phases：the first phase from distribution centers to resolve common distribution sites path optimization；the second stage to solve optimization from a common distribution point of the site to the needs of the path. Through case analysis and numerical solution, the results show that the method for solving the dual problems of location and route optimization has good validity.

【Key words 】k 一 means clustering; genetic algorithm; location — path optimization选址-路径优化问题(LRP)实质是LAP和VRP的集成， 包括共同配送站点选址和服务分配问题（LAP)、路径优化问 题(VRP)、配送车辆容载量和配送时间约束等进行多决策分 析。目前，在选址-路径优化方面，李波，邱红艳提出和设计 了模糊聚类求解车量路径优化，并运用遗传算法求解方法的 有效性;蒋波提出并采用遗传算法求解带时间窗的路径优化

问题;张潜，高立群提出采用聚类和遗传算法求解MVRP路径 优化问题;孙焰，李云峰提出采用两阶段法求解配送中心选址 问题。但当前对选址一路径优化问题的研究较少，尤其是带 时间窗的选址一路径优化研究方面，国外已经做了许多详细 且深人的研究，取得了一些有实用价值的成果，甚至进行了一 些实际的应用并取得了很好的效果。而国内对此研究较少， 实际应用效果不显著，因此我们有必要做深人研究。基于此， 本文提出从整个配送过程求解选址一优化问题的综合算法， 以弥补上述不足。1 K-means聚类模型建立和求解流程1.1建立K - means聚类模型数学模型

已知模型样本集I幻有™个样本和*个模式分类I ~，j+ =

1,2,…幻，以每个模式样本到聚类中心的距离之和达到最小 为目标，建立聚类问题数学模型为：

minE E T；,- \\\\X-mj\\

；=lA e ^>；

(1)

(2)⑶

S.

t

.

;. = 1

iy,=l(J=l,2,-,«)

Xy..

i y ijx (ij =1，2，…，K)

mj = 「1，如果样本i分配到聚类中心_；+上

yd

〇,否则 ⑷

式中，式（1)表示目标函数;式（2)表示模式样本只能分 配到一个聚类中心上;式（3)表示求解样本的均值向量公式; 式(4)表示&为0-1变量，&取1时，表示样本*分配7+聚类 中心上，否则取〇。1.2

Kmeans聚类算法流程

k - means算法的求解步骤如下：①任选A个初始聚类中心:c!，c2,...，ct;

一

【收稿日期】2017 -02 -16

【作者简介】豆训博（1991 一），男，河南商丘人，硕士研究生，研究方向：交通运输管理与物流工程。

李莉（1973—），女，陕西西安人，博士，副教授，研究方向:农产品物流，供应链管理。

72②

物流工程与管理

逐个将样本集(X)中的各个样本按最小距离原则分配

k - \\e - Q

第39卷

给&个聚类中心某一个C;.;

③ 计算新的聚类中心C； (j = 1，2,…A)即< 1E X其\\ ■ X BSj，中％表示第J+个聚类中心包含的样本个数；

④ 若< # c, 〇+ = 1，2，……，A；)，转步骤（2);否则算法收

(e = l,2,...，l)

Q, (A = 1,2,……，K)

(5)(6)(7)(8)

iiAw^i = 〇e = 0

T0k +

e = Ot = 0

+/J

(* = 1,2,……，K) (* = i,2,……,i)

敛，计算结束。

2

遗传算法

遗传算法又称GA( Genetic Algorithm)算法，它是模仿自 然生物进化机制发展起来的依据自然环境下优胜劣汰、适者 生存的遗传法则所形成一种的全局搜索优化算法。从一个具 有潜在优化问题的种群开始，种群由一定数目基因编码的个 体组成，基因编码成染色体，染色体构成每个个体。开始时，产 生一定量的初始种群，按照适者生存和优胜劣汰原则，逐渐演 化产生适应度越来越高的个体。借助于自然遗传学的交叉、变 异算子，对适应度高的个体进行交叉、变异操作，使其产生下一 代新种群，使其具有更高的适应度，适应环境能力更强。

遗传算法求解过程如下：① 构造足够量的染色体。从实际问题出发，对染色体进 行编码操作，尽可能在满足实际问题约束下进行染色体编码。②

随机产生初始化种群。在完成染色体编码以后，一个初始种群作为起始群，首先需要确定初始化种群数量，一

般情况下种群的数量视需求点的大小而确定，取值范围一般 在100 ~ 300之间。

③ 计算每个染色体适应度。适应度是反映染色体优劣的

惟一指标，遗传算法是为了寻求适应度最大的染色体，本例中 以配送距离最小值/为目标，取= (1//)，表示适应度函

数为配送距离的倒数，即目标函数值越小，对应的染色体进人

下一代的概率越大。

④

采取选择、交叉和变异等遗传算法基本操作来更新群

体。三大算子贯穿于基本操作整个过程，也体现了优胜劣汰 的自然规律。其中选择操作主要是从旧群体中以一定概率选 择个体到新群体中，个体被选中概率跟适应度值的选取有关， 个体适应度值越大，被选中的概率越大;交叉操作采用部分映 射杂交方式进行，变异主要是产生的后代染色体适应度不高 情况下，采用反转变异的方式对染色体中不同位置进行反转， 以提高染色体的适应度。

⑤ 重复步骤(3 )、(4)直到满足实际问题约束条件并保持 到一定的代数时结束运算。3

模型的建立

通过上述分析，以配送距离最小化为目标函数，建立带时 间窗第一个阶段路径优化问题的数学模型如下：

minf^e.i.k) = k = le =0i =0

X ZZueiweik

(i)

«X = 11' =L 1^eik^K (e =〇) (2)

t - 1

t - 1

矣 1

〇-

0，\"-1，2，...…，\"）(3),X X3认-1 0-1,2,.......，n)

(4)

k = le =0

(E |0，1 } (e，i =1,2,...，〇，〇 =1,2,....，尺）（9)式中，/表示分拨中心需服务的共同配送站点数量;e，*表 示单个共同配送站点，e，* = (〇，1，……，），u=〇代表分拨中 心;表示各车辆数;〜:从配送站点e到配送站点*的运输距 离;认：车辆的最大载重量;配送站点；的需求量，且max< 矣ft 车辆A到达配送站点*时的时刻心：车辆从配送站点

^行驶到配送站点*的时间，其中车辆完成配送站点 任务所需的服务时间（停留时间）；》«;；[为〇 - 1变量，当车辆 从

e点行驶到点i时(i<7+)，否

则=〇。

式（1)表示最小化配送距离;式（2 )表示从分拨中心出发

的车辆数不超过&式(3)表示每辆车均从分拨中心出发并最

终返回分拨中心；式(4)、（5)表示每个配送站点恰好被一辆

车访问一次;式(6)表示每辆车所承担的任务总和不超过车辆

的载重量;式(7 )表示车辆出发时间和返回时间均在规定 的时间窗内;式(8)表示车辆从配送站点e到达配送站点*的

时间约束;式(9)表示整数化约束，％只能取〇或1。同 理，以配送距离最小化为目标函数，建立带时间窗第二个阶段

路径优化问题的数学模型：

mmf2(i,j,k) = AE： = l；i=〇

t=〇 1 1(10)

«1 = 11/ = 1

(*=0)

(11)

%^ijk = (i=0，k = l，2,...，k)

(12)X \\^ijk = 1 G = l，2,...，n)

(13)AX： = 1 i = 〇=1 (J. = l ,2,...，n)

(14)t = 〇/' = 〇

(k=l,2,……，K)

(15)Tt +|〇1〇^(%+/;)^^ (* = 1,2,……，尺）

(16)(Si+fi+tij) = Sj 〇' = 1 ,2,...，n)

(17)

hE!0，1! (i，J' = l，2,...，n) (k = 1,2,....，尺）（18)式中，《表示共同配送站点需服务的需求点数量;表示

单个需求点，i，J+ = (0,1，....，A〇 i，J+ =0代表共同配送站点；A表示各车辆数;:从需求点*到需求点7的运输距离；:车辆灸

到达需求点*时的时间;％ :车辆从需求点*行驶到需求点J的 时间，其中:车辆完成需求点*任务所需的服务时间（停 留时间）;>为〇 -1变量，当车辆A从*点行驶到点J时（*# j+)，*#，否则 v =〇。

式(10)表示最小化配送距离;式(11)表示从共同配送站点 出发的车辆数不超过&式(12)表示每辆车均从配送中心出发 并最终返回配送中心;式（13 )、（ 14)表示每个客户点恰好被一

产生 第5期豆训博等:基于k - means聚类和遗传算法求解选址一路径优化问题研究

73

辆车访何一次;式（15)表示每辆车所承担的任务总和不超过车 辆的载重量;式(16)表示车辆出发时间和返回时间均在规 定的时间窗内;式(17)表示车辆从需求点〖到达需求点_/的时 间约束;式（18)表示整数约束，~只能取0或10 4

实验计算与结果分析

本文以乌鲁木齐社区蔬菜直销点统一配送为例，有2个 分拨中心，20家社区蔬菜直销点作为需求点，其位置如图1所 示，要求合理安排配送车辆，使配送距离最小《

0 10 20 30 40

里程/百米

50 60 70 80 90 100

图1需求点和分拨中心位置

首先，基于K - means聚类进行分析，即对20家社区统一 酉己送：求点进行K - means均值分析，求解出4个聚类中心作 为共同配送站点进行配送作业活动，求解结果见表U

表1

K - means聚类结果

聚类号

3

41 ( 67，57 ) 2

4 ( 84, 45 ) 6

7(47,30)

聚类

(47,43)3(57, 16(9,29)

(87,36)9(88,

10(52,21)数据

42)5(77,41)8 18(15,24)

30)11(87,18)( 68, 30 ) 19 20(15,48)

12(80, 14) 1315(39,21)(,22)

(94, 15 ) 14

17(40,29)(93,17)

聚类中心 (63,39)(13,34)(88,25)(45,25)

配送曇

1630

730

1075

1020

然后，采用遗传算法求解路径优化问题，每个分拨中心拥 有载重量2吨的汽车5辆，每个共同配送站点拥有1吨的汽 车5辆，负责20家社区蔬菜直销点的配送作业任务，求解结 果如表2和表3所系。

第一阶段，从分拨中心到聚类中心的路径优化如表2 所示。

表2

从分拨中心到共同配送站点路径优化结果

分拨中心

坐标个:辆数优化路径

配送距^离0307.2443081

(92,61)

3

042017.59320107.2802030

12.6063482(25,27)302406.7234010

7.97

从表2可知，分拨中心1对共同配送站点1、3进行配送 活动，配送车辆数为2,分拨中心2对共同配送站点2、4进行 配送作业，配送车辆数为1。

第二阶段，从共同配送站点到所配送区域内的需求点的

进行路径优化，如表3所示d

表3

共同配送站点到需求点的路径优化结果

配送

站点坐标

车辆

数优化路径

实际路线配送距 离（km)0-2-3 -0

3.3251(63,39)302304016500-5-02. 82840-1-19-8-07.28072(13,34)1023100-18 -20-16 -06.05260 -12 -9 -14 - 3

(88,25)

2

0537624010

13-6-11-0

9.48610-4-04.07924(45,25)20304120

0-15-0 1.44220-17-7-10 -0

3.1832

根据以上表2和表3配送情况，最终配送路径优化结果 如图2所示。

图2

配送路径优化结果

5

结论和建议

本文讨论了把K - means聚类和遗传算法相结合的方式， 对选址一路径优化问题进行了研究。并以乌鲁木齐社区蔬菜 直销点统一配送为例，求解出了较优的配送路线结果w下一步笔者将考虑从两个方面进行改进，一是借助于地 理信息系统（GIS)更精确地进行聚类分析;二是对本文算法进 行改进或替换，比如使用改进遗传算法、神经网络算法等，并 期望相关的研究结果更符合现实情况和对相关的物流配送企 业有更大的参考价值。

[参考文献]

[1] 张潜，高立群，等.物流配送路径多目标优化的聚类-改

进遗传算法[J] .控制与决策，2003,18(4) :418 -422.[2] 孙焰，李云峰.物流中心选址的两阶段法研究[J].物流

科技，2006,29(129):41 -44.

[3] 安立军.遗传算法在物流配送车辆优化调度中的研究及

应用[D].上海:上海海事大学，2007.

[4] 杨斌，万芳瑛.TSP问题解决的遗传算法[J].大众科技，

2008(12) ：56 -58.

[5] 蒋波.基于遗传算法的带时间窗车辆路径优化问题研究

[D].北京：北京交通大学，2〇10.

[6 ]李波，邱红艳.基于双层模糊聚类的多车场车辆路径遗传

算法[J].计算机工程与应用，2〇14,50(5):261 _2.