（计算机应用技术专业论文）集装箱装卸计划自动编制研究.pdf

摘要 摘要 随着社会主义经济的飞速发展和铁路的改革开放 集装箱运输以其众多 优越性 己成为我国铁路运输的主要形式和新的经济增长点 铁路集装箱作业效 率的高低 关系到铁路运输的效益和货主的切身利益 因此 对集装箱箱场作业 优化问题进行研究 是提升服务及资源利用率的重要课题 本文所研究的装车作 业和箱位分配作业都是集装箱箱场的主要业务 作业计划的制定直接影响了装卸 的效率 本文运用启发式搜索算法快速求出满意的集装箱双层车辆配载方案 同时依据 集装箱装载的三个目标的重要程度将多目标问题转化为单目标问题 来综合评价 所得的配载方案 从而提高装车效率 保证运输安全 在综合考虑集装箱位置信 息 列车位置信息的基础上 本文运用启发式算法与禁忌搜索算法相结合生成集 装箱装车顺序方案 使装卸机械走行距离最短 提高装卸机械的利用率 考虑到 分配箱位的各种约束条件 衡量分配方案优劣的多个目标 本文采用遗传算法求 得多个可供选择的方案 优化箱位分配 本文对相关算法进行了实例验证 表明 集装箱配载算法可以在短时间内得出一种符合装载约束条件 具有较高装载率的 有效方案 集装箱装车顺序算法可以得到机械走行距离最短的路径 箱位分配算 法可以得到在多个目标方面较为均衡的若干方案 本文所研究的装卸作业算法不仅具有实际的应用价值 同时也为进一步的作业 优化提供了基础的解决方案 关键词 铁路集装箱 装车作业 箱位自动分配 禁忌搜索算法 遗传算法 分类号 t p 3 1 1 5 a b s t r a c t a b s t r a c t a l o n gw i mt h er 印i dd e v e l o p m e n to fs o c i a l i s t i ce c o n o m ya n dt h e r e f o r m a t i o na n do p e n i n go f m i l w a y c o n t a i n e r i s a t i o nw i t hm a n ya d v a n t a g e s h a sb e c o m e t h em a i nf o r ma n dt h en e wp o i n t so f e c o n o m i cg r o w t ho f c h i n a sr a i l w a yt r a n s p o r t a t i o n t h ee f f i c i e n c yl e v e lo fr a i l w a yc o n t a i n e ro p e r a t i o ni sd i r e c t l yr e l a t e dt ot h eb e n e f i to f t h er a i l y w a yt r a n s p o r t a t i o na n dt h ev i t a li n t e r e s to fo w n e ro fc a r g o t h e r e f o r e t h e r e s e a r c h0 1 1t h eo p t h n i z a t i o no f c o n t a i n e ry a r do p e r a t i o ni sa l li m p o r t a n ts u b j e c tt or a i s e t h eu t i l i z a t i o nr a t eo fr o s o u g c 宅a n ds e r v i c e t h el o a d i n go p e r a t i o na n dt h ec o n t a i n e r a l l o c a t i o no p e r a t i o nt h i sp a p e rs t u d y sa r et h em a i nb u s i n e s so fc o n t a i n e ry a r d t h ep l a n f o r m u l a t i o nd i r d t l ya f f e c t st h ew o r k i n ge f f i c i e n c y t h ep a p e ru s e sh e u r i s t i cs e a r c ha l g o r i t h mt oo b t a i n r a p i d l ys a t i s f a c t o r y p r o g r a m m e sa n da c c o r d n g 幻t h ei m p o r t a n c e d e g r e eo ft h r e eo b j e c t i v e sm a k e s m u l t i o b j e c t i v ep r o b l e m b es i n g l eo b j e c t i v e p r o b l e m v a l u i n g t h ep r o g r a m m e s c o m p r e h e n s i v e l y a st oe n h a n c et h ee f f i c i e n c yo fl o a d i n ga n de n s u r et r a n s p o r t a t i o n s a f e t y c o n s i d e r i n gp o s i t i o ni n f o r m a t i o no f c o n t a i n c 目p sa n d 嘶1 1 t h ep a p e ru s e sh e u r i s t i c s e a r c ha l g o r i t h mc o m b i n e dw i t ht a b us e a r c ht og e n e r a t et h ep r o g r a m m e so fc o n t a i n e r l o a d i n gs c q u c n c c w h i c hi m p r o v e st h eu t i l i z a t i o no fl o a d i n ga n du n l o a d i n gm a c h i n ea n d m a k e st h ed i s t a n c eo fl o a d i n ga n du n l o a d i n gm a c h i n er u n ss h o r t e s t t a k i n gi n t oa c c o u n t t h ea l l o c a t i o nw i t ht h ev a r i o u sf a c t o r sa n do b j e c t i v e so fm e a s u r i n gt h em e r i t so f c o n t a i n e ra l l o c a t i o np r o g r a m m e s t h ep a p e ru s e sg e n e t i ca l g o r i t h mt oo b t a i nm a n y o p t i o n s o p t i m i z i n gt h ec o n t a i n e ra l l o c a t i o n t h ep a p e rm a k e se x a m p l e so nt h e s e a l g o r i t h m st ov e i l f y w h i c hs h o w st h a tc o n t a i n e rl o a d i n ga l g o f i t l m ac a no b t a i ne f f e c t i v e p r o g r a m m e si nas h o r tt i m em e e t i n gt h ec o n s t r a i n t so f l o a d i n g 丽t hh i g h e rl o a d i n gr a t e c o n t a i n e rl o a d i n gs e q u e n c ea l g o r i t h mc a no b t a i nt h es h o r t e s tp a t ht h a tt h em a c h i n en l s c o n t a i n e ra l l o c a t i o na l g o r i t h mc a no b t a i nm o r eb a l a n c e dp r o g r a m m e s i nt h i sp a p e r a l g o r i t h m sr e s e a r c h e dn o to n l yh a v ep r a c t i c a lv a l u eb u ta l s op r o v i d e t h e b a s i cs o l u t i o n f o r t h e f t u t h e r o p t i m i z a t i o n o f t h e o p e r a t i o u s k e y w o r d s r a i l w a yc o n t a i n c r l o a d i n go p e r a t i o n c o n t a i n e ra l l o c a t i o n t a b us e a r c h g e n e t i ca l g o r i t h m c l a s s n 0 t p 3 1 1 5 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留 使用学位论文的规定 特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索 并采用影印 缩印或扫描等复制手段保存 汇编以供查阅和借阅 同意学校向国 家有关部门或机构送交论文的复印件和磁盘 保密的学位论文在解密后适用本授权说明 学位论文作者签名 主t 1 啦 l 导师签名 陴坤 签字日期 坼 月卅e t签字日期 川年i 月 4 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果 除了文中特别加以标注和致谢之处外 论文中不包含其他人已经发表或 撰写过的研究成果 也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名 耋l 讫秒签字日期 1 7年 1 月7 日 致谢 本论文的工作是在我的导师陈光伟的悉心指导下完成的 陈光伟老师严谨的 治学态度和科学的工作方法给了我极大的帮助和影响 在此衷心感谢三年来陈光 伟老师对我的关心和指导 在铁道部信息中心实习期间 陈光伟老师悉心指导我完成了项目的开发研究 工作 在学习上和生活上都给予了我很大的关心和帮助 在此向陈光伟老师表示 衷心的谢意 陈光伟老师对于我的科研工作和论文都提出了许多的宝贵意见 在此表示衷 心的感谢 在铁道部信息中心工作及撰写论文期间 庞鸣雷 梁荣青等工程师对我论文 中的集装箱双层车辆配载的研究工作给予了热情帮助 在此向他们表达我的感激 之情 另外也感谢家人 他们的理解和支持使我能够在学校专心完成我的学业 1 引言 1 1课题研究背景 随着世界范围的集装箱运输快速发展和集装箱标准化 专业化和通用化的趋 势 我国铁路的集装箱运输迅速发展 己成为铁路货物运输的主要形式和新的经 济增长点 中铁集装箱运输公司与1 5 个铁路局集装箱分公司和分布于全国的5 0 0 多 个集装箱办理站 构成铁路集装箱运输系统 在铁路运输部门管理下 统一组织 铁路集装箱运输和经营管理 近年来 集装箱运能运量大幅上升 国际联运业务 不断发展 开通了中国大陆桥铁路通道 使从连云港 青岛 天津 上海 深圳 等港口口岸上桥的集装箱货物 经由中国几千公里铁路运输 穿越中国大陆运抵 中亚和欧溯国家 中国己成为世界上铁路集装箱运输发展最快的国家 中国进入 1 r 1 0 后 集装箱运输业逐渐在运输行业中表现出越来越重要的地位 目前 全路拥有1 吨 1 0 吨集装箱和2 0 英尺 4 0 英尺国际通用集装箱和折叠 式台架箱 双层汽车集装箱 罐式集装箱等专用集装箱共计1 4 类3 8 9 万只 拥 有集装箱专用平车9 1 3 0 辆 近年来 集装箱 集装箱专用车辆保有量逐年提高 装卸机械有所改善 购置了一些正面吊 轮胎吊 叉车等 十五 期间 新造 时速1 2 0 公里的集装箱专用平车5 2 0 辆 双层集装箱专用平车1 9 0 辆 改造x 3 k 车7 8 辆 新造包括2 0 4 0 4 8 英尺通用集装箱及各类特种集装箱1 5 万只 2 0 0 6 年 集装箱装卸机械进一步更新 提高了集装箱装卸作业效率与质量 双层集装箱运输是运输市场激烈竞争的产物 发展双层集装箱运输是解决铁路 运输能力不足的问题 提高运输效率和效益的措施之一 北京一上海双层集装箱 班列在国内首次运行 于2 0 0 4 年4 月1 8 日正式开通 该列采取直通运行 实施 客车化管理 定点 定时 定线路 定起始站 定到达站 以此在中国两大国际 化都市北京与上海之间构筑了超大运量的物流通道 该车通过采用 凹式框架 结构 车辆下层装载二只二十英尺标准箱 上层装载一只四十八英尺超大容量新 型集装箱 车辆承载能力为七十八吨 容积一百四十立方米 每列由三十八辆铁路 集装箱专用平车组成 且北京至上海只需运行三十八小时 较以往的铁路运输时 间大大缩短 极大地缓解了两地物流需求大而运力不足的矛盾 专家表示 中国整个铁路系统目前面对最严重问题 就是铁路运输能力不能适 应日益增长的运量需求 采用双层集装箱运输方式 就是增加运能 缓解运能与 运力需求矛盾的重要举措 双层集装箱运输是一种运输速度快 技术先进的货运 新产品 它的出现必将推动铁路货运产品改革的步伐 随着我国经济高速增长以及对外贸易量的增加 集装箱的吞吐量也必然将逐年 增加 为满足集装箱吞吐量e t 益增长的需求 提高对货主的服务质量 如何提高 集装箱堆场作业效率已成为当前集装箱堆场研究的重要课题 集装箱堆场作业效 率主要体现在集装箱装卸效率上 作为集装箱运输的一个重要环节 大型集装箱堆场在这里更是显示了极大 的优势 已承载了大宗货物的存储和运输 已经成为集装箱运输不可缺少的一个 重要环节 堆场提供的服务已经深深地参与到了集装箱运输的生产活动中去 实 实在在她为集装箱货主提供了增值服务 例如随着集装箱运输通过铁路 公路等 运输模式 在内陆地区也相应出现了许多集装箱堆场 为集装箱经营人开拓内陆 市场 提高集装箱运输的经济效益做出巨大的贡献 集装箱堆场在我国的发展起步比较晚 但是发展速度相当快 而且随着以通讯 技术 网络技术 感测技术 控制技术等为代表的现代信息技术的快速发展以及 全球信息网络的兴起 现在己经初具规模 虽然目前我国一些集装箱堆场己具备 了先进的生产设施和现场实时控制系统 但总体来说 与国外先进的集装箱堆场 相比还存在一定差距 主要表现在对堆场内部物流系统的资源配置 任务安排和 路径优化等方面还采用经验管理 堆场物流信息系统也有待于进一步完善和发展 为了适应现代物流和供应链管理的发展 满足快速增加的箱量需求和提高顾客服 务水平 在新一轮的竞争中取得优势 堆场管理者需按照现代物流和供应链管理 的要求 不断提高堆场内部物流网络节点配置的合理性 充分重视集装箱装卸时 机械设备作业计划和作业顺序制定的科学性 并不断完善其内部物流信息系统 以提高资源利用率 提高作业效率和效益 同时物流技术的发展和广泛应用也为 集装箱堆场提高其内部物流运作效率提供了保障 集装箱装卸是集装箱运输非常重要的环节 直接影响着集装箱运输的效率 铁 路的经济效益 如何摆脱人工操作的落后局面 同时给出一个合理的装卸方案 提高装卸机械的利用率和装卸车的效率 是本课题研究的目标 实现这些目标 将会给铁路集装箱尤其是目前的新型的双层集装箱运输带来巨大的经济效益 1 2集装箱堆场作业研究现状 当今世界集装箱运输已经实现了设备化和硬件的标准化 目前正朝着自动化和 软件的标准化方向发展 随着铁路货物吞吐量的e t 益增长 铁路集装箱作业效率 的高低 直接关系到整个运输过程的效率和成本 关系到铁路运输的效益和货主 的切身利益 因此如何对铁路集装箱物流系统进行更加合理有效地规划与设计 2 j l 哀銮通太堂亟 兰僮论奎 i 直 以最大限度地发挥其作业能力 是目前急需解决的问题 近年来 随着集装箱运输业的发展需要 以及计算机仿真软件的进步 研究者 们多利用计算机模拟技术和优化算法对集装箱物流系统进行研究 这些研究主要 集中在运营环节及装卸工艺系统方面的研究 其中运营环节发生在水平搬运 堆 场作业等 因此研究可以分为装卸设备资源的合理配置及调度 堆场作业 装卸 工艺流程的选择等部分 1 2 1关于堆场内装卸设备资源的合理配置及调度研究 i c h k i m 和j w b a e 采用混合整数规划模型研究将集装箱分配给自动导向车辆 a o v 的调度问题 1 x 1 1 z h a n g 用整数规划模型来研究轮胎式起重机的配置问题 以减少堆场工作的延迟 并通过拉格朗放松启发式理论来获得接近最佳解决方案 x 2 j a 州e l 和s h i e l d s 分别在其研究工作中对到港船舶的装卸箱过程进行模拟 研究 了岸边集装箱起重机调度问题 同时通过模拟还可以帮助制定堆场计划以减少翻 箱率 3 1 i c y k i m 和k h 瞄m 运用整数规划来最小化跨运车在堆场的运输时间 4 阁 张新艳在她的博士论文中使用一种进化策略算法对港口集装箱装船作业顺序进行 优化 并实现了基于面向对象的p e t r i 网的仿真模型l 州 从以上研究可以看出 国内研究比较少 国外研究中目前多用启发式算法和整 数规划来解决装卸设备资源的配置和调度优化问题 1 2 2关于堆场箱位分配的研究 且前国内外就此问题展开相关研究的学者为数不多 研究角度各不相同 采用 的技术方法也略有差异 但目标基本一致 都取得了一定的成果 k h k i m 和 j w b a e 假设当前集装箱堆场图可以获得 同时期望的贝布局也可以提供 研究了 集装箱重新配置作业问题 达到移动最少数量的集装箱和移动最短距离的目标 7 1 香港科技大学c h u q i a nz h a n g 和j i y hl i u 等提出了一种变动放箱范围的方法 在每 个计划范围中 问题可以分解为两个层次 每个层次可以由一个数学规划模型表 示 确定了每个时间段内每个街中放置集装箱的总数 实现了平衡各个街之间的 作业量 最小化将集装箱从前方堆场运送到在港船舶之间的距离 j p e t e r p r e s t o n e r h a nk o z a n 针对不同的集装箱操作计划分析了以最优存储策略为目标的港口系 统 建立了以船舶在港时间最小化为目标函数的集装箱箱位分配模型 并用遗传 算法获得了最优解 9 k i m 讨论了在一个贝内由场桥作业时计算期望倒箱数目的算 法 l o k o z a n 和p r e s t o n 把遗传算法用于减少集装箱倒箱和运输时间及船的在港 3 j 虚窑墟太堂亟 堂僮论塞j l 宣 时间 f l j 郝聚民等在图搜索技术和模式识别理论的基础上建立了随机条件下的混 合顺序作业堆场贝优化模型 1 2 1 1 3集装箱管理信息系统概况 1 3 1国外集装箱管理信息系统概况 集装箱运输是当前世界发达国家铁路快速货运的主要形式 并且已形成世界范 围的集装箱运输标准化 专业化和通用化的发展趋势 伴随着计算机技术的迅速 发展 各国运输企业在逐步建立 发展和完善企业管理信息系统的同时把建设集 装箱管理信息系统作为发展集装箱运输的重要内容和提高运输效益的重要手段 如美国 加拿大 日本 法国的铁路 海运公司的集装箱信息系统都已使用多年 并具有全球性计算机网络相支持 香港东方海外公司的集装箱管理信息系统管理 着其在全球运输的3 0 万个集装箱动态 加拿大c p 铁路公司使用集装箱管理信息 系统对所属2 0 个集装箱结点站站内集装箱调度管理 作业流程实现自动处理 同 时对集装箱运输实行全程动态追踪管理 其国铁 c n 的集装箱管理系统与货车实 时追踪系统结合使用 大大增加了集装箱运输能力 使集装箱周转时间压缩了二 分之一 美国六大铁路公司之一的c s x 公司 运输管理信息系统投入使用后 集 装箱运输能力增加了2 0 运输收入提高7 9 美国的b n 铁路公司 圣太菲铁 路公司 南太平洋铁路公司 联合太平洋铁路公司等 应用e d i 技术 可接受联 运提单 传输舱单信息 车辆和集装箱位置的实时追踪信息 运费支付信息 海 关报关检关信息 现款过户信息等 还可为多式联运用户提供询价和查询等服务 在西雅图港由于采用了e d i 技术 到港的集装箱卸船后仅用5 个小时便可在铁路 车站开出一列集装箱直达列车 国外大部分重要运输口庠己建立货物运输管理系统和电子数据交换 e d i 系 统 与银行 海关 商检 贸易 保险公司和其他运输行业信息系统联网交换信 息 快捷有效地组织国际集装箱联运业务 1 3 2国内集装箱管理信息系统概况 随着我国深化改革和扩大对外开放 外贸运输 其中特别是集装箱运输发展迅 速 经过十多年的建设 由海洋运输 港1 2 1 装卸和内陆转运等诸环节组成的我国 集装箱运输体系己初具规模 日臻完善 使集装箱运输的发展一直保持着良好发 展趋势 目前 我国从事集装箱运输的航运公司共有1 5 0 多家 己拥有集装箱船 4 j k 赢窑通太堂亟 兰篮论室i l 直 舶近千艘 中国远洋运输集团集装箱船队已居世界第四位 并在1 5 0 多个国家的 1 1 0 0 余个港口设有自己的代理 我国开辟集装箱班轮航线1 3 0 多条 每月开出的 航班达2 0 0 0 余个 此外 随着公路主骨架的建设 公路集装箱内陆中转站 集装 箱专用车队都有很大的发展 承担着港口集装箱的运量8 0 以上 交通部 远洋公司等都已建立集装箱管理信息系统和e d i 中心 对国际箱运输 的信息化开展了研究应用 为了促使我国国际集装箱运输的发展和规范化管理 中国交通部组织实施了以 上海为试点的集装箱试验项目 实现了集装箱运输单证及其流转程序的规范化和 标准化 在此基础上 于 九五 期间组织实施了电子数据交换系统 e d l 示范工 程 在中远集团和最大的三个外贸港口 上海 青岛 天津 以及集装箱吞吐量增长 最快的宁波港建成了e d i 系统 之后在大连 烟台 连云港 南京 厦门 福州 广州 深圳 防城等港口推广应用 并逐步将e d i 网络由沿海向内陆延伸 中国 海关总署也自1 9 9 7 年以来开始建设e d i 报关系统 己与交通 远洋系统相连 一 关四检 海关 边检 卫检 动植物检 商检 都实现了计算机办理 1 3 3铁路集装箱管理信息系统概况 铁路信息化经过多年建设 己取得显著成绩 运输管理信息系统 t m i s 的许多 子系统己投入运行并发挥了效益 但是 铁路国际箱联运和多式联运方面还没有 完全实现计算机管理 接运港口集装箱的比重不大 与海运和公路比较起来 对 国际集装箱 的接运铁路仅占约2 由于铁路与港口和海运企业 如中国远洋 运输总公司 对外贸易运输总公司等 之间没有建立起e d i 系统 不能进行信息交 换 无法及时得到通过海运到达港口的集装箱的装箱货物等信息 从而制约了铁 路接运港口集装箱的能力 集装箱办理站没有使用统一的管理信息系统 在车站 集装箱管理 信息采集 处理方面没有全面实现标准化和自动化 信息准确 及 时有待提高 这种情况造成铁路接运国际集装箱比例相对于其他运输形式较少 影响了铁路运输的效益和质量 影响了铁路市场竞争能力 1 4论文的研究内容 本文的主要工作是在分析集装箱箱场装卸作业的基础上 给出了集装箱装卸计 划自动编制算法 并且使用算例进行了验证 证明本文中的算法可以有效地提高 集装箱装卸作业效率 本文的研究内容可以总结为以下几个部分 1 集装箱的双层配载 根据配载的原则和要求 运用启发式搜索算法快速求 5 出满意的配载方案 以适应实时操作的要求 同时依据集装箱的搭配难易 度 平均轴心高 平均集重差三个目标的重要程度将多目标问题转化为单 目标问题 来综合评价所得的配载方案 从而提高装车效率 保证运输安 全 2 集装箱的装车顺序 综合考虑集装箱所在的箱位 列车的位置及集装箱在 车上的位置 运用启发式算法与禁忌搜索算法相结合生成集装箱装车顺序 方案 使装卸机械走行距离最短 提高装卸机械的利用率 3 集装箱的箱位分配 不仅与堆场的箱位状态 堆放原贝l j 有关 还要考虑相 同货主的集装箱尽量集中堆放 避免重量相差大的集装箱堆放在一起 以 免重箱压坏轻箱 平衡集装箱堆放高度 避免某个箱位偏高 保证集装箱 堆放的安全性 稳定性 总的来说 目标可以归纳为避重就轻 避远就近 避高就低 从而实现箱位的合理分配 1 5论文的意义 随着我国经济的高速增长 以及电子商务的蓬勃发展和中国加入w r o 当前 物流活动呈现出前所未有的频繁 物流业已成为我国国民经济新的增长点 但是 目前我国铁路集装箱管理仍然比较落后 普遍面临着专业化程度低 高耗低效等 问题 目前我国大多数的铁路集装箱箱场作业调度依然依赖于人工经验 采用人 工安捧的方式 从而导致企业运输资源无法充分利用 运营成本过高 或者无法 满足客户的要求 因此 对箱场作业优化问题进行研究 是提升服务及资源利用 率的重要课题 集装箱装卸是作为发展敏捷作业的一个重要组成部分 是实现物 流现代化和自动化的基础及前提条件 不仅可以帮助运输企业提高服务水平 为 顾客提供快捷 准时 安全 舒适的服务 而且有助于企业节约运输成本 改善 资源利用效率 缩短生产周期 加速资金周转 实现资源的合理配置 6 2 集装箱装卸作业优化算法理论基础 在给定的约束条件下 在诸多可选方案中 寻找一个满足最小目标值的方案通 常是一个组合优化问题 这类问题往往具有层次性 多组合性 动态性以及多约 束条件等特点 在规模较小时 可以采用传统的运筹学方法如动态规划法 分支 限界法 回溯法等 但随着问题规模的增大 求解的复杂度也将呈指数级增长 这是实际问题所不能接受的 此时传统的运筹学方法也就显得无能为力 而目前 对于多约束 复杂性的组合优化问题 大多采用启发式算法研究解决 对于双层 集装箱的配载由于其约束条件较多 实时操作要求速度较高 且其某些特征与背 包问题相似 所以采用能尽快得到一个满意解的贪心启发式搜索算法 路径问题 由于其某些特征与t s p 相似 可以借鉴其求解的某些思想 根据其约束条件 和模 型特点 本文采用智能优化算法禁忌搜索算法来求解 对于集装箱箱位分配问题 可以描述为一个组合多目标优化问题 采用遗传算法可以对这一问题进行较好地 求解 2 1组合优化的基本概念 组合最优化问题 c o m b i n a t o r i a lo p t i m i z a t i o n 是通过对数学方法的研究去寻找 离散事件的最优编排 分组 次序或筛选等 是运筹学经典且重要的分支 所研 究的问题涉及信息技术 工业管理 交通运输 通信网络等诸多领域 该问题可 以用数学模型描述为 r a i n f x s s 嗽 o x d 2 1 2 2 2 3 其中取 为目标函数 颤x 为约束函数 x 为决策变量 d 为有限个点的集合 一个组合最优化问题可以用 d 只d 表示 其中d 表示决策变量的定义域 f 表示可 行解区域f x ix e d 颤x o f 中的任何一个元素称为该问题的可行解 f 称为 目标函数 满足f x r a i n f x ix e f 的可行解称为该问题的最优解 组合最优化 的特点是可行解集合为有限点的集合 由直观可知 只要逐个判断集合中的点是 否满足甙x o 及比较目标值 就一定可以得到该问题的最优解 因此现实生活中 的大量问题是从有限个状态中选取最好的 所以大量的优化问题是组合优化问题 7 2 1 1 多目标优化 实际的工程优化问题大多数是多目标优化问题 目标之间一般都是互相冲突 的 多目标优化很早就得到了人们的重视 到目前已经发展了较多的求解多目标 优化的方法 一个多目标优化如果存在非劣解 往往存在无穷多个 形成非劣解 集 在求解实际问题时 过多的非劣解是无法直接应用的 决策者只能选择令其 最满意的一个非劣解作为最终解 求最终解主要有三类方法 一类是求非劣解的 生成法 即先求出大量的非劣解 构成非劣解的一个子集 然后按照决策者的意 图找出最终解 另一类为交互法 不先求出很多的非劣解 而是通过分析者与决 策者对话的方式 逐步求出最终解 最后一类是事先要求决策者提供目标之问的 相对重要程度 算法以此为依据 将多目标问题转化为单目标问题进行求解 2 2智能优化算法 解决最优化问题的算法称为最优化算法 可以分为经典优化算法和启发式优化 算法 经典算法的确立可以从 g b d a n t z i g1 9 4 7 提出解决线性规划的单纯形 s i m p l e x m e t h o d 开始 但单纯形不是多项式算法 随后 k a m a k a 提出了椭球算 法 多项式算法 内点法 对于非线性问题 起初人们试图用线性优化理论去逼 近求解非线性问题 但效果并不理想 后来的非线性理论大多都建立在二次 凸 函数的基础上 也就用二次函数去逼近其他非线性函数 在此基础上提出许多优 化经典的优化算法 无约束的优化算法包括 最速下降法 s t e e p e s t 共轭梯度法 牛顿法 n e w t o n a l g o r i t h m 拟牛顿法 p s e u d o n e w t o n a l g o r i t h m s 信赖域法 约束优化算法包括 拉格朗日乘子法 a u g m o n t e t il a g r a a g i a na l g o r i t h m s 序列二次规划 s q p 等 随着社会的发展 实际问题越来越复杂 例如全局最优化问题 经典算法一般 都用得局部信息 如单个初始点及所在点的导数等 这使得经典算法无法避免局 部极小问题 全局最优化是n p h a r d f 司题 在多项式时间内使无法等到其绝对最优解 只能采取某些策略 使得在可接受 的时间内得到近似最优解 所以原有的经典算法不再试用 必须对其进行改进 或将其与启发式算法结合 大自然是神奇的 它造就了很多巧妙的手段和运行机制 受大自然的启发 人 们从大自然的运行规律中找到了许多解决实际问题的方法 对于那些受大自然的 运行规律或者面向具体问题的经验 规则启发出来的方法 人们常常称之为启发 式算法 h e u r i s t i ca l g o r i t h m 现在的启发式算法也不是全部来自然的规律 也 8 有来自人类积累的工作经验 启发式算法有不同的定义 一种定义为 一个基于直观或经验的构造的算法 对优化问题的实例能给出可接受的计算成本 计算时间 占用空间等 内 给出 一个近似最优解 该近似解于真实最优解的偏离程度不一定可以事先预计 另一 种是 启发式算法是一种技术 这种技术使得在可接受的计算成本内去搜寻最好 的解 但不一定能保证所得的可行解和最优解 甚至在多数情况下 无法阐述所 得解同最优解的近似程度 我比较赞同第二种定义 因为启发式算法现在还没有 完备的理论体系 只能视作一种技术 启发式算法的计算量都比较大 所以启发式算法伴随着计算机技术的发展 取 得了巨大的成就 4 0 年代 由于实际需要 人们已经提出了一些解决实际问题快速有效的启发式 算法 5 0 年代 启发式算法的研究逐步繁荣起来 随后 人们将启发式算法的思想 和人工智能领域中的各种有关问题的求解的方法相结合 提出了许多启发式的搜 索算法 其中贪婪算法和局部搜索等到人们的关注 6 0 年代 随着人们对数学模型和优化算法的研究越来越重视 发现以前提出 的启发式算法速度很快 但是解得质量不能保证 虽然对优化算法的研究取得了 很大的进展 但是较大规模的问题仍然无能为力 计算量还是太大 7 0 年代 计算复杂性理论的提出 n p 完全理论告诉我们 许多实际问题不可 能在合理的时间范围内找到全局最优解 发现贪婪算法和局部搜索算法速度快 但解不好的原因主要是他们只是在局部的区域内找解 得到的解不能保证全局最 优性 由此必须引入新的搜索机制和策略 才能有效地解决这些困难问题 这就 导致了超启发式算法 m e t a h e u r i s t i ca l g o r i t h m s 的产生 h o l l a n d 模拟地球上生物进化规律提出了遗传算法 g e n e t i ca l g o r i t h m 它的 与众不同的搜索机制引起了人们再次引发了人们研究启发式算法的兴趣 从而掀 起了研究启发式算法的热潮 8 0 年代以后 模拟退火算法 s i m u l a t e da n n e a l i n ga l g o r i t h m 人工神经网 络 a r t i f i c i a ln e u r a ln e t w o r k 禁忌搜索 t a b us e a r c h 相继出现 最近 演化 算法 e v o l u t i o n a r ya l g o r i t h m 蚁群算法 a n ta l g o r i t h m s 拟人拟物算法 量子算法等相继兴起 掀起了研究启发式算法的高潮 由于这些算法简单和有效 而且具有某种智能 因而成为科学计算和人类之间的桥梁 总而言之 智能优化算法是一种具有全局优化性能 通用性强 且适合于并行 处理的算法 这种算法一般具有严密的理论依据 而不是单纯凭借专家经验 理 论上可以在一定的时间内找到最优解或近似最优解 9 智能优化算法的特点 都是从任一解出发 按照某种机制 以一定的概率在整 个求解空间中探索最优解 由于它们可以把搜索空间扩展到整个问题空间 因而 具有全局优化性能 智能优化算法要解决的一般是最优化问题 最优化问题可以分为 1 求解一个函数中 使得函数值最小的白变量取值的函数优化问题 2 在一个解空间里面 寻找最优解 使目标函数值最小的组合优化问题 典型的组合优化问题有 旅行商问题 t r a v e l i n gs a l e s m a n p r o b l e m t s p 加 工调度问题 s c h e m i n gp r o b l e m o l 背包问题 k n a p s a c kp r o b l e m 以及装箱 问题 b i np a c k i n gp r o b l e m 等 2 3邻域函数 邻域函数是优化中的一个重要概念 它的作用就是指导如何由一个 组 解来产 生一个 组 新的解 邻域函数的设计往往依赖于问题的特性和解的表达方式 编 码 下面是对邻域函数给出的一般定义 令 s f f 为一个组合优化问题 其中s 为所有解构成的状态空间 f 为s 上的可 行域 伪目标函数 则邻域函数可定义为 种映射 即n s 一2 其涵义是对 于每个解i s 一些 邻近 i 的解构成i 的邻域s e s 而任意j s 称为i 的邻域 解或邻居 通常约定 j es 营i s 2 4禁忌搜索算法概述 禁忌搜索 t a b u s c a r c h 或t a b o os e a r c h 简称t s 的思想最早由g l o v e r 1 9 8 6 年 提出 它是对局部邻域搜索的一种扩展 是一种全局逐步寻优算法 是对人类智 力过程的一种模拟 t s 算法通过引入一个灵活的存储结构和相应的禁忌准则来避 免迂回搜索 并通过藐视准则来赦免一些被禁忌的优良状态 进而保证多样化的 有效探索以最终实现全局优化 迄今为止 t s 在组合优化 生产调度等领域取得 了很大的成功 禁忌搜索是人工智能的一种体现 是局部邻域搜索的一种扩展 禁忌搜索最重 要的思想是标记对应已搜索到的局部最优解的一些对象 并在迸一步的迭代搜索 中尽量避开这些对象 而不是绝对禁止循环 从而保证对不同的有效搜索途径的 探索 禁忌搜索涉及到邻域 禁忌表 禁忌长度 候选解 藐视准则等概念 1 0 2 4 1 禁忌搜索算法的流程 简单t s 的基本思想是 给定一个当前解 初始解 和一种邻域 然后在当前解的 邻域中确定若干候选解 若最佳候选解对应的目标值优于 b e s ts of a r 状态 则 忽略其禁忌特性 用其替代当前解和 b e s ts of a r 状态 并将相应的对象加入禁 忌表 同时修改禁忌表中各对象的任期 若不存在上述候选解 则在候选解中选 择非禁忌的最佳状态为新的当前解 而无视它与当前解的优劣 同时将相应对象 加入禁忌表 并修改禁忌表中各对象的任期 如此重复上述迭代过程 直到满足 停止准则 条理化些 则简单禁忌算法的步骤可描述如下 1 给定算法参数 随机产生初始解x 置禁忌表为空 2 判断算法中止条件是否满足 若是 则结束算法并输出最优结果 否则 继续以下步骤 3 利用当前解x 的邻域函数产生其所有 或若干 邻域解 并从中确定若干候 选解 4 对候选解判断藐视准则是否满足 若成立 则用满足藐视准则的最佳状态 y 代替x 成为新的当前解 即x y 并用与y 对应的禁忌对象替换最早进入 禁忌表的禁忌对象 同时用y 替换 b e s ts o 细 状态 然后转步骤 6 否 则 继续以下步骤 5 判断候选解对应的各对象的禁忌属性 选择候选解集中非禁忌对象对应的 最佳状态为新的当前解 同时用与之对应的禁忌对象替换最早进入禁忌表 的禁忌对象元素 6 转步骤 2 邻域函数 禁忌对象 禁忌表和藐视准则 构成了禁忌搜索算法的关键 其中 邻域函数沿用局部邻域搜索的思想 用于实现邻域搜索 禁忌表和禁忌对象的设 置 体现了算法避免迂回搜索的特点 藐视准则 则是对优良状态的奖励 它是 对禁忌策略的一种放松 上述算法仅是简单的一种禁忌搜索算法框架 对各关键环节复杂和多样性的设 计则可构造出各种禁忌搜索算法 同时算法流程中的禁忌对象可以是搜索状态 也可以是特定搜索操作 还可以是搜索目标值等 同时 与传统的优化算法相比 t s 算法的主要特点是 1 搜索过程中可以接受劣解 因此具有较强的 爬山 能力 2 新解不是在当前解的邻域中随机产生 而或是优于 b e s ts of a r 的解 或 是非禁忌的最佳解 因此 选取优良解的概率远远大于其他解 由于t s 算法具有灵活的记忆功能和藐视准则 并且在搜索过程中可以接受劣 解 所以具有较强的 爬山 能力 搜索时能够跳出局部最优解 转向解空间的 其他区域 从而增强获得更好的全局最优解的概率 所以t s 算法是一种局部搜索 能力很强的全局迭代寻优算法 但t s 也有明显的不足 1 对初始解有较强的依赖性 好的初始解可使t s 在解空间中搜索到好的解 而较差的初始解则会降低 i s 的收敛速度 2 迭代搜索过程是串行的 仅是单一状态的移动 而非并行搜索 要设计一个禁忌搜索算法 需要确定算法的以下环节 1 初始解和适配值函数 2 邻域结构和禁忌对象 3 候选解选择 4 禁忌表及其长度 5 藐视准则 6 集中搜索和分散搜索策略 7 终止准则 2 5 遗传算法概述 近年来 随着人工智能应用领域的不断扩大 传统的基于符号处理机制的人工 智能方法在知识表示 信息处理和解决组合爆炸等方面所遇到的困难越来越明显 从而使得寻求一种适合于大规模问题并具有自组织 自适应 自学习能力的算法 成为有关学科的一个研究目标 大自然为我们解决各种问题创造了灵感 遗传算 法 g e n e t i ca l g o r i t h m s 简称g a 就是j h o l l a n d 于1 9 7 5 年受生物进化论的启发而提出 的g a 是基于 适者生存 的一种高度并行 随机和自适应的优化算法 它将问题 的求解表示成 染色体 的适者生存过程 通过 染色体 群的一代代不断进化 包括复制 交叉和变异等操作 最终收敛到 最适应环境 的个体 从而求得问 题的最优解或满意解 g a 是一种通用的优化算法 其编码技术和遗传操作比较简 单 优化不受限制性条件的约束 而其两个最显著特点则是隐含并行性和全局解 空间搜索 目前 随着计算机技术的发展 g a 愈来愈得到人们的重视 并在机器 学习 模式识别 图像处理 神经网络 优化控制 组合优化 v l s i 设计 遗传 学等领域得到了成功应用 g a 是基于自然选择 在计算机上模拟生物进化机制的寻优搜索算法 在自然 界的演化过程中 生物体通过遗传 传种接代 后代与父辈非常相像 变异 后 代与父辈又不完全相像 来适应外界环境 代又一代地优胜劣汰 发展进化 g a 则模拟了上述进化现象 它把搜索空间 欲求解问题的解空间 映射为遗传空间 即把每一个可能的解编码为一个向量 二进制或十进制数字串 称为一个染色体 c h r a m a s a m e 或个体 向量的每一个元素称为基因 g e n e s 所有染色体组成群 体 p o p u l a t i o n 或集团 并按预定的目标函数 或某种评价指标 如商业经营中的 利润 工程项目中的最小费用等 对每个染色体进行评价 根据其结果给出一个适 应度的值 算法开始时先随机地产生一些染色体 欲求解问题的候选解 计算其 适应度 根据适应度对诸染色体进行选择 交换 变异等遗传操作 剔除适应度 低 性能不佳 的染色体 留下适应度高 性能优良 的染色体 从而得到新的群体 由于新群体的成员是上一代群体的优秀者 继承了上一代的优良性态 因而明显 优于上一代 g a 就这样反复迭代 向着更优解的方向进化 直至满足某种预定的 优化指标 2 5 1遗传算法的基本概念 基本遗传算法 s i m p l e g e t i c a l g o r i t h m s 简称s g a 又称简单遗传算法或标 准遗传算法 是由g o l 曲e f g 总结出的一种最基本的遗传算法 其遗传进化操作过 程简单 容易理解 是其它一些遗传算法的雏形和基础 1 种群 p o p u l a t i o n 和个体 l n d i v i d u a l 遗传算法在求解问题时是从初始给定的多个解开始搜索的 这初始给定的多个 解的集合称为一个种群 种群是问题的解空间的一个子集 种群中的每个解称为 个体 2 染色体 c h r o m o s o m e 与基因 g e n e 基因组 g 蜘eg r o u p 对种群中每个个体进行映射变换得到的编码串叫做所谓的染色体 染色体上的 每一位叫做基因 染色体上一个有效信息段叫做基因组 3 适应度函数 f i t n e