遗传算法在物流配送中心选址15

遗传算法在物流配送中心选址 和车辆调度问题中的应用

物流是一个非常具有实际意义的问题，很长一段时间都是诸多学者研究的热点。对于物流中的诸多问题，特别配送中心选址和车辆调度问题，他们应用各种优化方法对其进行规划，做了多方面的研究。配送中心选址和车辆调度问题对一个企业来说是至关重要的，解决此问题主要包括有：启发式算法，虽然它规则简单，计算速度也很快，但它的不足在于解决问题的准确性较差，因此，它通常用于那些对于计算精度要求不高的方案；混合整数规划方法，它具有较好的收敛性和准确性。但由于这种算法在配置模型中存在太多的假设条件，以至于限制了它的应用范围；遗传算法，它具有整体优化的能力，同时适合于许多不同的模型，因此它是一种合适的选择。

本文就是运用遗传算法将选址和车辆调度两个方面的问题综合在一起讨论，在只知道需求点分布的时候，综合考虑各类费用以及配送便捷的基础上建立物流配送中心选址模型，用标准遗传算法对该模型求解，问题即可得到有效的解决，找出配送中心的最佳位置。然后再根据已确定的配送中心和需求点位置来制定车辆路径。在解决车辆优化调度问题时，本文综合考虑了各种成本费用，建立了适合物流配送模糊车辆调度问题的数学模型，同时采用期望值选择法，将爬山法与遗传算法相结合，从而构成混合遗传算法，使解决该问题快速地搜索到满意的结果。结合以上两种模型，同时解决这两方面的问题，使其更加具有完整性和适用性。

1物流配送中心选址和车辆调度问题阐述

物流配送中心选址主要因素及费用与物流配送[1，2]基本相同，主要包括：车辆费用，驾驶员工资（正常工作时间）和补助（加班费），车辆等待费用（提前到达客户，车辆需要等待），但对于选址，需要考虑配送中心建设费用和货物的存放费用。

限制条件：

1）所有路径均起始于配送中心，并要求返回配送中心；

2）每一个客户只由一辆车送货；

3）每个客户都有一个非负的货物需求量，并且经过该客户的配送路径货物总需求量不能大于配送车的载货量；

问题假设主要如下：

