（系统工程专业论文）车队动态调度优化模型与算法研究.pdf

山东大学硕士学位论文 摘要 目前我国道路运输企业普遍面临着货源不足、车辆闲置率和空载率较大等 问题，如何提高自身的管理水平和运输组织的科学性、有效地调配车辆、降低 企业的物流成本、增加核心竞争力已成为道路运输企业急需解决的问题。其中 车队调度是影响道路运输企业运营质量的重要因素之一，也是本文的研究重点。 首先，本文在分析总结目前国内外车队动态调度研究成果的基础上，采用 多阶段决策的思想和动态规划方法对车辆调配形式、影响调度的因素以及调度 流程进行了系统分析，并将整个服务周期划分为若干个任务时段，从优化任务 发运计划的角度入手，对单个任务时段，分别建立了单车型、多车型车队动态 调度模型。 其次，利用遗传算法分别对单车型、多车型车队动态调度模型进行求解。 同时，为提高算法解的质量和计算速度，利用多线程技术设计了模拟分布式遗 传算法，并探讨了相应的子群体划分策略、信息交换模型和信息交换频率。仿 真实验结果表明，在计算时间方面，模拟分布式遗传算法的计算时间比标准算 法提高了1 倍，解的质量也优于标准遗传算法，并在处理较大规模数据时具有 明显优势。 然后，在单时段车队调度的基础上，本文进一步提出了综合滚动调度算法， 分析了影响滚动调度的主要因素，设计了相应的滚动时域窗口和调整策略。 最后，利用v b 和c + + 语言联合开发了车队动态调度优化仿真平台，并以 山东某快运企业真实数据为测试数据，分别测试了标准遗传算法与模拟分布式 遗传算法的性能、不同计划长度对调度结果的影响以及综合滚动调度算法得到 的整个服务周期的车辆平均空载率。仿真结果中，本文所设计的综合滚动调度 方法在控制车辆平均空载率上优于社会货运平均空载率5 2 6 。由此也表明了 此方法高效、实用，具有重要的实际应用价值。 关键词：多阶段决策；动态调度；遗传算法：滚动调度；空载率 山东大学硕士学位论文 a b s t r a c t t h e a d 蹦g h t 既【t 芒叩r i s 馏f a c e1 1 1 es 吖e 陀q u e s t i o i l so fd e 丘c i e n t 僦g h ts o u r c 髂， m el l i g h c r 锄1 p t y - l o a d i l l gr a t i oo f v l i c l e s h o wt o 呻r o v et h e i rm 勰a g i n gl e v e l ，t o o r g a n i z ea n ds c h e d u l ev e h i c l ee 丘b c 6 v e l y t o1 0 wt h er u 越i l l gc o s to ft l l e 豇i 姗p r i s e s 锄ds 胁g t l l e i lc o 陀a d v a m a g e sh 嬲b e 撇u r g ep r o b l 锄t og o 咖o r so fr o a d 仃a n s p o r t a n d1 h en e e ts c h 甜u l i i 培m a n a g e 玎掀l ti sav e r yi m p o r 嘶tf h c t o rw ! h i c hc a n i l i l p a c tt h eq u a l 埘o f o p e 僦n gm 锄g 锄饥to f r o a d 舶i g h te m e r p r i s e s ，w h i c ha l s oi s t l l es t i l d 蛐唱锄l p h a s i so f t l l ep a p f i 璐t l 弘t 1 p 印e rm a l 【e s 啦eo f m u l t i p h 船e dd e c i s i a n dd y n a i i l i cp r o f 锄瑚缸g t l l c o r ys y s t 锄i c a l l y 觚a l y z 嚣t l l es c h e d u l i n gf o 咖so fn e e ta n dn 地f h c t o 墙删c h a 位娥t l l es c l 潮u h n 吕锄da l s o 如l a i y z 留t l l ew h o l es c h e d u l i n gp r o c e s sa t 也e b 嬲锄e mo fa tt h eb 勰c m e n to f 锄m y z i l 培t l l es t i l d ) 袖gp r o d u c t i o f 也ed y l l a m i c n e e ts c h c d l l l i l 唱b o t hh e 聆孤da ：b r o a d a n e rt h e s ew o r i 【sd o n e ，t h ew h o l es e i n g c y c l ei sd i 、，i d e dt om a n yp e d o d s ，锄dt h ep a p 盯d e s i g 璐托l e r a md 耵l a i n i cs c h c d u l i n g i n o d e l sa i l nt ot h ef l e e t sw h i c ho w ns i n 酉ev e 嫩c l c - t y p eo rm u l 印l et y p 瞄i nt h es e n s e o f m a l ( i n go p t i m i z et l l en l i s s i o np l a n 船ab r e a l 【t l l r o u g k s e c o n d l y ，也ep a p c r “s od e s i 孕塔c o 玎e s p o n d i n gg e n e d ca 1 9 0 r i 也mt og e t 也er e s u l t s a tt l 摇s a m e 缅e ，吐圮p 印盱u t i l i z e st h em o c kd i s 协u t e d - g e n e t i c 舢g o r i t h l mw h i c h d e s i g nr c l e 啪td i v i d i l l g - s 仃a 肥g yo ft h e 跚b c o i o n 弘t l l e m m u t a t i v ei l l f b r m a d o n m o d e la n dt h ec o m m u t a t i v ei n f o m l a t i o n 丘e q u e n c yi no r d c rt oi m p r o v et h ee 伍c i e n c y a n d “o m n gq u a l i t yo fm ea l g o r i n m 1 ks i n l u la _ 同e ) ( p c r i m e n ti l l d i c a t c st h a tt h e c a l c u l a t i v es p e e do fn 峙m o c kd i s 雠b u t 。d - g e i l e t i ca 1 9 0 r i m mi sa ，o n eh a i fo ft h e s 切n d a r dg e r l e t i c 舢g 耐t h i n a n dt h eq u a l i t yo f r e 叭l 拓a 1 i ss u p c r i o rt o 也es t 锄d a r d 0 n c 7 s u c c e s s i v e l y 址i ep a p c r 细恤c r 硪n g sf o r w a r dl l l er o l l i n gh o r i z o ns c h e d u l i n g a 1 9 0 m h mf o rt l l ed y l l a m i cn e e ts c h e d i t l i n gm a i l a g e m e n t ，锄da n a l y z e st l l e m a i n f 犯t o 塔w h i c h 胡k tt h er o l l i n gh o r i z o ns c h c 血l i n ga n dd e s i g 船t h er c l e 、，a mt l l e 山东大学硕士学位论文 咒1 e v a mr o l l i n gh o r i z o np r o c e d u r e 锄dm ea 由u s t i v es 删e g ya f t 盯d e a l i n gw i t l lt 1 1 e n e e ts c h e d u l i n gm a l l a g 翻n e n ta tt l l es i i i 画e l p 耐o d ，f b rd e a l i n gw i t l l ( h em i s s i o 璐w h i c h a p p e a ri nt h ew h o l ep e r i o d sa t 瑚d 咖 a tl 勰t ，t i l ep a p e rd e v e l o p sas i l n u l a t e dp l a t f o n nf o rt h er o l l i n gh o r i z o ns c h e d u l i n g o ft l l ed y l l 锄i cn e e tm a l l a g 锄e n t1 i t l lt l l ec o m p u t e rt e c h l l o l o 百鹤o f a n dc + + i a q g l l a g a i l dm ep 印e ra l s od o 胬t l l e 既p e r i m e mo ft 髂t i n gt l l ep e r f o r m a n c e sb o t l l m es t a i l d a r dg 胁e t i ca l g 耐l h ma n dl h em o c k - d i s 仃i b u l e dg c t i ca l g o d t h l l l 锄dm e 哪舐m e n to ft 鄂t i n g 地砌u c eo fn ”s c h c d u l i n ga tn l ec o n d i t i o mo fd i 疏删 l e n g t h so f t l l em i s s i o np 1 觚a n dt h ee x p e r i i n e mo ft 铝t i n gt h e 锄p 铲l o a d 瑚时oo ft h e n e e ta tm ew h o kp e i i o d sw i 也l l s i n gt h er o l l i n gh o r i z o n8 c h e d u l i n g 1 1 l cm s u l t so f 麟p e 血1 e 吣p r o v et h a tn l cr o l l i n gh o r i z o n 鲥俄i u l i n ga l g o r i m mi i lt 1 1 i sp a p e rm d u c e i n o r e5 2 6 a tt l l e 锄p 妒l o a d i n gm t i oo fv e h i c l et l l 锄t l l es o c i a l a v e n g e l p t y - 1 0 a d i n g 洲o s ot h er e s u l t sc a np r o v em a tt h ea l g o r i t h mi nm ep a p e ri s e 饪v e 锄dp r a c t i c d b l e ，o w l l i n gt 1 1 ei m p o r t a n tv a l u e 白r t t l a la p p l i c a t i o n s k e y w o r d s ：m u l t i p h a s e dd e c i s i o n ；d y n a m i cs c h e d u l i n gm a n a g e m e n t ；g e n e t i c a l g o r i t l l m ；r o l l i n gh o r i z o ns c h e d u i i n 吕唧妒1 0 a d i n g r a t i o 山东大学硕士学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 * ? 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：毯拉日期：2 衄，氅孓 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丞塞迤导师签名：期：型田：垒筮 山东大学硕士学位论文 1 1 课题来源和意义 第1 章绪论 随着市场经济的飞速发展，我国公路运输业展现出蓬勃生机，已成为中、 长途运输的主力。但在我国公路运输业繁荣景象的背后，也存在着制约其健 康发展的隐患。据统计，我国货运车辆的平均实载率为6 0 3 7 5 ，而载重利用 率是1 1 0 2 5 ，里程利用率为5 4 7 6 ，全国载货车辆空载率高达4 7 9 “1 ， 即有近一半的行程相当于空车运行。每年我国空载车辆造成的燃油、车辆和 道路损耗以及劳动力浪费大约达3 0 0 0 亿元但1 。随着我国物流市场的全面开放， 国外运输企业的大举进入，在激烈的市场竞争中我国公路运输企业将处于不 利地位。 干线运输是公路运输中的一支生力军，其货运量占公路货运量的半数以 上，而收入却只占公路货运总收入的3 7 咖。现在干线货运企业普遍面临着货 源不足、车辆闲置率高、企业微利或亏损等问题，特别是车辆空载率居高不 下带来的一系列问题，不但创造不了社会价值，而且还消耗能源，污染环境。 造成空载的主要原因除了经济发展不均衡、运输市场发展不规范等因素以外， 还有： ( 1 ) 货物运输方式滞后 多数公路运输企业小规模、分散化的经营方式，造成货物运输方式严重 滞后。由于现今运输市场入行门槛低，存在着大量个体及私营运输业者，车 辆自有，自我服务，不能形成规模，且货源有限，因而经常出现空载等浪费 现象。 ( 2 ) 运输组织不科学，运输任务缺乏衔接 目前大多数运输企业的各个分部之间缺乏信息沟通，对运输工作无法进 行整体上的组织管理，也很难实现整个运输网络中车辆的统筹调度。据文献 4 分析，造成车辆空载率过高的原因之一就是运输任务之间缺乏有效衔接。 因调运不当，货源计划不周，不采用运输社会化而形成的空载现象和运输组 织者工作失误或计划不周，造成货源不实，车辆空去空回，形成双程空载的 山东大学硕士学位论文 现象，使得运输企业的运营成本居高不下，公司利润空间进一步受到挤压， 使其经营更为困难。 因此，在我国运输市场管理机制不规范、竞争压力较大的情况下，如何 提高运输企业自身的管理水平，开展有效的运输组织，科学地进行调度工作 就成为压缩物流成本、提高物流服务水平的有效措施和关键所在。本文所研 究的车队动态调度优化问题就是在这种背景下提出的。 在实际的运输中，一般都将服务周期划分为若干个时段，在每个时段内 运输网络的各节点处都可能产生运输任务0 1 。任务一旦出现，就需要已经分配 到任务所在地的车辆来完成该任务，即进行车队调度。所以车队调度要完成 两方面的工作，时间上的和空间上的旧。首先要制定出时间上的任务发运计划， 即为各项运输任务指定发运时间，其次又要完成空间上的车辆分配，即为各 项任务指定运输车辆。从而车队动态调度优化就是指在服务周期内，通过制 定和优化任务发运计划，并按照一定原则科学地调度车辆，在所有任务均能 得到及时服务的前提下，以最小的运输成本获得最大收益。 要达到对车辆的统筹调度，就要求在进行某时段的车辆调度工作时不仅 要考虑本时段的运输成本，还要考虑对未来各时段的车辆调度工作的影响， 并且未来各时段的任务需求是不可预知的，因此问题的研究是动态的【钉。同时 为了提高对客户的服务水平，每个任务都要求在其规定的时间窗内完成，所 以本文主要研究带时间窗的车队动态调度优化问题( d y n a m i cf l e e t o p t i m i z e ds c h e d u l i n gp r o b l e mw i t ht i m ew i n d o w ) 。 1 2 车队调度问题研究现状 车队调度问题是指在一个运输网络中，存在着若干个任务点。每个任务 点既能向其它任务点发运货物，也能从其它任务点接收货物，且每个任务点 都拥有一定数量的车辆资源。调度的目的是给出车辆行车路线( v e h i c l e r 0 u t i n gp r o b l e m s ，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 s ，v s p ) ， 使总运输代价最小、总运输里程或时间最短。同时要满足一定的约束条件， 如任务时间窗、车辆能力、车辆最大行程等要求因此车队调度问题是一个 v r p 和v s p 相结合的v r s p 问题。 2 山东大学硕士学位论文 目前国内对于v r p 的研究较多，而对于v r s p 问题研究还不够深入。 1 2 1 国外研究现状 国外对动态问题的研究开始于1 9 5 4 年，文献 6 研究了利用动态网络来解 决如何安排油轮的调配才能使得所使用的油轮数最少的问题。文献 7 9 主要 对确定性的车队动态调度问题进行了研究。文献 7 研究确定性的有时间窗限 制的多车型车辆动态调度闯题，并利用一系列线性规划模型对原有的动态网 络模型进行改进从而能够用于处理多车型和有时间窗的车队管理问题。文献 8 9 都是利用物流排队网络解决确定性的车队动态管理问题，从控制参数 的角度把动态调度闯题分解成很多子问题，用多调整策略调整控制参数，逐 步推进解决问题。但是这种新方法运算速度有时较慢而且难以实现。 文献 1 0 一1 2 建立一个基于动态网络的空车调配的优化模型。文献 1 0 研 究了铁路运输中空车调配问题，用一种时空图表来表示车辆实际运动过程， 并设计了相应的网络流算法在时空图表上求解了空车分配方案。但是由于本 质还是图表作业，很难适用一定规模的车队，有一定的局限性。文献 1 1 针 对在运输网络中的空车规模和分配问题设计了一个优化模型，同时优化车队 的大小和车辆分配，利用一种网络近似计算的方法来解模型，并证明算法收 敛。但是在这个模型中，忽略了载货车辆的重要性。其中文献 1 2 主要通过 假设未来的任务需求和空车分布情况已知去制定调度计划，但在研究中只考 虑了对空车的调配问题，而忽略了载货车辆。并且没有对模型本身进行深入 的分析。文献 1 3 提出用一个连续概率分布来估计未发生需求量的解决办法， 虽然考虑了载货车辆的因素，但为了分析问题的难度提出了一个不符合实际 的假设，那就是载货车辆一旦到达目的地并卸载任务后就不能再被使用。文 献 1 4 不仅认识到了空车调配的重要性，把载货车辆和空车都作为决策变量 引入到所建立的数学模型中进行处理，大大增加了问题的合理性。并且对随 机问题的内在联系进行了研究，设计了一个连续线性逼近函数来逼近需求期 望函数，使问题从时空上分解为一个个单时段单节点问题进行解决。文献 1 5 研究了在不确定性需求的环境下随机性的车辆分配问题，设计了一个新的启 发式方法将未来各时段未知需求转化为确定性的概率分布，特别的是，在文 山东大学硕士学位论文 献中也设计了相应的滚动调度去模拟一段时间的调度情况，最后用大量算例 证明了这种算法的优越性，但是总体思路仍然是将未知需求转化为确定概率 分布。 文献 1 6 则同时考虑了装货集装箱和空集装箱的管理问题并引入了模拟 技术来解决随机性的调度问题，并使用启发式搜索技术来改进集装箱分配策 略。尽管针对该类问题的研究工作在不断开展，但问题的大规模特性和随机 特性致使有效求解算法的设计一直得不到很好地解决。文献 1 7 研究了一种 随机的动态资源分配问题。在此文献里，资源是可重用的，去完成随时产生 的任务。用了一种自适应的通过用非线性逼近函数未来的任务情况的动态规 划方法。这种函数逼近方法是分段线性的并且可以提供整数解。但是在这篇 论文里，它将随机需求最大程度地转化成确定性问题去解决，解的精确性较 差。文献 1 8 研究了一种铁路调度系统中的空车调配问题，计算空车调配的 费用，并且证明这种费用体现了规模效益。这篇论文的目标是去建立一个考 虑规模效益的优化模型。用一种依赖于时间的动态网络去体现出未来可能的 车辆运动过程，并在此基础上设计出了专门的禁忌算法。但侧重于规模效益 的研究，只是分析了调度环境的动态变化对整体的影响，并未制定相应的调 度策略。 1 2 2 国内研究现状 在静态v r p 问题上，文献 1 9 2 4 针对静态v r p 作了广泛而深入的研究，主 要是在满载与非满载、带有时间窗限制、是否带有回程取货等方面作了研究， 特别是文献 2 3 对于各类静态v r p 从问题建模到应用算法作了深入分析和总 结。在动态v r p 问题上，文献 2 5 主要研究了不确定信息造成的随机性事件的 解决策略，并给出了单车场、单车型闭合环境动态车辆调度的数学模型和算 法。文献 2 6 将时变复杂交通网络下的车辆路径问题分为确定需求和动态需 求两部分。并分别建立了不同需求下的调度模型和动态调整策略。 国内研究v r s p 较少。其中文献 2 7 针对复杂动态资源管理问题提供了一 种灵活的模型描述方法和优化思路，重点讨论了动态调度中不同参数对于问 题的影响，如资源分类，过程、控制等因素，研究带有普遍性但分析不够全 4 山东大学硕士学位论文 面。这是国内较早的关于动态资源分配方面的研究。 文献 2 8 基于智能决策支持系统的理论和方法，结合我国铁路空车调整 的实际，对建立和开发空车调整智能决策支持系统( e c d i d s s ) 的总体设计，以 及模型库子系统、知识库子系统、数据库子系统、人机交互子系统的设计与 实现方法进行了深入探讨。但是作了一定程度的简化，降低了模型精度，另 外调度决策支持不完善。文献 2 9 系统地介绍了铁路空车调配模型，并以朝 鲜铁路网络为背景，选取3 8 个大车站构成网络的节点；归类货车为5 大类，建 立相应的空车调配模型。实验表明能减少空车的行走距离，使货车更为有效 的运行。但是这种模型只适用于解决最简单的情况，并且没有考虑到与重车 的协调调度以及相应的滚动调度。文献 3 0 对铁路节点间空车调配优化问题 进行深入的研究与分析。采用采用系统科学的观点和方法、类比法及数理模 型的研究方法，同时结合离散数学、最优化理论、计算机数学等相关学科的 理论知识，以提供一种新的建模思路和求解算法为目的。但是并没有考虑到 对空车进行动态调整，以及与重车流的协调优化，欠缺一定的系统性。 文献 3 1 分析了航班调度信息管理系统的功能需求，比较了几种可行的 实现方案，提出了以a s 4 0 0 为服务器的系统总体开发方案，论述了硬件设计 选择和软件总体设计以及模块划分，开发了相应的软件平台，但侧重于调度 信息管理，只能对调度工作起到辅助作用。文献 3 2 以航班进离港过程为研 究对象，对机场进离港过程进行简单建模，运用排队论的方法对该模型进行 仿真，使用g p s s 软件研究模型中不同的输入对各服务阶段运行参数的影响， 运用摄动分析方法分析，得出合适输入分布；然后运用极大代数的闭环串行 生产线模型来研究不同的机型顺序进入模型对系统周期稳态运行的影响，得 到最优的机型排列；此文献运用离散事件动态系统理论和计算机仿真技术深 入地研究了系统的动态性，但是仍没有从全局角度考虑调度问题。文献 3 3 对机场和终端区的航班调度问题进行研究，建立了航班调度模型，并对终端 区飞机进场着陆问题进行详细分析研究，利用模糊理论设计算法在航班调度 模型的理论基础上，重点研究了模糊控制理论在进场飞机排序的应用及其实 现问题。采用标准起落航线，将进近过程分为若干飞行段，从而把全局排序 问题划分到各个飞行段上。利用m a t l a b 模糊工具箱建立模糊推理判据模型， 山东大学硕士学位论文 编写排序系统程序，并进行了仿真计算，得到了合理可行的排序结果，明显 减少航班队列的延误。但只是在考虑单跑道情况下，而且并未考虑同时存在 飞机进场和离场情况下的综合调度。也没有考虑随机情况的出现以及相关调 度方法。 在公路运输方面，文献 5 深入剖析了存在于已有研究工作中的不足，并 从车辆调配影响因素、车辆调配形式、车辆调配方案制定和问题的动态特性 四个方面对车队动态管理问题的基本情况进行详细论述。在上述工作的基础 上，将车队动态管理问题分为单车型确定性问题、多车型确定性问题和随机 问题三大类，并从其模型建立与算法构造的角度出发开展了系统化的研究工 作对于单车型确定性车队动态管理问题，利用函数逼近技术构造一个特殊 的线性函数来近似目标函数中的未来时段部分，从而建立问题的时空分解模 型，把问题从时间和空间上分解为多个单时段单节点的车辆调配问题。并根 据单时段单节点车辆调配问题的特点设计简单的排序求解方法。对于多车型 确定性车队动态管理问题，分析了车型和任务的匹配问题，并在单车型问题 模型的基础上对其进行改进，使其能够处理多车型问题。同时也设计了专门 的方法解决多车型的单时段单节点车辆调配。对于随机车队动态管理问题， 分析了问题的随机特性，并根据未来需求的概率分布函数，设计期望车辆数 的估计方法、车辆选择概率的确定方法和车辆期望收益值的确定方法，从而 确定线性替代函数斜率。构造线性替代函数来逼近目标函数中的期望函数部 分，使问题分解为多个单时段单节点问题。 但此文献为了降低分析问题的复杂度，对实际的情况进行了很多简化。 在处理确定性车队问题时简化两点之间的距离均为1 个单位时段，且车速相 同。而且在处理随机性车队管理问题时，只考虑单车型并且任务时间窗为o ， 一旦在本时段未完成，则认为该任务消失。由于在随机调度部分，未来各时 段的任务需求按已知的概率分布处理，也就意味着货源信息不确定，降低了 在实际中进行应用的可行性。 根据以上文献综述分析，国内外学者大多利用函数逼近技术从时间上和 空间上把问题分解为多个单时段单节点的车辆调度问题进行求解，或者利用 仿真技术来模拟调度情况，从而获得可行的调度方案。但是均对实际问题进 6 山东大学硕士学位论文 行了较大程度的简化，也没有实现整个运输网络所有车辆的统筹调度，并且 主要思路是将未知需求转化为确定概率分布，因此所做出的调度方案无法保 证存在确定的货源，在实际应用中具有一定的限制性。 1 3 论文主要工作和章节安排 针对以往研究中存在的不足，本文主要做了以下工作：首先详细分析干 线运输的实际流程和特点，将多阶段决策思想用于车队调度；然后分别建立 单时段下单车型、多车型车队动态调度数学模型，设计了相应的遗传算法求 解，并对算法作了一定程度的改进；最后进一步提出滚动调度算法，并根据 问题需要设计仿真平台，进行实际数据测试，检验本文所设计的模型和算法。 本文的章节安排如下： 第一章绪论；主要包括课题来源与意义、国内外研究现状( 国外研究现 状、国内研究现状) 、论文主要工作及章节安排。 第二章干线运输及车队调度分析：主要包括干线运输及相关理论( 整车 运输基本概念、遗传算法) 、车队动态调度的多阶段决策与动态规划( 多阶段 决策与动态规划、车队动态调度优化分析) 。 第三章车队动态调度优化问题数学模型：对动态调度的性质进行了分析， 针对单车型和多车型情况分别做了约定，进行了变量说明，建立了相关的模 型。 第四章车队动态调度优化问题的g a 设计：对单车型和多车型车队动态调 度问题分别进行了遗传算法设计。在最后一部分，为了改善遗传算法解的质 量和求解速度，对遗传算法进行了改进，设计了模拟并行式遗传算法。 第五章车队动态综合滚动调度及仿真实验：主要包括综合滚动调度设计， 仿真平台介绍( 功能、程序流程、模块结构) ，最后是仿真实验与结果分析。 第六章结论与展望：主要包括研究特色和创新点、需要改进和进一步研 究的内容。 7 山东大学硕士学位论文 第2 章干线运输及车队调度分析 由于本文主要研究的是干线运输领域的车队动态调度问题，采用的主要思 想是多阶段决策，因此在本章重点介绍一下干线运输的基本知识与相关理论、 多阶段决策与动态规划，最后要对本文所研究的车队动态调度阿题进行分析。 2 1 干线运输及相关理论 由于干线运输中主要业务为整车运输，不失一般性，本文仅研究干线运输 中的整车运输情况。 2 1 1 整车运输基本概念 一、整车运输定义 凡一次托运批量货物的质量在3 吨( 含3 吨) 以上或虽不足3 吨，但其性 质、体积、形状需要一辆3 吨位以上的汽车运输均属于整车运输范畴1 。 从货物的物理属性构成上看，整车货物多为固体货物，而其中又以块状货 物，如煤炭、矿石等和粉末状货物，如水泥、化肥居多。集装单元可以视作整 车货物的一种特殊形式，包括托盘、集装笼以及用特殊包装物固定在普通货板 上的货物等。从货物的运输条件上，一些特种货物包括危险货物、大件( 长大 笨重) 货物、鲜活货物和贵重货物一般也都作为整车货物嘲。 整车运输一般不需要中间环节或中间环节很少，即直达运输模式，送达时 间短、相应的货运集散成本较低。涉及城市间或过境贸易的长途运输与集散， 如国际贸易中的进出口商多数采用为基本单位签订贸易合同，以便充分利用整 车货物运输的快速、方便、经济、可靠等特点m 矧。 二、直达运输模式 ( 1 ) 直达运输定义：直达运输是指越过商业仓库环节或铁路交通中转环 节，把货物从产地或起运地直接运到销地或客户，减少中间环节的一种运输方 式m 1 。如图2 1 所示： 山东大学硕士学位论文 图2 一l 直达式运输 ( 2 ) 直达运输的优缺点和适用范围 直达运输是追求运输合理化的重要形式，要点是通过减少中转过载换载， 从而提高运输速度，省却装卸费用，降低中转货损脚删，节省了运输时间与费 用，灵活度较大。但相对而言对企业各部门分工协作程度的要求较高，企业内 部计划、财会、业务、仓库等各个机构应加强联系，建立相应的联系制度来满 足其需求。 三、业务运作流程 整车运输采取的是直达模式，主要的业务流程如图2 2 所示： 1 0 图2 - 2 业务运作流程 山东大学硕士学位论文 整车货物运输过程是一个多环节、多工种的联合作业系统，是社会物流必 不可缺少的、重要的服务过程。从总体上讲，这个过程由四部分组成，包括运 输准备过程、基本运输过程、辅助运输过程和运输服务过程嘲。 ( 1 ) 运输准备过程 运输准备过程是在运输之前所做的各项技术性准备工作。包括：车型选择、 线路选择、装卸设备配置、运输过程的装卸工艺设计等作业过程。 ( 2 ) 基本运输过程 基本运输过程是指直接组织货物，从起运地到达目的地完成其空间位移的 生产活动。包括起运站装货、车辆运行、终点站卸货等作业过程。 ( 3 ) 辅助运输过程 辅助运输过程是指为保证基本运输过程正常进行，所必需的各种辅助性活 动，它主要包括车辆、装卸设备、承载器具、专用设施的维护与修理作业，以 及各种商务事故、行车事故的预防与处理工作、营业收入结算工作等。 ( 4 ) 运输服务过程 运输服务过程是指服务于基本运输过程和辅助运输过程中的各种服务活 动。例如，各种行车材料，配件的供应，代办货物储存、包装，保险业务，均 属于运输服务过程。 四、运输成本构成 运输成本通常可以根据成本的特性划分为变动成本、固定成本、联合成本、 公共成本四个部分伽： ( 1 ) 变动成本：变动成本是指与每一次运输配送直接相关的费用，包括 与承运人运输每一票货物有关的直接费用，如人力成本、燃料费和维修保养费 用等。开动运输工具要花费劳动、燃料、维修保管费等；运输数量越多，运输 路程越长，费用就越高。这些随运输数量、里程而变动的费用，就是变动成本。 ( 2 ) 固定成本是指在短期内不随运输水平的变化而变化的成本。它主要 包括运输基础设施洲如站台，通道、机器设备等的建造设立成本以及管理系 统费用。这些成本的大小不受营运量大小的直接影响，因此称为固定费用。 ( 3 ) 联合成本：是指决定提供某种特定的运输服务所发生的费用。例如， 为承运人决定装载一卡车货物从a 地运往b 地时，卡车从b 地返回a 地的费用 山东大学硕士学位论文 是不可避免的，这部分费用就称为“联合成本”。 ( 4 ) 公共成本 公共成本是指承运人代表所有的托运人或某个分市场的托运人支付的费 用，包括诸如端点站或管理部门之类的费用。 整车承运人的运营成本主要由人力费和燃油费组成，也包括一些车辆维护 和保险费用。在第三章的问题分析中，是以任务发运计划期间的总运输成本 最小为目标函数，目标函数中的成本组成部分只包括运输成本，也就是由车辆 载货移动、原地等待和空车移动的费用组成。 2 1 2 遗传算法 遗传算法( g e n e t i ca l g o r i th l l l ，简称g a ) 最早由美国的j h o l l a n d 予1 9 7 5 年 提出，是产生最早、影响最大、应用也比较广泛的一种进化算法。由于其简便、 高效和全局搜索性，g a 已被成功地应用于工业设计、经济管理、交通运输等不同 领域，解决了许多组合优化问题。例如，可靠性优化、流水车间调度、作业车间 调度、机器调度、设备布局设计、图像处理、最优控制，信号处理以及数据挖掘 等m 嘲。 一、标准遗传算法 算法流程的主要步骤描述如下d 力渊： ( 1 ) 随机产生一组符合问题可行解结构的染色体，并根据适应度函数，计 算每条染色体的适应度值。 ( 2 ) 根据规定的算法收敛规则判断是否可以输出结果，若满足则输出结果， 否则执行以下步骤。 ( 3 ) 根据每个染色体的适应度值，按照一定的规则对种群进行选择操作。 ( 4 ) 按选取的交叉率儿对种群执行交叉操作。 ( 5 ) 按选取的变异率p 。对种群执行变异操作。 ( 6 ) 返回到( 2 ) 。 标准遗传算法的主要优化流程如图2 3 所示： 1 2 山东大学硕士学位论文 图2 3 标准遗传算法的主要优化流程 二、并行遗传算法 虽然遗传算法无论是从直观上还是理论上都具备并行性，但在实际应用中， 通常会使得计算开销过大，造成寻优时间过长，难以满足具体需求。因此，很多 山东大学硕士学位论文 学者开始将研究的重点放在提高g a 的搜索速度方面，其中一个重要的研究方向就 是g a 的并行化执行，即并行g a ( p a r a l l e lg a ，p g a ) 溉“删。 并行算法的基本思想是将整个任务分解成若干子任务，并同时采用一组处理 器分别求解各个子任务。其中，从群体管理方式的不同，并行g a 可以分为全局 单群体主从式p g a ( 9 1 0 b a ls i n g l e p o p u l a t i o n 眦s t e r s l a v ep g a ，m s p g a ) ， 简称主从式p g a ；全局单群体细粒度p g a ( 9 1 0 b a ls i n g l e p o p u l a t i o n f i n e g r a i n e dp g a ，f g p g a ) ，简称细粒度p g a ；多群体租粒度p g a ( 眦1 t i p l e p o p u l a t i o n ，c o a r s e g r a i n e dg a ，c g - p g a ) ，简称为多群体p g a ，或分布式p g a ”。 “删。由于本文是利用多线程技术对最后一种p g a 进行了模拟，所以下面重点对 粗粒度p g a 进行相关介绍。 1 、粗粒度p g a 工作原理 粗粒度p g a 的结构设计比较复杂，在处理器个数较少的情况下，可以将群 体分为若干个子群体，每个子群体包含一些个体，每个子群体分配一个处理器， 让它们相互独立地并行执行进化。子群体进化过程中以某种方式交换个体，称 为个体迁移( i n d i v i d u a l sm i g r a t i o n ) ，并由一组参数控制。通常存在两种 迁移实现：岛屿模型、踏脚石模型帆“1 。岛屿模型允许从一个子种群迁移到任 意一个子种群，而踏脚石模型限定迁移操作只能在相邻的子种群间进行。若子 群体之间不存在个体迁移，在遗传学上称之为孤岛模型( i s l a n dm o d e l ) ，相应 的p g a 称为孤岛p g a “枷。粗粒度p g a 的应用通常要求结点计算量与通信计 算量的比值比较高，适用于内存分布式的m i m d 计算机，一般亦称为分布式 p g a 嘲【螗】 2 、粗粒度p g a 设计 ( 1 ) 基本情况 粗粒度p g a 是将整个群体划分成几个子群体，各个子群体分配在各自的处 理机或局域网工作站上独立地进行标准遗传算法的进化操作，在适当的时候各 个子群体之间相互交换一些信息，进行个体的迁移，即个体从一个子群体迁移 到另一个子群体。这种方法改变了标准遗传算法的基本特点，即各子群体独立 地进行进化，而不是全部群体采用同一机制进化，丰富各子群体的多样性，防 止早熟收敛的发生。这种遗传算法的基本框架如下嘲： 1 4 山东大学硕士学位论文 随机产生一个初始种群并将它分成多个子群体； 并发地对每个子种群肛( f = 1 ，2 ，) 执行和。 在所给定的进化代数内对艇执行遗传操作，包括选择、交叉、变异等。 当满足一定迁移条件时，按照某一种迁移模型进行个体迁移，执行新一 代子群体 若不满足结柬条件则转。 ( 2 ) 迁移模型蝴 粗粒度p g a 采用迁移操作进行各子种群问的信息交换。通常存在两种迁移 实现：岛屿模型、踏脚石模型。如果个体的迁移是完全随机的，即从子群体中 均匀随机地进行抽样，然后再随机地迁移到另一个群体中。在迁移的过程中， 认为这些子群体是完全独立的，个体的选择及迁移对这些子群体都是对等的， 即相当于将这些子群体看成是一些独立的岛屿，个体从一个岛屿到另外的岛屿 的机会是均等的刀，这种迁移方式称为岛屿模型( i s l a n dm o d e l ) ，如图2 4 所 示。但在自然界中，个体的聚居地或多或少地具有某种联系，个体的交换在相 邻的聚居地之间要频繁些。在进行并行实现时，子群体的互连方式既可以是总 线形的，也可以是环型的，或是二维阵列、超立方体形式帆“。我们可以根 据互联方式的区别来确定子群体问的相邻关系，从而使个体迁移到相邻子群体 具有较大的概率，这样进行迁移的方式称为踏脚石模型( s t e p p i n g s t o n e m o d e l ) ，如图2 5 所示。 一 一 表示子群体 表示子群体中的个体 图2 4 岛屿模型 山东大学硕士学位论文 表示子群体 表示子群体中的个体 图2 5 踏脚石模型 ( 3 ) 迁移策略 在分布式遗传算法中，有关多群体d g a 的迁移策略，一般需要考虑：子群 体通信的拓扑结构、迁移方式和数量、迁移率或进化代的间隔、接收地子群体 的替代方式d 刀。 本文所考虑的迁移策略涉及三个因素，迁移个体的选择方式、迁移率与接 收地子群体的替代方式。迁移个体的选择方式可以有两种方式，分别是选择最 佳个体进行迁移和随机选择个体进行迁移。接收地子群体的替代方式也有两种 方式，是替代最差个体的替换方式和随机替换方式，这样共有四种迁移策略1 ： 选择最佳个体进行迁移并在接收地替换最差个体 选择最佳个体进行迁移并在接收地采用随机替换方式； 随机选择个体进行迁移并在接收地替换最差个体； 随机选择个体进行迁移并在接收地采用随机替换方式。 借鉴文献 4 4 对以上四种迁移策略对于分布式遗传算法性能的分析，结果 表明采用迁出最佳个体并在接收地随机替换个体的迁移策略能使多群体并行遗 传算法的性能达到最佳。 综上所述，构造这种分布式遗传算法时，需要考虑下述几个主要问题1 ： 子群体划分方式 可将初始群体均匀划分为各个子群体，也可随机决定子群体所含个体的数 1 6 1 ，一 厂-、 山东大学硕士学位论文 量州1 。 信息交换方式口钉 在并行遗传算法的运行过程中，各处理机之问要相互交换一些信息。信息 交换方式包括参加信息交换的对象，指的是哪几个处理机之间可以相互交换信 息，也可以是全部处理机之间交换：其次包括交换信息的内容，指的是随机交 换，还是择优交换。可以是交换随机选定的几个个体，也可以是从较好的几个 个体中任选一个进行交换，还可以是交换子群体中最好的个体；还包括交换时 间或频率，指的是何时交换，可以是以同步或异步的方式在每一代进化过程中 都进行信息交换，也可以是以指定的时间间隔或进化代数间隔进行信息交换； 最后考虑的是交换信息量，指的是交换几个个体。可以只交换一个个体，也可 以交换多个个体。 2 2 车队动态调度问题的多阶段决策与动态规划 由于本文的思路是将整个服务周期划分为若干个时段，从而将整个服务周 期内的调度转化为一个个单时段内的工作。因此是一个多阶段决策问题，而动 态规划方法是解决多阶段决策问题的有效方法，所以下面就首先介绍多阶段决 策含义和动态规划思想。 2 2 1 多阶段决策与动态规划 一、多阶段决策 多阶段决策问题可以按时间顺序分解成若干相互联系的阶段，在每个阶段 都要做出决策，全部过程的决策组成一个决策序列。这种把一个问题看作一个 前后关联具有链状结构的多阶段过程的决策就称为多阶段决策过程，也称序贯 决策过程m 1 。使整个活动的总体效果达到最优的