（计算机软件与理论专业论文）遗传算法在动态车辆调度问题中的研究.pdf

摘要 随着信息技术和通讯技术的飞速发展使得实时地获取和处理信息成为可能， 为了获得更多的经济利益，许多现代企业已经充分地利用这些技术手段来对自身 资源进行科学管理。物流配送中的动态车辆调度问题就是现代企业要考虑到的一 种节约成本的重要方式。本文针对物流配送中的动态车辆调度问题，提出了用改 进的遗传算法来求解该问题。 首先，研究了动态车辆调度问题的知识表示方法，将动态车辆调度问题分解 成相互关联的动态车辆线路安排问题和静态的车辆调度问题，简化了问题原型。 其次，建立了解决问题的模型并分析了模型各部分的功能。根据实际情况， 改进了适应值函数及惩罚函数；采用启发式方法解决了单一车辆线路安排问题； 通过速度预警模型预测速度以确定车辆行驶路径。 然后，提出了动态车辆调度的仿真实验模型，引入了触发器的概念来处理四 类触发事件；提出了用插入的启发式方法来解决新客户请求。 最后，通过仿真算例验证了遗传算法求解动态车辆调度模型及遗传算法在解 决动态调度问题中的科学性和有效性。 本文的研究有一定的理论意义和实用价值。在物流配送系统中应用实时信息 可以使规划过程动态性更强，结果更趋近实际；导航系统的使用方式也可以为以 后的研究提供数据支持；规划目标是尽量节省配送中心服务成本，以更好地客户 服务，可以使配送服务更快捷。 关键词：物流配送；遗传算法；动态车辆调度；启发式算法；触发器 a b s t r a c t t h e r a p i dd e v e l o p m e n to fc o m m u n i c a t i o na n di n f o r m a t i o nt e c h n o l o g ym a k e si t p o s s i b l et oo b t a i na n dp r o c e s sd a t at oq u i c k l ya tap a r t i c u l a rr e a lp o i n to ft i m e i n o r d e rt o g a i nm o r ee c o n o m i cp r o f i t s ，m a n ym o d e r ne n t e r p r i s e s h a v ea l r e a d y s u f f i c i e n t l ya p p l i e dt h e s et e c h n o l o g i e si n t ot h es c i e n t i f i cm a n a g e m e n to ft h e i ro w n r e s o u r c e s t h es c h e d u l i n gp r o b l e mi nl o g i s t i c sa n dd i s t r i b u t i o no fd y n a m i cv e h i c l e s i sac o s t - e f f e c t i v ew a yt h a tam o d e r ne n t e r p r i s es h o u l dt a k ei n t oa c c o u n t t h i sp a p e r p r o p o s e dt h a ta ni m p r o v e dg e n e t i ca l g o r i t h ms h o u l db eu s e dt os o l v et h ed y n a m i c v e h i c l es c h e d u l i n gp r o b l e mi nl o g i s t i c sa n dd i s t r i b u t i o n t h ep a p e rf i r s t l ys t u d i e dt h ei s s u eo fk n o w l e d g er e p r e s e n t a t i o ni nd y n a m i c v e h i c l e s c h e d u l i n gp r o b l e ma n dd e c o m p o s e d t h ed y n a m i cv e h i c l e s c h e d u l i n g p r o b l e m si n t oi n t e r r e l a t e dp r o b l e m sw h i c hi n c l u d et h er o u t i n go fd y n a m i cv e h i c l e s a n ds t a t i cv e h i c l es c h e d u l i n gp r o b l e m sa st os i m p l i f yt h ep r o t o t y p eo ft h ep r o b l e m s e c o n d l y , t h ep a p e re s t a b l i s h e dam o d e lt os o l v et h ed y n a m i cv e h i c l ep r o b l e m s a n dd e s c r i b e dt h ef u n c t i o n so f e a c hp a r to ft h em o d e l t h ef i t n e s sf u n c t i o n sa n dt h e p e n a l t yf u n c t i o n sc o u l db ei m p r o v e da c c o r d i n gt ot h ea c t u a ls i t u a t i o n ，t h e nt h e h e u r i s t i cm e t h o dw a su s e dt os o l v et h ea r r a n g e m e n t so fv e h i c l e si nas i n g l el i n e t h e p a p e ra l s ou s e dt h ef o r e c a s t e dm o d e lt op r e d i c tt h es p e e dr a t eo fv e h i c l e ss o a st o d e t e r m i n et h ep a t ho fv e h i c l e s t h i r d l yt h ep a p e rp r o p o s e d ad y n a m i cv e h i c l es c h e d u l i n gs i m u l a t i o nm o d e la n d i n t r o d u c e dt h ec o n c e p to ft r i g g e r st oh a n d l et h ef o u rt y p e so ft r i g g e re v e n t s a n i n s e r t i o nh e u r i s t i cm e t h o di sp r o p o s e dt os o l v et h ei s s u e sr a i s e db yn e wc l i e n t s f i n a l l y ，t h es c i e n t i f i cf e a t u r e sa n de f f e c t i v e n e s so fg e n e t i ca l g o r i t h ma n di t s u s a g ef o rd y n a m i cv e h i c l es c h e d u l i n gm o d e lw e r ev e r i f i e dw i t hs i m u l a t i o ne x a m p l e s t os o l v et h ed y n a m i cs c h e d u l i n gp r o b l e m t h i sr e s e a r c hi so fg r e a ts i g n i f i c a n c eb o t hi nt h e o r ya n du t i l i t ys i n c et h e r e a l t i m ei n f o r m a t i o ni nl o g i s t i cd i s t r i b u t i o nc a nm a k et h er o u t i n gp r o c e s sm o r e d y n a m i ca n dt h er e s u l tc l o s e rt or e a l i t y ；t h et o p o l o g yo fn a v i g a t i o ns y s t e mc a n p r o v i d ed a t as u p p o r tf o rh o m o l o g o u sr e s e a r c h e s ；t h eo b je c to ft h i sp l a ni st or e d u c e t h ec o s to fs e r v i c ed i s t r i b u t i o nc e n t e r sa n dp r o v i d eb e t t e rs e r v i c ef o rt h ec u s t o m e r s w h ic hc a nm a k et h ed is t r i b u t jo ns e r v ic ef a s t e ra n db e t t e r 1 i k e yw o r d s ：l o g i s t i c sd i s t r i b u t i o n ；g e n e t i ca l g o r i t h m ；d y n a m i cv e h i c l e s c h e d u l i n g ；h e u r i s t i ca l g o r i t h m ；t r i g g e r i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：荫 嘲易日期：h 。年钼日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容 编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密冈。 ( 请在以上相应方框内打“”) 作者签名：苌潞罨jj 荡日期：勺年6 月日 导师签名：多色日期：知内年乡月多 日 1 1 研究背景及意义 第一章绪论 在现今的运输界里，物流是一个比较时髦的词汇。什么是物流，简单地讲， 物流就是商品的流通，但是随着商品经济的发展，物流已经不仅仅是商品流通本 身，它所指的范围特别广泛，包括了商品的运输、储存、配送、装卸、保管、物 流信息管理等相互关联的活动。虽然物流的概念早在本世纪5 0 年代就已经被提 了出来，但物流真正发展起来，还是最近1 0 年内的事情。在过去l0 年中，因为 物流在提高物资流通速度、节省仓储资金、旅途费用等有效手段方面的作用，而 受到了越来越多的货物的主人的重视。在物流业高速发展的今天，物资在流通过 程中的各个环节信息，比以往任何时候都更加重要，其中包括每种物资到达每个 地点的时间和数量、离开每个地点的时间和数量、旅途时间和数量、生产量以及 需求量等各种信息。这些信息对整个生产过程的控制和管理都将起到至关重要的 作用。因此，现代企业要合理地利用社会和自然资源，尽量地减少企业的成本， 相对地提高企业的竞争力，在这个竞争激烈的社会占据一席之地，都要求企业大 力加强物流管理，减少物资的消耗量，从而尽可能多地获取经济效益。概括讲来， 物流的作用主要有以下几点：( 1 ) 简化交易，很明显地，物流业的存在大大地简 化了交易的结构和过程。( 2 ) 降低成本、提高效率，可以说，物流不仅可以提供 了更专业的服务，还可以实现规模经济，所带来的低成本与高效率。( 3 ) 提高服 务水平，一定程度上，物流可以更好地满足消费者的需求，减少缺货发生的可能， 与营销达成有效配合，提供更为专业的物流的服务。 配送是物流中一种特殊的、综合的活动形式，是商流与物流的紧密结合，包 含了商流活动和物流洁动，也包含了物流中若干功能要素的一种形式【2 】。物流配 送有三个系统目标。( 1 ) 服务目标：物流系统是“桥梁、纽带”，其作用不言而喻， 物流系统是流通系统的一部分，它具体地联结着生产与再生产、生产与消费等环 节，因此要求有很强的服务性与关联性。物流系统采取送货、配送等形式，就是 其服务性的体现，物流系统管理的好坏也直接影响到服务的好坏。在技术方面， 近年来出现的“准时供货方式、“柔性供货方式 等，也是其服务性的表现。 ( 2 ) 快速、及时目标：及时性不但是服务性的延伸，也是流通对物流提出的要求。 快速、及时既是一个传统目标，更是一个现代目标。其原因是随社会大生产发展， 这要求更加强烈了。在物流领域采取的诸如直达物流、联合运输、高速公路、 时间表系统等管理和技术，就是这一目标的体现。( 3 ) 节约目标：节约是经济领 域的重要规律，在物流领域中除流通时间的节约外，由于流通过程消耗大而又基 本上不增加或提高商品使用价值，所以领先节约来降低投入，是提高相对产出的 重要手段。配送中常用的配送工具是车辆，因此关联到了车辆调度问题。 车辆调度问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 最早是由d a n t z i g 等在1 9 5 9 年 首次提出来的。关于动态v r p 的研究最早是在2 0 世纪7 0 年代。讲的是，在 车辆运送货物往返的过程中，要考虑交通拥塞、天气变化、交通事故、车辆故障、 新订单的到来及取消等实时信息，车辆的路线安排也要随之改变。传统的v r p 理论没有把这些状况考虑进来，所有的信息都是静态的，是理想化的模型，因此 无法解决这些问题，这才有了所谓的动态车辆调度问题( d y n a m i cv e h i c l er o u t i n g p r o b l e m ，d v r p ) 。在这种d v r p 问题中，物流服务提供商就有必要对用于物流车 辆进行实时监控、导航、实时接收和发送调配信息，以方便在问题条件发生变化 后，能够及时、准确、有效地调整物流车辆的行车方案，减少不确定因素对物流 计划造成的负面影响，保障物流任务顺利完成。 现代物流业的飞速发展为社会经济的发展作出了巨大的贡献，但同时也带来 了很多的社会问题，如运输车辆的燃油消耗所造成的空气污染，包装所带来的废 弃物污染，运输过程中所带来的噪声污染、资源浪费、城市道路拥堵等。而车辆 调度问题是解决这些问题的一个关键环节，处理好了这个问题，就处理好了大部 分与之相关的问题。因此，本文针对车辆调度问题中出现的越来越多的不确定因 素，提出了用遗传算法来求解动态车辆调度问题。之前，有过许多用遗传算法来 求解车辆调度问题的文章，但是这类文章往往是建立在假设的基础之上的，而我 们面对的是现实的问题，现实中的情况恰恰是会与理想中的情况有所差别的，甚 至会出现背离，这也是本文中的课题要解决的主要问题。 1 2 国内外相关研究 国外物流业的发展特点概括地讲具有以下几点：物流行业少数规模很大的企 业与大量、分散的中小企业并存；国外发达国家在包裹运输、快件运输、零担运 输以及城间客运等方面都由全国甚至国际范围的企业集团，主导着相关行业的发 展。由于物流市场的多样化，为大量分散的中小企业提供了很大的经营空间， 特别是在区域运输、中短途运输、货物整车运输以及客运旅游和专车或包车运输 等方面，中小型企业由于机动性好、一次性资本投入少、成本低等优势，仍发挥 着十分重要和积极的作用。根据经合发组织( o e c d ) 1 9 8 7 年对部分成员国按企业 拥有车辆数对营业性企业进行的分类，瑞典6 0 企业为只有一辆车的企业或个 体经营者，英国6 0 以上的企业不足5 辆车，葡萄牙9 0 的企业不足3 辆车， 丹麦8 l 的企业为个体经营者，西班牙9 8 以上的企业在5 辆和5 辆车以下、 平均每个企业拥有车辆数为1 4 辆。物流进一步向着专业化方向发展，国外发达 2 国家社会分工和运输需求进一步深化，促使物流市场细化，物流进一步向着专业 化方向发展。许多汽车运输企业均按照专业化分工的要求建立起来，如专为搬家 服务的搬家运输公司、专门运送汽车产品的汽车专运公司、以及运输各类液体( 油 品、化工产品) 以及干散货的其它专运运输公司等等。即使许多大型汽车运输企 业，也根据专业化分工，分化成为若干专业化的子公司，如澳大利亚t n t 运输 集团公司在澳大利亚本土有4 0 多个各类专业化子公司，各子公司经营业务分别 涵盖着除传统的整车、零担外，还包括车辆租赁、信件、服装、甚至花卉等等。 国外发达国家的运输组织和管理方法都较为先进，大中型汽车运输企业为了 提高服务质量和管理水平，一般都广泛地采用了现代化的通讯和计算机技术作为 运输业的组织和管理的手段。在同常的管理方面，一般都建立了生产经营、车辆 调度、保养维修、人事劳资、财务统计等方面的计算机管理信息系统，以提高工 作效率，以及决策的科学性。在车辆调度方面，广泛地采用了车载通讯技术，一 些大公司甚至采用了卫星通讯以及导航星测时与测距全球定位系统( n a v i g a t i o n s a t e l l i t et i m i n ga n d r a n g i n gg l o b a lp o s i t i o ns y s t e m ，g p s ) 技术，以便于能够及时 而准确地掌握车辆的动态信息，从而对车辆进行科学调度，减少空驶里程，提高 运输效率。在运输服务方面，一些大公司利用条形码技术将货物的品名、规格、 数量、收发货人及地点等信息输入计算机，通过电子数据互换( e l e c t r o n i cd a t a i n t e r c h a n g e ，e d i ) 实现计算机异地信息的传输，建立起货物追踪系统，以便货主 能够及时地了解所托运货物的动态信息。随着国外先进设备的引进，我国一些大 城市相继尝试将通用分组无线业务( g e n e r a lp a c k e tr a d i os e r v i c e ，g p r s ) 与六氟 化硫气体绝缘全封闭配电装置( g a si n s t u l a t e ds w i t c h g e a r ，g i s ) 等新技术，并将之 运用于车辆调度，例如重庆市将g i s 技术引入到了公交系统管理中，从而开发 了“重庆市公共交通信息管理系统”；北京市车辆总公司开发了我国第一个综合 性车辆i t s 项目；上海市第一次应用g p s 技术为9 8 1 路公交进行线路安排，在 浦东成功投入运行；杭州市是我国第一个将g p s 定位技术应用到车辆调度管理 的城市。 在理论研究方面，也有许多较成功的研究实例，其研究的重点主要还是车辆 的线路调度安排：陈湘州等针对基于路径组合编码的遗传算法应用于求解v r p 问题时，顺序交叉算子局部寻优能力不足的缺陷，引入一种进化逆转算子，改进 了遗传算法求解v r p 问题时的局部搜索能力【43 1 。孙福春等提出了一个调度算法 来解决车辆派遣的问题，并在此基础上利用遗传算法给出车辆行驶的次优路径， 给出了车辆调度相应的数学模型【4 4 1 。杜明等提出利用遗传算法来解决v r p 径问 题，基于遗传算法的基本思想设计了合适的算法程序，通过实验表明了遗传算法 能够有效地求解v r p 问题【45 1 。还有些论文也是关于这方面的【3 。1 1 】，一般都采 用改进节约法与随机法相结合的手段构造了初始解群体以增加解的多样性，对遗 3 传算法中较优的一部分染色体进行了禁忌搜索以使搜索更容易跳出局部最优，同 时加快搜索初期的搜索速度。总而言之，类似这样的文献还有许多 1 2 - 2 0 ，但主 要是关于路线安排的文章，而专门针对动态车辆调度的问题并没有全面考虑到。 在技术应用方面，从目前国内的办公自动化系统现状看，随着互联网的发展， 我国的应用技术也加入了许多先进理念，但是由于软件开发商不太注重像车辆管 理这样边缘性r 常办公管理系统的开发，没有做到企业数据的真正共享，企业的 高层也意识不到规范车辆管理给企业带来的好处和收益，所以对于它的开发和建 设投入的力度还很不够。随着车辆调度在企业物流中和业务运作中的作用突显， 国家也相应地出台了相关政策对企业车辆进行有效的监管。近些年来，随着买方 市场的形成，企业对物流领域中存在的“第三利润源泉”开始有了比较深刻的认 识，优化企业内部物流管理，降低物流成本成为目前多数国内企业最为强烈的愿 望和要求。我国在各方面的技术都取得了巨大突破和成就，2 0 0 3 年我国铁路营 业里程7 3 万公里，比l9 7 8 年增加4 l ，公路里程达17 9 6 万公里，比l9 7 8 年 增加10 2 ，其中高速公路3 力公里，内河航道里程1 2 2 万公里；2 0 0 3 年沿海 港口万吨级及以上深水泊位达到近6 0 0 个，运输线路和作业设施有了较大的改 善。以发展现代物流为核心的物流园区、物流中心、配送中心等大批涌现。随着 经济发展和技术进步，在共用通信网的规模、技术层次、服务水平方面都发生了 质的飞跃；2 0 0 3 年，电话用户总数达5 3 2 亿户，其中固定电话2 6 3 亿户，移动 电话2 6 9 亿户。互联网上网人数达7 9 5 0 万人，上网计算机达到3 0 8 9 万台，网 站总数达到5 9 6 万个，互联网的应用逐步普及；19 9 8 年以来，山东省经委以优化 企业内部物流管理为切入点推进现代物流发展的试点工作，得到山东省及其周边 省份许多企业的广泛认同和参与。这些都足以说明这样的问题，相对来说，我国 物流活动的发展水平虽然还是比较的低，加强企业内部物流管理仍然是全社会物 流活动的重点，但是也取得一定的成果，在曲折中前进着。与此同时，专业化的 物流服务需求已经出现且发展势头极为迅速。其一是跨国公司在中国从事生产经 营活动、销售分拨活动以及采购活动过程中，对高效率、专业化物流服务的巨大 需求，这是带动我国物流产业发展的一个十分重要的市场基础。其二是国内优势 企业对专业化物流服务的需求。目前，我国一批颇具竞争实力的优势企业，例如 海尔集团、青岛啤酒、上海宝钢等，在市场扩张的过程中，在不断优化企业内部 物流系统的基础上，已开始尝试和利用专业化物流服务。其三是在一些新兴的经 济领域中，如私营企业、快递服务行业以及电子商务领域等，也产生和存在着一 定规模的物流服务需求。 当前，中国物流产业已进入发展阶段，形成了一种热潮。这种热潮从三个不 同的层面来看，表现为以下三个不同的方面：( 1 ) 从微观层面，企业物流管理和 物流企业均有一定程度的发展。一是许多实行连锁经营的零售企业建立了自己的 4 配送中心，为企业内部的连锁网点提供物流配送服务，一些连锁企业配送商品比 例已经超过企业经营品种的5 0 。二是部分制造业企业也在探索和尝试物流管 理方面的改革。三是出现一批定位于全方位物流服务的专门的物流企业。( 2 ) 从 地方政府层面，目前一些经济发展较快地区的地方政府，如深圳、北京、上海等 对促进物流产业的发展给予了高度重视，并已开始着手研究和制定地区物流发展 的规划和有关促进政策。( 3 ) 宏观层面的中央政府有关部门。如国家经贸委、国 家计委、国家内贸局、国务院发展研究中心等也从不同角度关注着我国物流产业 的发展，并积极地研究促进物流产业发展的有关政策。 综上所述，我国的智能车辆调度的研究起步比较晚，无论在理论研究还是在 技术应用、工具手段上都和国外的标准存在着一定的差距，物流产业发展仍然面 临着较大的市场需求的约束：专业化物流服务的方式还是很有限的，物流企业的 经营管理水平也有待提高；低水平的物流基础设施和装备条件严重影响着物流效 率的提高；物流产业发展面临着较大的制度约束。同时，由于我国的特殊国情， 我国的车辆调度智能化又不能完全照搬国外的模式。当前，我国的车辆调度模式 主要以路线安排为主的模式，所以我国的研究主要集中在路线安排方面的优化。 因此，我国的车辆调度研究水平与国外还有很大的差距，还处于起步的阶段，还 有一段很长很艰巨的路要走。 1 3 主要工作内容 通过对国内外相关研究的综合分析，使用计算机仿真来研究复杂物流配送系 统中的动态车辆调度问题。首先研究了动态车辆调度问题，并在此基础上设计了 动态车辆调度模型，最后通过仿真实验，根据实验数据，作了进一步的分析。本 文的具体研究内容如下： ( 1 ) 研究了动态车辆调度问题的知识表示方法。分析了动态车辆调度问题的 实质，将该问题化为若干个子问题来进行解决。 ( 2 ) 提出了动态车辆调度模型。改进了适应值函数；在单一车辆线路安排中 采用启发式方法来解决；通过速度预警模型来预测速度以确定车辆行驶路径；作 了动态车辆调度问题的复杂性分析。 ( 3 ) 设计了动态车辆调度的仿真实验模型。在模型的基础上，设计了模拟器 来模拟四种事件触发器，分别来处理四种事件的发生；提出了插入的启发式算法 来解决新客户事件引发的染色体长度改变的问题。 ( 4 ) 动态车辆调度问题的仿真系统研究与算例验证。实现了基于该模型算例 的动态车辆调度系统；并通过算例验证了遗传算法求解动态车辆调度模型及遗传 算法在解决此类问题中的有效性。 1 4 论文结构 第一章首先，从智能交通系统和现代物流在国民经济中的地位出发，论述 了选题背景和意义。其次，在对d v r p 的国内外发展和研究现状进行概述的基 础上，指出研究中存在的问题。最后对本论文研究的主要工作和章节安排进行了 介绍。 第二章首先用车辆调度问题引出动态车辆调度问题，指出了为什么要采用 动态车辆调度；再次研究了动态车辆调度问题的表示方法并简单介绍了解决车辆 调度问题的一些方法。然后介绍了遗传算法的概念及其主要操作，其中包括交叉、 选择、变异等操作；论述了遗传算法的研究方向和研究范畴；综述了遗传算法的 特性，分析了遗传算法的优缺点，参数选择问题等可能会在引用遗传算法中遇到 的问题。 第三章分析了动态车辆调度的必要性，概括描述了动态车辆调度问题；提 出了动态车辆调度问题的模型；最后建立了一种改进的遗传算法来处理动态车辆 调度中的静态子问题，并做了车辆调度问题的复杂性分析。 第四章进行了计算机仿真实验，对可能影响到实验的数据进行了分析，其 中包括静态数据和动态数据，提出了基于动态速度曲线的预警模型来预测下一时 刻的速度；然后提出了事件模拟器，对四种类型的事件实时触发处理；针对新客 户送货请求的提出，提出了在遗传算法中进行了启发式的插入操作；最后通过仿 真实验，求出了实验结果，并对实验结果进行分析。 总结与展望对论文工作进行了总结，并给出论文进一步研究的内容和方向。 6 2 1 动态车辆调度问题 第二章相关技术 车辆调度问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 主要包括车辆送货路线安排问 题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 和车辆调度问题( v e h i c l es c h e d u l i n gp r o b l e m ， v s p ) ，在学术界被认为是n p 难问题。车辆调度问题同时也具有复杂性和多约束 性等特点，是一个多目标组合优化问题，一般来说，很难得到其最优解。v r p 问题同时包括带时间窗的v r p ( v r p t w ) 和随机v r p ( v r p r a m ) 等问题【2 。 目前，我国大部分的物流配送中心( 如中心配送、大中型超市的货物运载等) 的车辆调度仍大部依赖于人工经验，从而采取人工安排的方式，这种方式必然会 导致企业运输资源无法被充分利用，运送成本过高，或者无法满足客户的要求等 问题。因此，企业应该把整个物流资源进行统一规划，统一车辆调度管理，从而 相对地节约企业成本，提高价值空间和企业利润。在整个管理的过程中需要考虑 到的成本因素主要有。 ( 1 ) 车辆成本：指车辆在运送货物往返的过程中消耗的汽油成本及车辆的折 旧成本，该成本主要取决于车辆行驶距离的远近，距离越短，则成本越小，这也 是企业为了节约成本而主要考虑的因素之一。 ( 2 ) 人员成本：指支付给车辆的架驶员的工资和福利等，该成本一般和运载 车辆的数目成正比，车辆一定的情况下会是比较固定的成本。 ( 3 ) f l 艮务提前成本：指车辆在发送货物时，提前到达客户要求地点所造成的 车辆等待的成本，如支付停车位等的成本。 ( 4 ) 服务延迟成本：指车辆到达客户处的时间，超出了与客户约定的时间， 但在客户尚可接受的时间内所应支付的罚款。 传统的动态车辆调度解决办法难以满足现代化作业的要求。一方面，服务客 户区域在扩大和零售商数目的增加等问题的出现，使得解决办法的复杂性呈几何 倍数增长；另一方面，面对客户临时提出的需求，考虑到客户的利益，这就向我 们提出了实时性的要求，要求配送中心能够实时处理，立即反应。同时，传统的 解决办法往往是理想化的模型，既没有考虑到瞬息万变的信息，也没有考虑可以 影响到交通状态发生变化的突发事件，因此动态车辆调度问题成了学者们研究的 课题，开始发挥出静态的或者说是传统的车辆调度算法无法弥补的巨大作用。 因此，动态车辆调度问题可以这样分析，本质上，车辆路径问题都具有“提 供商与“消费者”这两个相互关联的利益实体；他们之间的关系是由“消费者 7 给出的、并经“提供商”确认过后的订单而确定；确定后，前者是车辆路径问题 的决策主体，他要利用车辆为后者提供取货或送货服务。送货过程就是提供商在 收到一个或多个顾客订单后，根据订单的货物要求，确定了供货地点，然后根据 时间约束和地点要求，为可用车辆安排任务及行车路径，从而去组织运输服务。 综上所述，动态车辆调度问题可以分为动态车辆路径问题( d y n a m i cv e h i c l er o u r i n gp r o b l e m ，d v r p ) 、和车辆调度问题( v s p ) 来进行解决，而多个车辆的调度问 题又可化为单一车辆的调度问题来解决。 2 2 动态车辆调度问题相关研究 针对车辆调度问题中出现的一系列问题，人们认识到了人工作业方式的一些 不足。近年来，学者们用了遗传算法、精确算法和近似算法等来解决这一组合优 化问题，并且取得了一定的成果。精确算法主要有拉格朗日分解法，分枝定界法， k 树状算法和列向量法等。其中，n o b e r t 和l a p o r t e 提出了多种分枝定界法【2 2 1 。 s i m c h i 提出结合列向量法和分枝定界法解决v r p 整数规划问题。c h r i s t o f i e d s 采 用动态规划，延伸空间变量法来解决v r p 问题1 23 1 。f i s h e r 提出用两阶段优化方 法，解决带时间窗的v r p 问题【2 引。近似算法方面，l a p o r a t e 采用禁忌搜索法， 提高了求解v r p 问题的精度1 2 引。o s m a n 采用2 o p t 组合优化方法，以求解交换 不同路线顶点的多目标问题【26 1 。蔡延光采用模拟退火和禁忌搜索，以求解带时 间窗的多重运输调度问题【27 1 。李军采用序列优化启发式算法，以求解组合配送 问题1 2 引。李显生设计了分派节约启发式算法，以求解车辆高度的多目标决策模 型怛引。王舒萍提出的先跟据客户间的距离进行聚类，再使用遗传算法的办法， 以求解带有时间窗而且配送车辆数目一定的车辆分发与线路安排问题【30 1 。z e d d i n i 针对动态车辆调度问题，提出了一种基于自组织的和多代理系统，以响应新 的请求的模型【3 。在解决动态车辆调度的问题用到遗传算法时，经常结合其它 算法的混合算法来求解该问题。 现阶段，在物流系统中的动态车辆调度问题存在两个主要的需要解决的问 题。2 0 世纪9 0 年代以来，信息技术的不断发展，互联网与电子商务应用的广泛 普及，大大降低了国际贸易和国际物流的运营成本，使国际物流得以长足发展。 目前，国际物流的效率在很大程度上取决于新兴信息技术的应用程度，其发展趋 势是建立智能化运输系统。通过发展运输实时跟踪定位系统、运输路径优化的地 理信息系统、全球网络定位系统、三维条形码技术和红外线感应系统等新型信息 技术，将运输仓储电子化管理过程与网络财务支持系统、电子商务融为一体。现 代物流业的一个发展趋势是绿色物流，即在物流业发展中将环保和可持续问题放 在重要位置。其目标是解决好与物流相关的能源、环境、交通安全等问题。目前， 日本工f 抓紧制定新综合物流施政大纲，其重点之一就是要减少大气污染物排 8 放，加强地球环境保护，对可利用的资源进行再生利用，实现资源、生态和社会 经济良性循环，建立适应环保要求的新型物流体系。发达国家的经验证明，发展 现代物流业，关键是具备一支优秀的物流管理队伍。在物流人才需求的推动下， 美国已经形成了较为合理的物流人才教育培训体系，许多著名的高等院校设置了 物流管理专业，其中部分高等院校设置了物流方向的研究生课程和学位教育，形 成了一定规模的研究生教育系统。在美国物流管理委员会的组织和倡导下，全面 开展物流业职业资格认证制度，如仓储工程师、配送工程师等职位。所有物流从 业人员必须接受职业教育，经过考试获得上述工程师资格后，才能从事有关的物 流工作。一方面，传统的经营组织方式，物流活动主要依靠企业内部组织的自我 服务完成。这种以自我服务为主的物流活动模式在很大程度上限制和延迟了高效 率专业化物流服务需求的产生和发展。在企业优化内部物流管理、提高物流效率 的过程中，也存在着企业内部物流活动逐步社会化的发展趋势及其对社会化物流 的潜在需求。但由于市场发育和现代企业制度改革的不完善，企业无法将其内部 低效率的物流设施和组织实施有效的剥离。这就使得企业不得不继续沿用以往的 物流方式。为适应市场竞争的需要，一些大型工业企业开始重视现代物流技术的 应用，以订单为中心改造现有业务流程，在生产组织、原材料采购及产品销售、 配送和运输等方面实行一体化运作，降低库存，减少资金占用。商业企业则加快 改制重组，发展连锁经营、统一配送和电子商务的步伐。近几年来，通过改造传 统国有运输、仓储企业，发展民营物流企业，积极引进外资物流企业，以及实现 生产流通企业物流社会化等途径，专业化物流企业发展迅速并逐步形成了不同所 有制形式、不同经营模式和不同经营规模的专业物流企业共同发展的格局。物流 的服务功能增强，服务水平提高，采用现代物流技术的工商企业使物流成本降幅 更大。另外，物流企业经营管理水平较低，多数从事物流服务的企业缺乏必要的 服务规范和内部管理规程，经营管理很粗放，很难提供规范化的物流服务。随着 社会的发展进步，对物质的需求量大大增加，必然增加客户的数量，从而给物流 运输造成压力，对车辆调度进行合理的管理，以尽可能地节约成本，成为了现代 物流类企业的当务之急，本文针对这一难题，提出一种可行的改进的遗传算法在 车辆调度问题的应用解决方案；另一方面，原有的物流车辆调度系统都是基于理 想模型的基础之上的，即假设客户的需求和要求送达的时间都是已知的，但是在 这瞬息万变的时代，客户的需求可能不会是预知的，临时会有增减，这就要求物 流系统及时对客户的要求作出响应，即实时动态变化，本文针对这一问题，也提 出了一种在线的遗传算法实时处理带时间窗的车辆调度问题。 2 3 遗传算法 现在科学技术的发展正进入多学科互相交叉影响的时代，生命科学与工程科 9 学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个 显著特点。遗传算法的蓬勃发展体现出了科学发展的这一特点。制造智能的机器 一直是人类的梦想，人们为此付出了巨大努力。但是，近年来随着人工智能应用 领域的不断拓展，传统的人工智能方法在处理模式信息、知识表示、解决组合爆 炸等方面所碰到的问题已经变得越来越突出，这些困难甚至使某些学者对强人工 智能提出了强烈批判，对人工智能的可行性提出了质疑。众所周知，在人工智能 领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货 朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不 能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能 在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过 程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。遗传算法 就是在这种背景下产生并经实践证明特别有效的算法。遗传算法由密歇根大学的 约翰霍兰德和他的同事于二十世纪六十年代在对细胞自动机进行研究时率先提 出。在二十世纪八十年代中期之前，对于遗传算法的研究还仅仅限于理论方面， 直到在匹兹堡召开了第一届世界遗传算法大会。随着计算机计算能力的发展和实 际应用需求的增多，遗传算法逐渐进入实际应用阶段。19 8 9 年，纽约时报作者 约翰马科夫写了一篇文章描述第一个商业用途的遗传算法一进化者。之后，越 来越多种类的遗传算法出现并被用于许多领域中，财富杂志5 0 0 强企业中大多数 都用它进行时间表安排、数据分析、未来趋势预测、预算、以及解决很多其他组 合优化问题。 在遗传算法里，优化问题的解被称为个体，它表示为一个参数列表，叫做染 色体或者基因串。染色体一般被表达为简单的字符串或数字串，不过也有其他的 表示方法适用，这一过程称为编码。一开始，算法随机生成一定数量的个体，有 时候操作者也可以对这个随机产生过程进行干预，播下已经部分优化的种子。在 每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。 种群中的个体被按照适应度排序，适应度高的在前面。这里的“高 是相对于初 始的种群的低适应度来说的。 下一步是产生下一代个体并组成种群。这个过程是通过选择和繁殖完成的， 其中繁殖包括交配( c r o s s o v e r ) 和突变( m u t a t i o n ) 。选择则是根据新个体的适应度 进行的，适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。 初始的数据可以通过这样的选择过程组成个相对优化的群体。之后，被选择的 个体进入交配过程。一般的遗传算法都有一个交配概率，范围一般是0 6 - 1 ，这 个交配概率反映两个被选中的个体进行交配的概率。例如，交配概率为0 8 ，则 8 0 的“夫妻”会生育后代。每两个个体通过交配产生两个新个体，代替原来的 “老”个体，而不交配的个体则保持不变。交配父母的染色体相互交换，从而产 1 0 生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二 个个体则正好相反。不过这里的半段并不是真正的一半，这个位置叫做交配点， 也是随机产生的，可以是染色体的任意位置。再下一步是突变，通过突变产生新 的“子”个体。一般遗传算法都有一个固定的突变常数，通常是0 1 或者更小， 这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是 改变染色体的一个字节( o 变到1 ，或者1 变到0 ) 。 经过这一系列的过程( 选择、交配和突变) ，产生的新一代个体不同于初始的 一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被 选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复： 每个个体被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而 复始，直到终止条件满足为止。一般终止条件有这几种。 ( 1 ) 进化次数限制； ( 2 ) 计算耗费的资源限制( 例如计算时间、计算占用的内存等) ； ( 3 ) 一个个体已经满足最优值的条件，即最优值已经找到； ( 4 ) 适应度已经达到饱和，继续进化不会产生适应度更好的个体； ( 5 ) 人为干预； ( 6 ) 以及以上两种或更多种的组合。 随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是 基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间 的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新 的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希 望。二是遗传算法正同益和神经网络、模糊推理以及混沌理论等其它智能计算方 法相互渗透和结合，这对开拓2 l 世纪中新的智能计算技术将具有重要的意义。 三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发 展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法 和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机 模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工 生命的重要研究对象，而遗传算法在这方面将会发挥出一定的作用。五是遗传算 法和进化规划( e v o l u t i o np r o g r a m m i n g ，e p ) 以及进化策略( e v o l u t i o ns t r a t e g y ，e s ) 等 进化计算理论日益结合。e p 和e s 几乎是和遗传算法同时独立发展起来的，同 遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算 法具有相同之处，也有各自的特点。 目前，这三者之间的比较研究和彼此结合的探讨正形成热点。l9 9 1 年d w h i t e y 在他的论文中提出了基于领域交叉的交叉算子( a d j a c e n c yb a s e dc r o s s o v e r ) ， 这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了旅行商问题 ( t r a v