配送中心建设费用为W，坐标为(X0Y)，客户总数为 l ，其坐标为,0(Xi,Yi),i1,2,…,l，第i个客户需求量为 gi ，卸货时间为 ti1，配送中心和客户的预约时间为 ti2，配送中心与客户或者客户与客户之间的最短距离为 dij(i,j0,1,2,…,

l)，车辆的平均车速度为 vij(i,j0,1,2,…,l），每公里车辆的费用的为

cij(i,j0,1,2,…, l)，车辆种类为m，第p类卡车车辆数为 np ，载货量为 vp ，车辆等待费用每小时为 r ，正常工作时间 t3加班时间 t4pg 时司机的工资为每小时s1，pg 时的补助为每小时s2，车辆需要返回配送中心，Z表示车辆总费用，另

xijpg1,车辆pg经过路径(i,j)1,车辆pg给客户i送货，yipg 0,车辆pg未经过(i,j)0,车辆pg没有给客户i送货2标准遗传算法解决配送中心选址问题

标准遗传算法的基本思想和基本步骤在上文中已经详细的论述，但在实际问题中，其具体操作却有着不同的地方，对于选址问题，主要方法和步骤[3-5]如下： 第一步：选址数学模型

根据题目我们有： 车辆行驶的费用为：i0ldcxj0p1q1mlmnpijijijpg （3.1）

驾驶员的费用（工资和补助）为：p1(tq1np3pg1 s4pgs2) （3.2）

由此建立物流配送中心选址问题的数学模型：

minfi0ldcxj0p1q1lmnpijijijpgp1m(tq1np3pg1 s4pgs2)W （3.3）

（配送中心选址考虑的费用）

s.t.

yp1q1mnpipg（3.4） 1 保证任一客户i只由一辆车来送货

gi1li 保证任一车辆送货量不大于载货量 （3.5） yipv pg优化目标：找出配送中心选址所需费用最小时的(X0,Y0)

第二步：编码方案

若需要选定m个配送中心，则染色体需要由2m个浮点数排列组成：

gX1,Y1,X2,Y2,…Xi,Yi,i1,2,…,m，其中Xi,Yi表示第i个配送中心的地址坐标，一个染色体所包含的m个地址就是配送中心的选址的一个方案。如，对于本文，只需要一个配送中心，则染色体为X,Y。

第三步：初始种群

在配送区域随机产生一系列地址点Xi,Yi，构成N个个体，构成初始种群，

G0g1,g2,…,gN(其中gX1,Y1,X2,Y2,…Xi,Yi,i1,2,…,m),并作为遗传迭代的第一代。

第四步：适应度函数

遗传算法的一个特点是它可以使用所求问题的目标函数值即可得到下一步的有关收集信息，而对目标函数值的使用是通过评价个体的适应度来体现的。适应度是群体中个体生存机会选择的唯一确定性指标，所以适应度函数的形式直接决定了群体的进化行为。为了直接将适应函数与群体中的个体优劣质量相联系，在遗传算法中适应度规定为非负，并且在任何情况下总是越大越好。配送中心选址模型问题所建立的目标函数式（3）是求最小值，则适应度函数可采用

2.4

式

Cmaxg(x),当g(x)Cmax，定义如下： f(x)0,其他情况Cmaxf(x),当f(x)Cmax， （3.6） F(x)0,其他情况Cmax可以取当前出现过的最大值。

第五步：选择算子

对于浮点数编码，我们宜根据个体的适应度大小从大到小排列个体，重排后的个体g1适应度最高，性能最优。根据排序决定每个个体复制到下一代的概率pi，用轮盘赌法复制L个个体，进入下一代，代数增加1。

第六步：交叉算子

采用与二进制相似的单点交叉。在二进制单点交叉中，只需要将交叉点对应的元素进行交换，浮点数编码的单点交叉与此相同。如

11父代个体X1,Y11,X2,Y211.2,5.0,6.1,8.2， 2父代个体X12,Y12,X2,Y225.1,2.6,4.3,5.4

交叉点为3，则交叉过后，子代个体为

3X13,Y13,X2,Y235.1,2.6,6.1,5.4 4X14,Y14,X2,Y241.2,5.0,4.3,8.2。

在设定交叉概率pc后，从群体中随机选出Npc个个体进行两两交叉，从而得出新的个体。

第七步：变异算子

变异操作以概率pm对染色体群中的某些染色体的某些位进行变异，产生新的个体染色体，作为交叉运算的补充，变异操作可能增加方案的多样性，克服求解可能出现的早熟和陷入局部最优解的现象，变异概率pm取不同的值对算法性能的影响很大，

pm过大，求解时间会明显增加，但算法收敛于局部最优的可能性减少。

第八步：算法停止准则设计

淘汰不符合约束条件（4）（5）的染色体，同时，在每一代产生的染色体当中，计算出个体的最大适配值fmax和最小适配值fmin，若|fmaxfmin|（为停止准则参数），则回到第五步，继续进行遗传操作，否则就输入最优结果，停止计算。

3混合遗传算法解决车辆调度问题

在解决车辆调度问题时，本文在标准遗传算法的基础上，采用了期望值选择方法，并且将爬山法和遗传算法相结合，从而构成求解该问题的混合遗传算法，其主要步骤

[6-8]

如下：

第一步：车辆调度数学模型

车辆调度需要考虑的因素与配送中心选址基本相同，但，不需要考虑配送中心建设费用，并且需要增加考虑车辆等待费用。故，我们可以建立如下车辆调度模型：

minZi0ldcxj0p1q1mnplmnpijijijpgp1m(tq1np3pg1（车ss2)rmax(ti2ti1,0) （3.7）

4pgi1l辆的总费用）

s.t.

yp1q1ipg1 保证任一客户i只由一辆车来送货

gi1li 保证任一车辆送货量不大于载货量 yipv pg优化目标：车辆的总费用最小。

第二步：编码方案

根绝物流配送问题的特点，物流中的车辆调度问题适宜采用自然数编码。首先根据货物的总的需求量C=gi，每辆车的平均载货量vp，计算出需要车辆的数目n＝

i1mgi1mivp。根绝自然数编码的原理我们可以产生1，2，3，…，l，l1，…，ln1的

自然数排列，其中1，2…，l为客户序列，l1，…ln1为n虚拟配送中心，n为所需的车辆数。

第三步：初始种群

在通过自然数编码产生的排列当中，我们随机选择n个符合约束条件（6）（7）的排列作为初始个体，构成初始种群。例如用4辆车向7个客户送货，设某个排列为1，3，8，2，6，9，4，7，10 ，5，它表示4条路径0-1-3-8-0，0-2-6-9-0，0-4-7-0，

0-5-0，其中的0表示配送中心。若每一条路径上客户的需求量之和均小于车辆的最大载货量，则选择改排列作为一个个体；否则，则不能选此个体作为个体。并输入控制参数（交叉概率，变异概率，群体规模，最大运行代数）。

第四步：适应度函数

自然数编码能够很好的保证每一个客户所需要的货物只由一辆车配送，但不能保证交叉变异以后的个体满足条件，故给予一定的惩罚。令

Mmax{giyipgvp,0}，保证客户i的需求量不大于给它送货车辆的载货量。

i1lM0gi,(i1,2,…,l), 表示所有客户对货物的总需求量。

i1l若取惩罚权重为10/M0，则染色体的适应度函数可以定义为：f

第五步：选择算子

1

Z10M/M0 在物流配送的车辆调度问题中，我们采用期望值方法可以得到比较好的结果，根据式子2.14，群体中每一个个体在下一代生存的期望数目为Mnfi/fi，并且，

i1n被选中参与配对和交叉的个体在下一代的生存期望为该个体生存期望减去0.5，未被选中的个体在下一大的生存期望为该个体生存期望减去1，但需要注意的是，个体生存期望为小于零的不参与配对和交叉。

第六步：交叉算子

对于自然数编码个体，根绝前面2.5.2节所讲述的循环交叉算子（CX，cycle crossover）的方法，我们可以很容易由父个体产生出子个体。

变异算子和算法停止准则的设计与配送中心选址中的变异和停止准则设计相同。

4算例

某牛奶公司在一城市中有12个销售点，销售点的需求量，位置，以及卸货时间如表3.1所示。送货车辆有两种，A类载货量为500箱，没公里车辆费用为3元，B

类载货量为400箱，每公里车辆费用为2.5元。驾驶员正常工作时间内的工资为每小时10元，加班补助为每小时20元。设最早发车时间为早上6：00 。

1）试确定一个配送中心的地址（配送中心建设费用为1.5万元，并且范围坐标为（1000，1000）），使目标函数值最小。

2）确定配送中心地址后的车辆调度方案，使目标函数值最小。

表3.1 销售点坐标及需求表

客户 1 2 3 4 5 6 7 8 9 10 11 12 牛奶箱数 120 200 120 150 140 60 110 180 90 60 140 150 客户位置（km） X坐标 30 40 48 52 92 92 94 108 44 20 108 130 Y坐标 114 36 96 120 154 66 100 100 160 54 32 88 卸货时间 （min） 60 90 60 80 70 40 60 90 50 90 60 70 预约时间 ti2 7：30 7：30 7：30 7：30 7：30 7：30 7：30 7：30 7：30 7：30 7：30 7：30

1、 配送中心选址模型为（3.3）式，在matlab6.5环境下编程可实现此例中配送中心地址的寻找。其控制参数如下：

N = 12 %种群规模 n = 1 %配送中心个数

l12 ％销售点数目

B = 0 1000 0 1000 ％配送中心边界范围

M = 1000 ％最大迭代代数

pc＝ 0.85 ％交叉概率

pm＝ 0.05

％变异概率

Cmax＝1.0×105 ％固定最大值 W = 15000 %配送中心建设费用

运行程序，得出配送中心的坐标为（60，140），目标函数值为17532.54。 2、配送中心确定后，我们可以根据dij(XjXi)2(YjYi)2，(i0,j1,2,…,12)计算出各销售点与配送中心的距离。同时我们可以看到各个销售点的总需求量为1620箱，按照车辆调度问题中编码的办法可以计算出共需要4辆车（

162016204），500400因此求解出来的方案应该为1—15（13，14，15为虚拟配送中心）的一个排列。设定群体规模为N＝20，交叉概率pc0.85，变异概率pm0.05，最大运行代数为1000代。

在

matlab6.5

中运行，其结果显示最优染色体为

3—2—10—13—5—8—15—7—12—6—11—14—9—1—4，A,B类车各需要2辆，总费用为2725.98元。具体运行情况见下表3.2。

表3.2 车辆调度情况

序号 1 车型 A 车辆容量 /实载量（箱） 500/480 车辆路径以及收发车时间 0(6:35)—3(6:30)—2(9:05)—10(11:35) —13/0(13:57) 2 B 400/320 13/0(6:41)—5(7:30)—8(8:51) —15/0(10:55) 3 A 500/460 15/0(6:28)—7(7:30)—12(8:56) —6(10:58—11(12:23)—14/0(14:33) 4 B 400/360 14/0(7:00)—9(8:00)—1(10:05)—0(11:31) 395.39 1054.58 382.69 总费用 （元） 892.32

3、结论

本题主要在考虑到降低成本的基础上，建立了近似于现实生活中的物流活动的数学模型。采用了SGA解决选址问题，在解决车辆调度问题时，采用了期望值选择法，将爬山法与GA结合起来构成HGA,，克制了传统选择法带来的统计误差和局部搜索能力差的特点，提高了解的精度。

参考文献

[ 1] 封全喜,刘诚.基于混合遗传算法的物流配送模糊车辆调度问题的研究.长沙交通学

院学报,2005.9.

[2]CHEN Qing-Geng, WANG Ning,, HUANG Shao-Feng. The Distribution Population—based Genetic Algorithm for Parameter optimization PID Controller.ACTA AUTOM ATICA SINICA,vol.31,No.4,July,2005。

[3] 陈火根,丁红钢,乘耀东.物流配送中心车辆调度模型与遗传算法设计.浙江大学学

报,2003.9.

[4] QIAN Jing, PANG Xiao-hong, Zhi-ruing. An Improved Genetic Algorithm for

Allocation Optimiiation of Distribution Centers. Journal of Shanghai Jiaotong University(Science),Vo1.E-9,No.4,2004,73～76.

[5] LUO Pi, Li Qiang, GUO Jl-cheng, TENG Jian-fu. Improved Genetic Algorithm and Its

Performance Analysis, Transactions of Tianjin University. vol.9, No.2, Jun.2003. [6] 玄光男[日],程润伟.《遗传算法与工程设计》.北京:科学出版社,2000.1:37-42 [7] ZHAO Yong-ming, ZHANG Su, XIAO Chang-yen, CHEN Ya-zhu. A hybrid genetic

algorithm for multi-modal image registration, Journal' Harbin Institute of Technology (New Series),Vo1.13,No.1,2006.

[8] FANG Lei, ZHANG Huan-chun, JING Ya-zhi. A New Fuzzy Adaptive Genetic

Algorithm. Journal of Electronic Science and Technology of China, Mar.20059 。