（企业管理专业论文）基于遗传算法的满载车辆调度问题研究.pdf

西南交通大学硕士研究生学位论文 第日 页 汹， 尸 .， ab s t r a c t g e n e t i c a l g o r i t h m i s a c o m p l e t e ly n e w m e t h o d b a n d t o g e t h e r w i t h t h e p r i n c i p l e o f l i f e - f o r m e v o l u t i o n , o p t i m i z a t i o n t e c h n i q u e a n d c o m p u t e r t e c h n i q u e . v e h ic l e s c h e d u l i n g p r o b l e m i s a n p d i f f i c u l t p r o b l e m t h a t h a s n o t b e w e l l s o l v e d . t h e p a p e r d e v o t e s t o r e s e a r c h v e h i c l e s c h e d u l i n g p r o b l e m i n f u l l l o a d s w i t h g e n e t i c a l g o r it h m . t h e p a p e r d e e p l y a n a l y z e s t h e p r e s e n t s i t u a t i o n o f v e h i c l e s c h e d u l i n g p r o b l e m , h a n d l e n e t w o r k - m o d e l t o s o l v e v e h i c l e s c h e d u l i n g p r o b l e m i n f u l l l o a d s . s o t h e p r o b l e m c a n b e t r a n s l a t e d t o s o l v e t h e s e q u e n c e o f a r c s a n d w e g e t t h e c o d e t o t h e p r o b l e m . t h u s t h e p r o b l e m c a n b e s o l v e d w i t h g e n e t i c a l g o r i t h m . a p p l y i n g g e n e t i c a l g o r i t h m w i t h n a t u r a l n u m b e r a n d t h e a l g o r i t h m t o t h e s h o r te s t r o u t e i n n e t w o r k g e t t h e m e t h o d t o s o l v e t h e p r o b l e m . t h e p a p e r d i v i d e d t h e p r o b l e m t o t w o k i n d s o f p r o b l e m s . o n e i s s i n g l e d e p o t , t h e o t h e r i s m u l t i p le d e p o t s . t h e p a p e r p u t f o r w a r d t h r e e k i n d s o f c o d e t o s i n g l e d e p o t a n d m u l t i p l e d e p o t s w i t h g e n e t i c a l g o r i t h m a n d d i f i n e t h e g e n e t i c o p e r a t o r s t o t h e t h r e e d i f f r e n t e n c o d i n g w i t h g e n e t i c a l g o r i t h m . a n d t h e p a p e r a l s o d e f i n e s t h e e l e m e n t ry c o l o n y , f i t - f u n c t i o n a n d t h e c o n t r o l p a r a m e t e r s . b as e d o n t h i s , t h e p a p e r a n a l y z e s t h r e e k i n d s o f v e h i c l e s c h e d u l i n g p r o b l e m i n f u l l l o a d s w i t h l i m i t e d c o n d i t i o n s t o s i n g l e d e p o t a n d m u l t i p l e d e p o t s w i t h s o m e c a r s b as e d o n g e n e t i c a l g o r i t h m， a n d p r o c e s s e s t h e e x p e r i m e n t a l a n a l y s i s t o e a c h p r o b l e m w i t h l i m it e d c o n d i t i o n s a n d o b t a i n b e tt e r s o l u t i o n . r e s e a r c h e s i n t h e p a p e r t h a t e n r i c h t h e o ry a n d a p p l i c a t i o n o f g e n e t i c a l g o r i t h m o n n a t u r a l n u m b e r , a n d b r i n g n e w t e c h i q u e t o s o l v e v e h i c l e s c h e d u l i n g p r o b l e m , h a v e t h e o r e t i c a l v a l u e a n d p r a c t i c a l s i g n i f i c a n c e . k e y w o r d s : v e h i c l e s c h e d u l i n g p r o b l e m ; g e n e t i c a l g o r i t h m; v s p i n f u l l l o a d s ; s i n g l e d e p o t ; m u l t i p l e d e p o t s 西南交通大学硕士研究生学位论文第1页 第 1 章绪论 交通运输是人类生产活动和生活活动中一个不可缺少的方面。随着社会经 济的发展，人们对交通运输的需求迅速增大和提高，从而形成了现代交通运输 产业。这样，合理组织运输，降低运输成本，提高经济效益，就具有重要的意 义，车辆调度问题的研究就是由此而来的。 1 . 1 v s p 与t s p 1 . 1 . 1 车辆调度问题 1 . 1 . 1 . 1 v s p 描述 车 辆调度问 题 ( v e h i c l e s c h e d u l i n g p r o b l e m ， 简 称为v s p ) 产生于 现实的公 路交 通运输， 于1 9 5 9 年由d a n tz ig 和r a m s e ， 首次总结 提出 。 它一般定义为: 对一系列发货点和 ( 或)收货点，组成适当的行车路线，使车辆有序地通过它 们， 在满足一定的约束条件 ( 如货物需求量、发送量、 车辆容量限 制、行驶里 程限制、时间限制等)下，达到一定目 标 ( 如路程最短、费用极小、时间尽量 少、使用车辆最少等) 。 几十年来， 这一问题引起运筹学、计算科学、图论与网 络分析、随机过程等学科的专家和运输计划制定者和管理者的极大重视， 进行 了大量的理论研究和实验分析，取得了很大进展。特别是近十多年来，随着计 算机技术的快速发展，为各种算法的实验研究和实施提供了基础。目 前该问 题 己不仅仅局限于公路交通运输领域，经常出 现于水运、航空、通讯、电力、工 业管理、计算机应用及v l s l 设计等领域. 川 . 1 . 2 v s p 研究中 存在的问 题 目 前，国内 对v s p 研究的比 较少， 仅有郭耀煌、 李军编著的 车辆优化调 度 一书较系统地介绍了该问题的理论与算法。 国外对v s p的研究的比较深入， 应用也比较广泛， 但也存在不足，主要表现在: 1 . 研究非满载问题，主要集中在车辆封闭问题，对车辆开放问题的研究尚 未见到;对点服务和对弧服务的 研究较多， 对点弧混合服务问 题研究的较少; 对单目 标研究较多，对多目 标情况研究较少;对有时间窗问题的研究仅限于单 车场问题，且因条件限制应用有限;对随机不确定性需求问题的研究较少，且 西南交通大学硕士研究生学位论文第2页 限于单车场无容量约束的情形。 2 . 研究满载问题较少， 仅限于把满载问题转化为非满载问 题来处理， 这样 不但扩大了变量的维数，而且只有在非满载问题得到很好解决的情况下才有意 义，缺乏实用性。 3 . 算法的适应性差。 对于各种各样的v s p ， 还没有一种通用算法。 即使对 于形式十分相近的问题， 通常也不能用同一种算法来求解，给问题的研究者和 应用者带来很大的不便。并且从v s p 提出至今，一直沿用传统的求解方法，没 有太大的突破。 对大规模的组合优化问题， 传统方法一般很难求得全局最优解， 即使取得全局最优解也要依靠选取优良 的 初始搜索点。 v s p 是以 旅行商问题为基础提出的，下面就简单介绍旅行商问 题。 1 . 1 . 2 旅行商问题 旅行商问题( t r a v e l l i n g s a l e s m a n p r o b l e m ， 简称t s p ) ， 是最重要的一个组合 优化问 题，自1 9 3 2 年由k m e n g e r 提出后，引起许多专家学者的兴趣，产生了 各种各样的求解方法， 但对于大规模的t s p ，无一能行之有效地产生全局最优 解。 t s p 是典型的n p 难题， 研究它的重要意义在于所有的n p 类问题都等价于 t s p 。因此，t s p已成为组合优化中的一个标准问题，人们每提出一种新的寻 优方法，总是力图用t s p 来检验。 一般 t s p描述起来十分简单，即一个旅行商通过全部1 个城市一次且仅一 次的最短旅行线路. t s p的每个可行解都是1 个城市的一个全排列，解的个数 是( 1 一 1 ) ! ， 解的规模随着城市数的增加指数增长，出 现组合爆炸现象。 若1 为 2 0 ， 则 解 的 个 数 约 为1 .2 x 1 0 1 7 ， 在 每 秒 运 行1 亿 次 的c r a y 1 1 巨 型 机 上 运 行 也 须 3 5 0 年。 为了 更 好地描述t s p ， 将 其定义为网 络g = ( v , a , c ) ， 其中: v = 0 , 1 , . . . , 1 - 1 为 一点 集， 表 示 旅行 商需 要 访问 的 城 市;a = ( i, j ) i i, j = 0 ,1 , . . ., 1 - l , i * j ) 为 弧 集 ， 表 示 旅 行 商 可 能 走 过 的 路 段 集 合 ; c = ( c . i ( i , j ) e a ) 为 费 用 矩 阵 ， c y 表 示 旅行商经过对应弧(i ， 力所花费的时间、 距离或运 输成本等。 为了说明问题方便，设城市0 为旅行商的出发和返回点，称为源点。为构 造数学模型，定义 西南交通大学硕士研究生学位论文第3页 若弧 ( i , 力 在回 路上 否则 ， .且0 衬!r!、 - 少 x 则以分派为基础的数学模型为: m in z = 艺艺 c u x 0 ( 1 一 1 ) l . x v 二 1 艺x= 1 j = o x= ( x y ) ， 1 = 0 , 1 , . . . , 1 一 1( 1 一 2 ) 0 , 1 , . . . , 1 一 1 ( 1 一 3 ) x 0 = 0 或1=0 , 1 , . . . , 1 一 1 ( 1 一 4 ) ( 1 一 5 ) 尹 51， ，.任， 其中:式 ( 1 - 1 ) 表示成本极小的目 标:式 ( 1 - 2 )和式 ( 1 - 3 ) 表示每一结点被 访问 一次且仅被访问 一次; 式 ( 1 - 4 ) 为支路消去约束 ( s u b t o u r 一 b r e a k i n g约束 ) 条件;式 ( 1 - 5 )为变量的取值约束。 支路消去约束s即避免出现不完整旅行线路的约束，s 一般有下面几种表 示法: ( 1 ) s = ( x , ) i yyx , 2 1 ， 对 点 集 v 的 每 一 个 非 空 子 集 q ， 此 式 中 含 有 i e q j o q 2 1 个支路消去约束，说明点的某一子集必须同 解中 其它点集相连: ( 2 ) s = ( x ; ) l 艺艺i r i - 1 ， 对 2 ,3 , . . . , 1 的 每 一 非 空 子 集 r ， 此 式 中 含 i e r j 口 r 有2 1 个支路消去约束，暗示了 任一子集必须同解中 其它点集相连。 ( 3 ) s = ( x , ) i w 一 w i + ix ,. 5 l 一 1 , 2 _ 0 ( 为 整 数 ) ， 表 示i 到j 的 货 运 数( 车 辆 载 重 的整数倍) ; y - ( w w 2 , . . . ， ti y k ) 为 车 辆配置向 量，w ; ( w , 0 ， 整数 ) 表示车场i 处车辆配 置数; 要求:每辆车在完成任务后回到车场; 问 题:求完成供求矩阵的 运输任务， 使总的 运输距离最短的方案。 2 . 1 . 2 满载v s p 的分类 对于满载v s p的适当分类，在理论研究和实际应用系统开发都具有重要的 指导意义。 参照b o d i n , g o l d e n , b o d i n , d e s r o s i e r s , l a p o r t e e t a l 等人对v s p 研究现状，根据满载的v s p 的特点，对满载的v s p 的约束条件和目 标函数作 了如下的分类， 共1 4 个条目， 以下分类表中不同条目 的选择和组合， 即构成相 应的满载v s p的子问题。 1 . 车队数 。一个车队 西南交通大学硕士研究生学位论文第1 8页 。一个以上车队 。不确定 2 . 每个车队拥有的车辆数 。一辆车 。一辆以上 。不确定 3 . 车辆类型 。所有车辆的载重相等 。所有车辆的载重不完全相等 4 . 供求类型 。供求确定 。供求随机 5 . 需求位置 。边 ( 弧) 。结点 。混合型 6 . 网络类型 。无向 。有向 。混合 ( 既有有向边又有无向边) 7 . 时间规定 。在规定时间区间内完成运输任务 。无时间规定 8 . 费用函数 。费用固定 。费用随时间和空间不同而变化 9 . 作业类型 。可倒运 ( 一次运输任务可以分成多阶段完成) 。不可倒运 西南交通大学硕士研究生学位论文第1 9页 1 0 . 距离约束 。每辆车的运输距离无限 。每辆车的运输距离有限 1 1 . 车队位置 。活动的 。确定的 1 2 . 送达程度 。全部送达 。部分送达 ( 不送有损失) 1 3 .目标函数 。总的路程最短 。车辆维护费用和运输费最少 。人的因素 。最少车辆数 。考虑缺货损失、停车等待损失、加班费 1 4 . 其他 2 . 2 满载的v s p 的图论基础 由 于对设计遗传算法的需要， 满载v s p 在图论上与非满载v s p 存在一定的 差异性。 对于一般的v s p ，其网络模型如下所述: 设g = ( v ,e ,a ) 是一个连通的混合网 络， v 是顶点 集， e ,a 分别是( 无向) 边集 和 ( 有向)弧集， e中的边和a中的弧均被赋权 ( 或称距离或称时间或称费 用) .v , e , a 分别为 v ,e , a的子集， 求一个包含v , e , a的巡回 ( 闭 链) ， 使其 总长度 ( 或时间或费用)最小。 先引入下面的一些概念。 定 义1 设g = ( v ,e ,a ) 是 一 个 连 通 的 混 合 网 络 ， a ;, a , e a 是 两 条 有向 边 ， 则a , 到 a j 的 距 离 为 。 的 箭 头 顶 点 到 a j 的 箭 尾 顶 点 的 距 离 ， 记 为 d ( a a j ) o 定 义2 设g - ( v ,e ,a ) 是 一 个 连 通 的 混 合 网 络 ， s = ( a a 2 , . . . , a m ) 是 一 组 有 向 边 的 有 序 集 合， 则 定 义s = ( a , a 2 , . . . ， a m ) 的 长 度为 : 西南交通大学硕士研究生学位论文第2 0页 l . d (. ,， 十 洲a ,il + la m l u i sm- 记 为le n (s ) 或l e n ( aa 2 , * * * , a ., ) a 定 义3设g = ( v ,e ,a ) 是 一 个 连 通的 混 合 网 络， (a， a 2 , . , a m ) 是 一 组 有向 边的 有 序 集 合， ， 是v 中 的 任 意 顶点 ， 定 义， 到( a , , a 2 ， 一 ， a . ) 的 距 离 为， 到a ， 的 箭 尾 顶 点 的 距 离， 记 为d ( v ; a l ， a 2 ， . . . ， a m ) ; ( a ; ， a 2 ， . . . ， a m ) 到， 的 距 离 为a 。 的 箭 头 顶 点 到， 的 距 离 记 为 d ( a , , a 2 , . . . ， a m ; v ) . 这样就可以构造出满载v s p的网络模型: 对 于 网 络g = ( v ,e ) ， 若 从i 到 .! 有氏个 单 位的 货 物， 则 定 义 从i 到 j 有氏条 有向 边， 其长 度为i 到1 的 距离， 这样就可以 构 造一 个新的 混 合网 络g = ( v ,e ,a ) , 其中a是所有这些有向边的集合。 因此， 满载的v s p 就转化为求一个包含车队 和所有有向边的最短路问题。 例如， 在一辆车的 情况下， 交通网络图如图2 -1 所示， 车队位置为 1 ， 每 条边的权为 1 ,需求矩阵为: 八ucun山.1 102c甘 图2 -1交通网络图 由图和需求矩阵转换可得有向图2 -2 ; ,丈一 a v 图2 -2 有向图 西南 交 通大学 硕士 研究 生学 位论文第 2 1页 - - 种种种种种种种种种种种种种种 这 样问 题 就 转化 为由 车 场1 出 发， 包 含 所 有弧a , , a 2 , . ., a s 然后 再回 到车 场1 的最短路问题。 2 . 3 最短路问题简介 2 . 3 . 1 最短路问题概念 为了说明问题，先举关于一个关于最短路问题的例子。 已有如图2 -3 所示的单行线交通网， 每条弧旁的数字表示通过这条单行线 所需要的费用。现在某人要从 1 结点出发，通过这个交通网到4结点去，求使 得总费用最小的旅行路线。 图2 -3交通网 其中，1 , 2 , 3 , 4表示结点，0 内的数表示结点到结点 ( 弧)的权 ( 距 离) 。由图可见，从1 结点到4 结点的旅行线路是很多的，如可从1 结点出发， 经过3 结点到达4 结点，也可以从 1 结点出发，经过2 结点到达4 结点，也可 以直接从1 结点到达4 结点。不同的路线，所走的距离是不同的，如按第一种 路线，总距离是3 ，按第二种路线，总距离是7 ，按第三种路线，总距离是9 0 由 此， 可得出 一般的 最短路问 题， 给定一 个赋权有向图g = ( v a ) ， 对每一 弧 a = ( vv j ) i 相 应 地 有 权， ( a ) 二 w 0 ， 又 给 定d 中 的 两 个 顶 点 v s , v , ， 设p 是 d中 从v ， 到v , 的一条路， 定 义路p 的 权是p中 所有弧的 权之 和， 记为w ( p ) 。 最 短路问 题就是要在所有从v : 到v , 的 路中 ， 求一条权最小的 路， 即 求一条从v ， 到v , 的 路 p o ，使 w ( p o ) 一 吵w (p ) 。 式 中 对 d 中 所 有 从 v ， 到 v , 的 路 p 取 最 小 ， 称 p o 是 从v s 到从 的 最短 路。 路p的 权 称为从凡 到巧 的 距离， 记为d = ( v s , v , ) 。 显然， 各种从v ， 到v ， 的 路的 距离d = ( vv , ) 不一定相等。 2 . 3 . 2 最短路问题的算法 最 短 路问 题的 算 法 最常 用的 是d iy k s tr a 算 法， 是由d iy k s tr a 于1 9 5 9 年提出 西南交通大学硕士研究生学位论文第2 2页 来的。 在 这里介 绍 求 任意 两点间 的 最 短路的 弗 洛 伊德 ( f l 妙 a d ) 算 法 ( 不容 许 有负回路) 。 1 . 有关术语 给定一个赋权有向图g = ( v ,a ) ，首先将图中 所有顶点编号为:1 ,2 ， 一， n; 然后定义: d 0 从 顶点i 到 .l 的 最 短 路长 度， 但中 间 只 允 许经 过 前m 个顶 点。 若无 路， 则 令d 一 + 。 。 心 从 顶 点i 到1 的 最 短 路 长 度， 但中 间 无 顶 点 ， 衅= 0 e d r 从 顶 点i 到7 的 最 短 路 长 度， 但 中 间 可 经 过n 个 顶 点。 二一 n x n 矩 阵 ， 其 中 碌 砌 。 算法就是逐次求出d o , d , . . . , d n( 结束) 。 2 .基本思路 令只通过前m - 1 个顶点( 1 , 2 , . , m 一 1 ) 的从i 到m ， 从m到.1 及从i 到1 的 最 短 路 分 别 为 d 二 一 , d， 及 d 罗 - 。 由 于 不 存 在 负 回 路 ， 故 从i 到.1 的 只 能 经 过 前m 个 顶点( 1 ,2 , . , m 一 i m ) 的 最 短 路 必为 下 述 两条 路 径 之 一: d 二 一 ， 十 d 川或 d m - 1 即 心= m in 嵘 一 ， + d 篇 ， 心 一 ， 。 可 见 ， d ， 可 从 d 。 一 ， 递 推 得 出 。 3 .算法步骤 s t e p 1 : 将 图 中 所 有 顶 点 编 号 为 : 1 ,2 , - - - , n( 随 意 编 号 ) 得 到 矩 阵d 0 , 心即 为1 的 连 边 长 ， 无 连 边 ， 令心= + 0 0 ， 心= 0 。 s t e p 2 : 令 m = 1,2 , . . ., n ， 根 据 公 式 : 叮= m in ( d ;m + 叮， ， 心 一 ， ， 逐 个 算 出 d , d . . . . . d “ 每 确 定 一 个 元 素 ， 记 下 表 示 的 路 。 最 后 d “ 中 的 元 素 d n 即 为 从 i 到.1 的最短路. 由d - ， 递推得出d . 时，可发现有以下特点: 心= 0 , = d 黔， d 川= 端。 即 矩 阵 d 的 对 角 线 元 素 为。 ， 且 其 第m 列和第 m行也不需计算，