其中， 表示第p辆车的行车时间， ； 为发车时间， 为收车时间； 表示第p辆车的加班时间， 。
3．车辆调度遗传算法案例
3.1问题描述
处理过的塘沽物供中心的数据如表3-1,3-2所示：
表3-1库房和码头之间的距离表
|
距离（Km）
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
0
|
0
|
80
|
65
|
50
|
40
|
35
|
50
|
65
|
65
|
|
1
|
|
0
|
15
|
30
|
45
|
60
|
75
|
90
|
90
|
|
2
|
|
|
0
|
15
|
30
|
45
|
60
|
75
|
75
|
|
3
|
|
|
|
0
|
15
|
30
|
45
|
60
|
60
|
|
4
|
|
|
|
|
0
|
15
|
30
|
45
|
45
|
|
5
|
|
|
|
|
|
0
|
15
|
30
|
30
|
|
6
|
|
|
|
|
|
|
0
|
15
|
15
|
|
7
|
|
|
|
|
|
|
|
0
|
5
|
|
8
|
|
|
|
|
|
|
|
|
0
|
表3-2码头装船8点到9点之间的配送量和配送时间窗
|
码头编号
|
需求量（吨）
|
装船时间
（分钟）
|
时间窗
|
模糊时间窗
|
|
ET
|
LT
|
ET
|
LT
|
|
1
|
0.6
|
6
|
8:00
|
9:00
|
8:10
|
8:50
|
|
2
|
1
|
9
|
8:00
|
8:15
|
8:03
|
8:12
|
|
3
|
0.6
|
6
|
8:00
|
9:00
|
8:10
|
8:50
|
|
4
|
0.75
|
8
|
8:00
|
8:30
|
8:05
|
8:25
|
|
5
|
0.7
|
7
|
8:00
|
8:05
|
8:00
|
8:05
|
|
6
|
0.3
|
4
|
8:00
|
9:00
|
8:10
|
8:50
|
|
7
|
0.55
|
6
|
8:00
|
9:00
|
8:10
|
8:50
|
|
8
|
0.9
|
9
|
8:00
|
8:20
|
8:03
|
8:18
|
|
合计
|
5.4
|
55
|
|
|
|
|
3.2编码及初始种群的生成
由于VRP问题用二进制编码具有先天性的不足，为了弥补这一缺的，本案例采用序数编码，其中0代表库房，自然数表示码头的编号，本案例中有8个码头，随机产生一个序列23786154，然后按以下步骤进行染色体的生成操作：
(1)从左向右累计码头需要运输量，一旦累计运输量大于运输车辆容量时，记录此时的累计次数i，记录断点一为i-1，累计量清零；
(2)从序列的第i个数字重新累计码头需要运输量，当累计需求量大于运输车辆容量时，记录此时的次数j，记录断点二为i+j-l，累计量清零；
式(3)重复以上操作直至结束，生成断点集；
(4)对断点集进行操作，在每个断点的后面插入“0”，表示重新从库房出发；
(5)在序列首未位添加“0”，染色体生成完成；
现以序列23786154为例说明解码过程，设生成的断点集合为式(3，6，5)，则首先在序列的第2、第5及第7位后加“0”，序列变为23078601504。然后在序列前段加“0”，则染色体为，表示配送方案由4条路线组成，其中运输车辆l的路线为：库房0—码头2—码头3；运输车辆2的路线为库房0--码头7—码头8--码头6；运输车辆3的路线为库房0--码头1—码头5；运输车辆4的路线为库房0—码头4。至此完整的染色体生成，然后通过重复染色体生成过程，直至达到种群规模，即为算法的初始种群。
3.3选择算子
选择算子的实现具体操作如下：
(1)首先随机生成n组序列，通过序列加“0”，生成n个染色体；
(2)对这n个染色体进行按适应函数进行适应值 计算；
式(3)根据公式 ，计算每一个染色体的概率；
(4)根据公式 计算每一个染色体的累计概率；
(5)生成呈均匀分布的随机数r(0≤r≤1)，若r≤d1，则选择第1个染色体，若以d≤r≤d(l=2,3，．．．n)，则选择第k个染色体，重复以上操作直至选择的染色体达到种群规模。由于选择的随机性，在染色体选择后，当代群体中的最佳染色体可能会丧失繁殖能力，为了提高算法的性能，在轮盘赌的基础上再采用精英保留策略。
3.4算法的终止
由于遗传算法搜索路径具有较大的随机性，根据启发式算法的终止条件，本文给定适当的终止参数e、 、Y。只要算法满足下列条件之一，就认为算法收敛。
(1)计算每代群体中染色体的适应度方差，当方差小于e时，则认为算法收敛；
(2)计算每代群体中适应度的均值，当均值与最佳染色体适应度的比值大于时，认为算法收敛；
式(3)由于计算时间是有限的，计算代数不能无限长，故当迭代次数达到规定的Y时，停止计算。
4．结论
考虑生产计划损失量函数对车辆调度的的情况下计算得出最终优化解为4226元。最后得到车辆的行驶路线为0—5—2—0；0—4—3—0；0—8—7—6，总的行驶距离为460Km。经检验，此路径安排完全满足各码头的运输需求量约束和装载车辆的承载量约束，是此问题的一个较优的可行解。
此结果表明，经过改进遗传遗传算法优化之后，钻井平台的采购计划可以在最大程度上满足，而且能尽量避免因为配送延迟造成的生产计划的延时，从而使企业能将生产成本控制在比较低的范围。
[1]郎茂祥，胡思继.用混合遗传算法求解物流配送路径优化问题的研究[D]．2002，10(5)：51~56
[2]邢文川，谢金星．现代优化计算方法[M].北京：清华人学出版社，1999
[3]李军.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社，2000
[4]林郁丞.基于聚类分析和遗传算法的带时间窗车辆路径问题研究[D].福州.福建农林大学.2009
2/2 首页 上一页 1 2 |
