《面向动态调度的智能物流运输模型研究.pdf》由会员分享，可在线阅读，更多相关《面向动态调度的智能物流运输模型研究.pdf（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、上海交通大学硕士学位论文面向动态调度的智能物流运输模型研究姓名：李斌申请学位级别：硕士专业：企业管理指导教师：徐丽群20060101面向动态调度的智能物流运输模型研究 1 面向动态调度的智能物流运输模型研究 摘 要 在传统的静态运输调度问题中，各种信息在运输调度前是已知的，这些信息不随时间的推移而变化，这并不符合现实中快递业务、电子商务等涉及到的物流运输活动现状。实际上，在运输调度前相关信息并不完全知道，而且随着时间的推移，信息也会发生变化，在这种情况下动态运输调度是必须的。近年来 IT、通讯技术的发展以及物流设备设施的改进使得解决动态运输调度问题有了可能。多智能体技术的发展和广泛应用为解决动
2、态运输调度问题提供了新的思路。本文在静态运输调度问题的基础上，研究探讨了动态运输调度问题，并引入多智能体系统技术，建立了解决此类问题的智能物流运输模型。本文在详细研究动态运输调度问题动态性和周期性指标的基础上，界定出一类适合于多智能体技术解决的动态运输调度问题扩展了的动态运输调度问题。接下来，针对扩展了的动态运输调度问题，引入多智能体系统技术，建立了智能物流运输模型，对模型的详细框架、思想和算法等进行了研究。最后的实例分析表明，面向动态调度的智能物流运输模型能较好地解决扩展了的动态运输调度问题，提高运输调度的效率。关键字 动态运输调度，多智能体，物流，apriori 方法 面向动态调度的智能物
3、流运输模型研究 2 THE RESEARCH ON INTELLIGENT LOGISTIC TRANSPORT MODEL FOR DYNAMIC VEHICLE SCHEDULING PROBLEM ABSTRACT Comparing on the Static Vehicle Scheduling Problem(SVSP),the research analyzed the Dynamic Vehicle Scheduling Problem(DVSP)and addressed the Intelligent Logistic Transport Model(ILTM)based
4、on multi-agent system.In SVSP,the all relative information should be identified and they should not change in the vehicle scheduling process.But it is not true in the express business,E-Commerce etc.There,not all relative information can be known and they will change in the vehicle scheduling proces
5、s.It is called DVSP.Now,the development of logistic equipment&facility and IT&communication technology has made DVSP-solution feasible.The multi-agent system is a new way to solve DVSP.So the research defined the special DVSP(Extensive DVSP)for multi-agent system,after analyzing the dynamic and cycl
6、e of DVSP.Next,the research established the ILTM for Extensive DVSP according to multi-agent system,and designed the framework,algorithms etc.At last,the example using ILTM showed that ILTM was able to solve DSVP well and could improve the efficiency of vehicle scheduling.KEY WORDS Dynamic Vehicle S
7、cheduling Problem,Multi-agent System,Logistics,a-apriori optimization 上海交通大学上海交通大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：李斌 日期：2006 年 1 月 12 日 上海交通大学上海交通大学 学位论文版权使用授权书学位论文版
8、权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密保密，在 年解密后适用本授权书。本学位论文属于 不保密 不保密 。（请在以上方框内打“”）学位论文作者签名：李斌 指导教师签名：徐丽群 日期：2006 年 1 月 12 日 日期：2006 年 1 月 12 日 面向动态调度的智能物流运输模型研究 1 1 绪论 1.1 研究背景 随着市场经济和物流业的发展，企业
9、中运输调度的地位逐步从流通中的一个环节、一个功能，演变成为必须直接面对市场需求，及时捕捉需求变化，实时做出相应运输计划调整的相对自主独立的系统。“按需物流”概念的引入，日杂百货行业 ECR 战略的盛行，快递业务、电子商务的迅猛发展，要求运输调度能更快的响应、更全面的决策、更灵活的动作，要求在调度前不完全知道相关信息，并且信息在调度过程中发生变化的情况下进行优化运输调度。1.1.1 按需物流【1】回顾一下物流发展的历史（表 1），表 1 物流发展的历程 不同时期的物流 物的流通 商务物流 价值链物流 对象 流通部门 全公司/企业间 价值链 目的 降低物流费用 通过提高总的质量增加顾客满意 不同企
10、业合作、社会系统的共生 范围 销售物流 产品物流、生产物流、供应物流 从原料供应业者到最终客户为止、从销售到售后服务循环再生为止 可以看出，物流的发展是随着经营环境的变化，在物资、空间、时间、价值链不断延伸扩展。在物资方面，从材料到零部件，再到产品，到服务；在空间上从国内到本地域再到全世界；在时间上从销售到售后服务，再到以回收为终点的产品生命周期的全部内容；在价值链上从企业内到企业间，再到价值链的全部。当前由于网络技术发展、经济全球化趋势加强，物流进入了供应链管理时代，要求供应链系统中的上、下游企业，以市场需求为导向、信息共享、协同运作，从而形成充分满足顾客需求的高效物流系统。“按需物流”就是
11、再上述背景下提出的，它指的是物流的按需化形态，是物流在现代商务环境下发展出来的最新形态。在“按需物流”形态中，实现了实时、可视化、协同化（信息共享）。首先是实时，以前的物流系统中的所谓实时，指的是实时掌握材料仓库、产品仓库、配送中心、物流中心等网点的状况和状态，是用“点”捕捉信息，而“按需物流”中所讲的实时不是用“点”，而是用“线”捕捉信息。其次是可视化，在“按需物流”中，不能仅仅停留在单纯地提供订货和接受订货、库存、入库和出库等物流数据上，而是以这些数据为基础，实现哪些是异常的哪些是适当的，哪些是应该指示的哪些是不应该指示的等信息的可视化。最后是协同化，是指与 E to E 有关的价值链上的
12、全部企业，能够协调运作。下图显示了一个“按需物流”的概念图（图 1）：面向动态调度的智能物流运输模型研究 2 图 1 “按需物流”概念图“按需物流”可在制造商、销售商、批发商、零售商的价值链运转中，实现信息的实时可视化，它与实际有几个仓库、本公司仓库和其他公司仓库的区别，以及与配送、运输的路途都没有关系，其链的全部信息建立在系统之上，作为“假想仓库”被管理着。进而，再以所有的信息为基础，进行需求管理、预测、计划、追踪、警告、指示及引导，实现全过程的最佳化。因此，在“按需物流”中，必须迅速拟定与市场同期的运输调度计划，将以前那种按周期进行生产的方式，转变为按收到的订单多少进行生产的方式。在动态情
13、况下处理运输调度问题成为“按需物流”的必然要求。1.1.2 ECR 战略【2】效率型消费者对应（Efficient Consumer Response,ECR）是日杂百货行业的供应链营销战略，由零售商、批发商与厂商等供应链节点组成各方相互协调和合作，更好、更快并以更低成本为顾客提供更多价值的一种供应链管理方法。由于降低分销成本的压力越来越大，ECR 对于日杂行业越来越重要。ECR 的实施包括有效的店内布局和有效的补货。有效的补货通常由下列要素构成（图 2）：面向动态调度的智能物流运输模型研究 3 图 2 ECR 战略的补货流程 在这个过程中，动态的配送系统主要处理：（1）由仓库发给店铺；（2）
14、由厂商发给仓库。首先动态的计算机辅助订货系统根据产品预测和补货前置时间计算出店铺存货的预计出货量，在将预计售出量和即将到货量进行比较，以确保在下次到货之前有足够的库存。在此过程中，店铺的需求都是动态的，不确定的，此过程的运输调度大多是动态的，动态运输调度问题的解决，将有效降低 ECR 战略的配送成本。1.1.3 快递业务 按照中国快递市场规模的增长与 GDP 增长的线性关系，中国的快递市场近几年的增长规模将达到 26以上【3】。快递市场的高速发展也推动了动态运输调度问题的研究。快递公司的经营模式一般是在一个地方收集邮件/包裹，并在某个时间限制内将货物安全地送到另一个地方，他们在将货物送到远方的
15、一个终端前需要在本地收集要送到外地的包裹并将他们合并起来。类似地，来自远方终端的货物需要在本地被配送。POS 机扫描 店铺商品预测 电子收货系统 价格和促销数据动态计算机辅助订货系统 集成的采购管理 厂商订单履行系统动态的配送系统 仓库电子收货 直接出货 自动化会计系统 议付 面向动态调度的智能物流运输模型研究 4 图 3 长途邮件快递业务 如图 3，整个业务大致分成邮件的收集和分送两大过程，在邮件分送过程基本上是一个静态问题，而虚线所示的的邮件收集过程则是一个动态运输调度问题，当邮件收集车辆或人员出发去收集邮件时，并不知道所有顾客信息，实际上很大一部分顾客都是动态顾客。1.1.4 电子商务
16、电子商务的出现，大大改变了原有的商业经营环境，对物流供应也提出了更高更新的要求。随着消费者不断要求更短的处理周期时间，安排管理、追踪和监测货运情况所需要的时间已经从几个星期缩短为几天甚至几个小时，运输调度也越来越呈现出明显的动态化。而在我国大规模的网上购物实现起来之所以非常困难，一些从事网上购物的网站经营之所以经营不佳，其中一个重要原因就是运输条件跟不上，对于动态运输调度问题根本无法处理，造成运输费用过高，配送不及时。尤其是零售型的网上交易，为每个客户实现送货上门是高成本的。传统的零售模式是消费者自己到零售商处直接购买。并自己将商品拿回，而网络购买时，卖方还负责将卖出的商品交到买方手里。虽然负
17、责转移商品的责任人变了，但转移商品的费用并没有变，它依然要加到交易成本中，最终由买方以商品价格方式支付，而顾客最关心的是商品的最终售价，因此，能否降低商品本身的售价是能否成交的关键，这里面运输费用是一个关键。在发达国家，成功的网上销售商背后都有一个成功的物流运营商为他完成所售商品的送货上门环节。而在我国，如何有效解决动态运输调度问题，经济合理地完成此类物流运输和配送，成为当前电子商务发展过程中的一项重大问题。1.2 研究意义 虽然动态运输调度问题的紧迫性已经从方方面面表现出来，但对它的研究还相当的薄弱，国内现有的研究大多集中在静态运输调度方面，对动态运输调度关注得比较少。因此，本文的研究一邮件
18、发送者 地区收集中心国家收集中心 机场 机场 国家分送中心 地区分送中心邮件接收者 面向动态调度的智能物流运输模型研究 5 方面是介绍国外关于动态运输调度的一些新的研究成果，在此基础上扩展了动态性和周期性的概念，另一方面结合多智能体技术，为动态运输调度的解决提供一条思路，起到抛砖引玉的作用。动态运输调度问题的解决，其重要的意义在于：1.2.1 提高服务水平，提升企业竞争力 通过对动态运输调度问题的分析，可以为企业解决运输调度问题的动态性提供一个有效的分析框架。确定企业所面对的物流运输需求处于何种状况，以及在此状况下对应的服务水平的设定和解决方法。而找出适合动态运输调度问题的解决方案，将大大提高
19、企业的服务水平，尽可能满足顾客的需求，同时经过合理优化的方案也能降低企业物流成本，增强企业的竞争力。1.2.2 增强物流系统的灵活性 研究动态运输调度问题的实质是研究企业物流运输系统在动态环境下如何优化，如何达到物流运输的目标的方法。这个问题的解决实现了企业物流运输手段在面对不确定性需求，不确定需求时间、交通拥挤等情况下，灵活决策，满足顾客需要的能力。因此将大大提高企业物流运输系统对单个顾客要求的反应能力，以及对意外环境的适应能力。1.2.3 促进信息技术在物流运输系统的应用 近年来，信息、通讯技术和硬件的高速发展，给各行各业带来了巨大的冲击。物流行业也不例外，GIS、GPS 以及 ITS 等
20、的应用给运输配送带来了新的机遇和挑战，动态运输调度问题的解决需要这些技术的综合应用，必将促进这些信息技术在物流运输中的广泛应用。1.2.4 提高运输智能化水平 随着城市的商业繁荣，大量商品需要送到商店和消费者手中，加重了城市交通压力，解决动态调度规划问题将有助于提高商品运输效率，减少物流对城市交通的影响，是发展智能交通系统的一个重要组成部分。此外，在理论上，该研究还充实丰富了物流科学、计算机科学、运筹学和自动控制等领域。1.3 本文的内容与结构 本文从现实的一些动态运输调度例子背景出发，通过对运输调度问题的回顾和分析，提炼出动态运输调度问题的定义，在对研究现状的简要概述后，将动态运输调度问题置
21、于物流系统和交通运输系统之中，对动态运输调度问题进行了分类，从中界定出适合于多智能体技术解决的一类动态调度问题扩展了的动态运输调度问题。最后，本文建立了一个针对扩展了的动态运输调度问题的智能物流运输模型。本文的第一章绪论部分提出了动态运输调度产生的现实背景，第二章主要介绍和研究动态运输调度问题，并对本文拟解决的扩展了的动态运输调度问题进行详细说明。第三章简要介绍了多智能体技术，并以此建立了智能物流运输模型，并针对模型中的算法、模块、所采用的理论和方法进行详细描述。第四章用了一个实例来分析此模型的可行性，最后第五章在此基础上对这一模型的优势和不足，作了结论和展望。面向动态调度的智能物流运输模型研
22、究 6 2 动态运输调度 2.1 问题的定义 2.1.1 运输调度问题的提出 国外将物流配送中的运输调度问题归结为 Vehicle Scheduling Problem。最早由 Dantzig和 Ramser 于 1959 年首次提出，很快引起运筹学、应用数学、组合数学、图论和网络分析、物流科学、计算机应用等学科的专家与运输计划制订者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及试验分析，取得了很大进展。该问题一般定义为：对一系列装货点和（或）卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量
23、、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定目标（如路程最短、费用最省、时间尽量少、使用车辆数尽量少等）。按照组织的行车路线的输出是不是一条预先规划好的路线，并且会不会被重新优化，运输调度问题可以分为静态和动态两类。静态运输调度问题可以归结为一般化的旅行商问题。在此问题中，一个旅行商人从一个城市出发，途经一系列城市，最后回到出发的城市，如何规划线路能使所走的距离最短。此类问题提出的时间较早，研究得比较充分，求解算法不下数百种，总括而言，基本上可分为精确算法和启发式算法两大类，精确算法包括分枝定界法、割平面法、网络流法、动态规划法等；启发式算法有构造算法、两阶段法、不完全优
24、化算法、改经算法等；还有一些亚启发式算法，如遗传算法、神经网络、模拟退火算法等。相对而言，动态运输调度问题引起人们关注的时间比较短，研究得也不是很多，许多的求解方法都是从静态运输调度问题中借用过去，加以改进的。2.1.2 动态运输调度问题 Psarafits【4】对运输调度问题是这样定义的：如果一个运输调度问题的输出是一条预先规划好的路线，并且这条线路不会被重新优化，而是根据事先知道的输入进行优化计算得出来的，那么这个问题就是静态的；反之，如果一个运输调度问题的输出不是一条预先规划好的路线，这个问题就是动态的。如表 2 所示，可以看出，这个定义是在对比静态运输调度问题的基础上建立起来的。表 2
25、 对此静态和动态运输调度问题 问题类型 静态运输调度问题 动态运输调度问题 规划前 假设所有与路径规划相关的信息在调度员做出路径规划前是完全已经知晓的。不是所有的与路径规划相关的信息在调度员做出路径规划前都已经知晓。规划后 与路径规划相关信息在规划好后不再发生变化或不再被考虑。与路径相关的信息可能会在路径规划好后发生变化 表 2 所说的相关信息既包括顾客的所有属性，如顾客的地理位置、现场服务时间以及每个顾客的需要量等等，也包括道路情况、车辆情况等影响路线规划的其他信息。很明显，放宽了信息完备假设的运输调度问题动态运输调度问题更适合于描述在现代物面向动态调度的智能物流运输模型研究 7 流运输中的
26、实际运输调度情况。在“按需物流”的概念中，其供应链的全部信息作为一个“假想仓库”被管理着，拟定的运输调度计划必须与市场同步，而市场又经常是瞬息万变的，因此在执行运输调度前，不可能获取完备的相关信息，在执行过程中，也不能确保没有新的需求出现。在实施 ECR 战略过程中也是这样，运输调度计划是建立在预测的基础上，各店铺的实际需求都是动态的。快递业务、电子商务中的集货和配送过程，如果待信息完备或以完备的信息为基础进行运输调度，不但浪费时间，而且大大提高了运输成本。上述问题都符合动态运输调度的定义。动态运输调度问题同时也是基于静态运输调度问题定义的，因此传统的静态运输调度问题的一些特征也表现在动态运输
27、调度问题上。我们知道，传统的静态运输调度问题被认为是 NP 难题，在一段合理的时间内，对现实中一定规模的问题并不总是能得到最优解。这意味着动态运输调度问题也必然是 NP 难题，因为在这种情况下，相当于每出现一个新的实时请求时，就要对一个静态运输调度问题进行求解。对于动态运输调度来说，当前问题的解总是暂时解，这种解只对应于当前所输入集合，在执行过程中，如果没有新的请求出现，那么这个暂时解就是最佳的，以图 4为例。图 4 一个动态运输调度问题的实例 没有容量限制的车为区域 A 内的顾客服务，实心表示提前请求的顾客，空心表示实时请求的顾客，实线表示在车辆离开车场前就已经由调度员规划好的路线，其中 b
28、c 段 d 顾客实时请求出现时车辆所在的位置。较理想的情况是新的顾客以最小的延迟时间被插入已经规划好的路线中，并且不改变未访问顾客的访问顺序。实际上，把新顾客插入到以前的路线是一项很复杂的任务，类似于重新对另一个静态运输调度问题进行求解。尽管我们可以想到，利用静态运输调度问题的求解方法对每一个动态请求来求解，以解决动态运输调度问题，但动态运输调度问题与静态运输调度问题还是有很多的不同，以至于思考方法，所用到的工具等都有显著的差异，不能简单地套用静态运输调度方法来解决动态问题。2.1.3 动态与静态运输调度问题的比较 相较于静态运输调度问题，动态运输调度问题在主要影响因素、输出结果的形式、解决方
29、案的特性、优化模型的描述四个方面都有很大的不同。（1）主要影响因素 A 车场 ab c d e面向动态调度的智能物流运输模型研究 8 动态运输调度问题包括两大影响因素，一个是时间。一个是未来的信息。在静态运输调度问题，如旅行商问题（TSP），车辆路径问题（VRP）等，都没有与时间相关的调度部分，所有的这些问题中，一般认为时间与旅行的距离成正比例，因此在问题的描述和问题的解中不必单独明确地考虑。然而在动态运输调度问题中，无论有无时间约束，时间尺度都是很重要的因素，我们在调度中特别是新的顾客请求出现或其他信息变为已知时，最起码要知道在任一时刻车队中每一辆车所在位置，一般情况下，我们需随着时间的推移
30、对路线规划进行调整。另一重要因素，未来信息，在静态问题中是不加考虑的，关于问题的所有输入信息被假设是稳定的，无论这些输入处于调度过程中的哪一点（开始、中间、结尾），都不随时间而变化。在动态运输调度问题中，就不是这种情况，这时任何输入的信息通常对于实时出现的事件来说都是不确定的，但对于发生在将来的事件来说，这种确切性只是暂时的。因为在任何真实的生活中，在动态问题中未来几乎总是不确定的。关于未来的概率信息有时是可以得到（例如我们可以知道在某一特定的日子某位顾客请求服务的可能性的大小），但是在更多情况下甚至根本无法获知信息（例如急救、火灾紧急服务等等）。（2）输出结果的形式 通常，静态运输调度问题的
31、输出路线规划，其持续时间或者是已知的，或者知道什么时候结束。但动态运输调度问题的输出却正相反，其持续时间既不是已知的，又不知道什么时候结束，是可以修整的或者说是末端开放的。实际上一个典型的动态运输调度问题是一个开放的过程，时间周期是不确定的。这意味着在静态问题中结果是一个闭合的路径（车辆会返回车场），而在动态问题中结果往往只是一条非闭合的路径。（3）解决方案的特性 在解决动态运输调度问题过程中，近期事件应优先考虑，必须建立信息更新机制，要求重新分派车辆并调整车辆途经点的次序，计算速度应该更快。在静态运输调度问题中，因为输入信息不需更新，无论是在行驶的起始时刻，中途还是结束时刻出现的事件具有相同
32、的权重。而在动态运输调度中，信息总是处于动态变化之中，立即根据要求调配车辆资源（例如决定分派一辆车或做出路径规划决策）是不明智的做法，因为其他中间事件可能使得以前的决策变得不再最优，而且将来的信息还可能发生变化。因此将注意力更多的集中于近期事件在动态运输调度中是必要的。事实上对于动态运输调度问题所有的输入在路径规划的过程中的任一时刻都可能变化。例如车辆可能发生故障，顾客请求的服务时间要求可能需要调整，取消服务的情况也可能出现、由于未预测到的天气变化而使船不能如期到达预定港口等。因此在动态运输调度问题中信息更新机制作为算法结构以及输入输出接口的一部分是必要的。数据结构和数据库管理技术在动态运输调
33、度方案中很重要，因为它既有助于有效地修改问题的输入，又能有效地得到这些修改的结果。但在静态运输调度问题中这种机制不存在或者最多只是问题核心部分附带的内容。在动态运输调度问题中，新的输入的出现可能要求对已经完成的决策进行调整。这既涉及到车辆途经点的次序的调整，又涉及到车辆的重新分派。因此新的输入信息如新的顾客请求的出现可能使得有必要对一辆或更多辆车途经点的次序进行调整，或是重新分派车辆适应顾客服务请求，或者两者都需要。在实时环境中，当要重新优化路径或重新分派车辆时，对计算速度的要求要比在静态环境下对计算速度要求更高。在静态运输调度问题中一般可以允许等待几个小时用来得到问题的解。在这种环境下，可以
34、得到比较精确解，代码的运行也可以时批处理方式运行。但在动态运输调度中就不可能是这样了，这时调度员希望尽可能快地（以分钟而不是以小时计）知道该特定问题在出现新的信息时的解。调度员也可能希望在采取最后的行动前搞清楚不同条件下解的情况。这种运行时间约束通常意味着不可能采用精确算法。相应的，启发式方法得到大量应用，并且只需局部最优化就行，例如插入法、K 交换法以及其他的改进法都有助于上述目标的实现。（4）优化模型的描述 在描述动态运输调度的优化模型时，其目标函数、时间约束与静态运输调度相比都有很大的面向动态调度的智能物流运输模型研究 9 不同，而且车队规模的弹性更低，有时还需要考虑排队问题。传统的静态
35、运输调度问题的目标一般是最小化行驶距离或最小化车辆行驶时间。然而这在动态运输调度问题中可能是没有意义的。因为动态运输调度问题的整个过程是开放的，总的车辆行驶时间在调度是也是开放的，即使在调度时确定可以达到最小，但是并不能确定在后续过程中这个总的车辆行驶时间仍然是最小的。动态问题中对解的评价更有意义的可能是服务能力，例如顾客请求满足程度等，遗憾的是这样的目标函数通常在算法上可能不便于实现，而只能以一些相近的传统静态问题的目标函数来代替。在时间约束方面，静态问题和动态问题的主要区别在于动态问题中的输入，如最早的集货时间或最晚集货时间，比静态问题中相应的时间约束要更宽松一些。理论上，如果不能满足顾客
36、的时间约束，还可以以一定的成本额外增加一辆车对该顾客提供服务。然而这个方法在动态运输问题中不一定适用，因为不一定有备用车辆随时可供使用。在静态运输调度问题中算法的执行与路径规划的执行之间的时间间隔通常足够长，因此可以调整车队的规模，在动态问题中就不具有这种弹性，如果车辆资源有限，有些顾客得到的服务质量可能会更加差，从而导致排队现象的出现。当顾客请求出现的速率超过某个极限值时，动态运输调度系统可能会出现拥堵现象，系统在不产生额外延迟的情况下不可能处理所有的请求。这种情况下，任何根据从传统的静态问题借鉴而来的目标函数构造出来的算法都只会产生无意义的结果。这个时候，就有可能必须在模型中引入排队论才能
37、有效解决动态运输调度问题。2.2 研究文献回顾 随着物流业的发展，动态运输调度问题逐渐引起人们的研究兴趣，在过去的十几年里，在各种期刊和书籍中出现了大量研究动态运输调度问题的文献，大都是国外文献，国内由于对动态运输调度问题的研究开始得比较晚，近几年才陆续有少量学术文章发表，而且主要是综述和介绍类。因此，本节主要依据国外文献，对动态运输调度问题的典型问题、理论与模型、策略和算法、实际应用方面分别做一番介绍，以期大概描绘出动态运输调度问题的当前研究现状。2.2.1 典型问题 早在 20 世纪 70 年代 Wilson【5】就对动态运输调度中的一类重要问题动态拨召车辆问题（DialARide）进行了
38、研究。在该问题中，商品在顾客指定的地点集货并送到另一个顾客指定的地点，要求在运输调度中确保每一顾客请求的起点和终点能一一配对，此过程中顾客的请求是动态的。Wilson 提出了插入法，插入的原则是在所有可行插入位置上最小化从需求发生到计划装载的延迟时间，从转载点到卸货点之间的行驶时间，以及计划装载和承诺装载时间的时间差。其后，此问题引起学者们极大的兴趣，Madsen【6】将其应用到运输老人和残疾人的动态拨召运输系统上，提出了一种新的插入方法，算法先用插入法静态安排车辆路径，然后根据新顾客和已插入顾客之间可能存在的利益冲突抽象出一个冲突函数，并以最小化冲突函数作为新顾客的插入准则，按序列模式处理实
39、时需求。Teodorovic【7】等人应用模糊推理来处理路线规划以及在动态情况下对路线的选择；Attanasio【8】等人将问题扩展到多车辆的情形，并采用了并行启发式算法。至 2005 年，Zhihaixiang【9】等人将更多复杂的约束条件加到 DialARide 问题上，大大丰富了此问题。动态旅行修理工问题（Dynamic Traveling Repairman Problem DTRP）是指，分布在一定区域的服务请求随机到达，服务由一定速度一定载重量的车辆提供，问题的目标是找到合适的运输调度策略，确保系统期望时间最小（等待时间加现场服务时间）。问题的典型例子是电力公司的修理工挨家挨户地修
40、理电力供应中的突然故障，由于故障发生的突然性，问题呈现出明显的动态性。面向动态调度的智能物流运输模型研究 10 这个问题最早由 Bertsimas【10】等人提出，他们用排队论、几何概率、组合优化方法研究了几种不同的策略，此后，Papastavron【11】、Weintraub12等人对这一问题都进行了深入研究。邮件快递服务，一般在一个地方收集邮件和包裹，并在某个时间限制内将货物安全地送到另一个地方，他们在将货物送到远方的一个终端前需要在本地收集要送到外地的包裹并将他们合并起来，类似地，来自远方终端的货物需要在本地被配送。大多数集货请求是动态的，需要尽可能地在当天得到服务。Gendreau【1
41、3】【14】、Cordean【15】等人对这个问题进行了深入研究。紧急服务，以报警、火灾、救护等为例，所有的顾客都是动态的。大多数情况下，没有事先的路线，因为请求通常得到服务后又会出现新的请求。于是问题就是安排最恰当的车（例如最近）服务新的请求，因此安排紧急服务的方法根据位置分析来确定车辆和司机所应前往的位置。Gendreau【16】等人专门讨论了有关此类问题。2.2.2 理论与模型 动态运输调度问题的比较准确的定义是 Psarafits【4】通过将静态运输调度与动态运输调度作比较提炼出来的，之后，1995 年 Psarafits【17】发表了篇综述，全面地回顾了动态运输调度问题。在明确动态运
42、输调度问题定义的基础上，Lund【18】等人于 1996 年引入对动态运输调度问题的一个测度动态度，描述了问题的动态程度。当时采用的指标是动态请求的数目在所有请求中所占的比例，没有考虑到请求出现的时刻对动态程度的影响。Larsen【19】对此作了进一步扩展，并且还考虑了顾客服务时间的可能时间窗口，完善了动态度的定义。Powell【20】等人则集中研究了基于不确定规划的模型，同时对不同的动态运输调度问题如动态交通分配问题（该问题寻找通过容量与时间有关的网络的链路将货物从起点到终点的最优路径）也作了深入研究。他们还讨论了如何评价解的质量，这在比较动态模型与静态模型非常有用。他们指出在静态模型中找到
43、一个合适的目标函数相当容易，并且该目标函数通常是用来评价解的质量的办法，然而对动态模型而言，在作业计划期间目标函数常常无助于评价解的质量。2.2.3 策略与算法 关于动态运输调度问题的算法主要有两大类，串行算法和并行算法。串行算法主要包括：简单策略、快速插入法以及亚启发式算法。而并行算法主要是基于禁忌搜索的并行算法。Bertsimas【21】、Swihart【22】等人研究的简单策略，归纳起来主要有这样几种：（1）先来先服务（First come first served，FCFS）策略，调度员根据需求到达的顺序依次安排服务。（2）随机排队中位（Stochastic queue medium，
44、SQM）策略。这项策略对先来先服务策略进行了改进，在该策略中车辆位于服务区的中位，当请求到达时，位于中位的车辆以先来先服务的顺序提供服务。服务结束后，车辆回到中位。（3）最近服务（Nearest neighbor，NN）策略，即当前顾客服务结束后，车辆对最近的未服务的请求提供服务。（4）旅行商（TSP）策略。即请求被分成几个集合，确定了一个请求集合后即可转化为一个旅行商问题，并根据该旅行商问题的最优解对请求进行服务。插入算法比较简单，在要求的解不是很高的情况下，得到了大量应用。Roy【23】等人提出的一种插入算法，将实时顾客插入当前路径中最合适的位置，算法简单，在硬件上运行速度也非常快。Psa
45、rafits【4】提出了一个用于紧急海上补给问题的插入算法。该算法在滚动作业计划周期内执行。只有集货请求发生的时间在【t，t】内才会被考虑（是滚动作业计划周期），当且仅当集货请求发生在【t，t】内时（01），才明确地被分配给一艘船。此后，MitrovicMinic【24】等人扩展了滚动作业计划的概念。当一个新的请求出现时，主要把努力放在优化当前解的近期部分（一般对应于包裹的收集期），而把较少的努力放在远期部分（一般对应于包裹的配送期）。这种方法是考虑到车辆路径的较后部分可能随时间变化而发生变化，从而在早期将其进行足够的优化是没有意义的。面向动态调度的智能物流运输模型研究 11 动态运输调度问题
46、的最好算法一般都是亚启发式算法。Osman25指出这些亚启发式算法能够有效处理大规模的组合优化问题，得到近似的最优解。亚启发式算法主要包括：（1）模拟退火算法（Simulated annealing）,通过对局部最优解的扰动寻找近似全局最优解。（2）遗传算法（Genetic algorithm，GA），模拟生物遗传过程中基因重组，用一定的规则选择，最后重组出近似全局最优解。（3）人工神经网络（Neural networks），模拟神经网络的自适应性，通过大量的训练，使神经网络能够生成经验似的全局最优解。（4）专家系统（Expert system），利用专家的经验形成规则，从而有效地寻找全局最优
47、解。其他还有蚁群算法（Ant colony methods）、禁忌搜索（Tabu search，TS），适应记忆技术（Adaptive Memory，AM）及变量领域搜索（Variable neighborhood search,VNS）等算法。Ghiani【26】等人指出后三种算法组合使用时被证明是最成功的算法。亚启发式算法在执行时，因为计算量非常大，一般都采用并行算法，在实践中采用的较多的是并行禁忌搜索算法。有关于算法的评价，Bertsimas 和 SimchiLevi【27】在同时研究了静态运输调度问题和动态运输调度问题的基础上，评价了已知算法在应用时的健壮性和渐进性。他们认为运输调度问
48、题的解析研究提供了对算法结构的新的知识，使得对经典算法的效果进行分析成为了可能，也使我们能更好地理解将运输调度问题和其他问题（如库存问题）整体考虑的模型。同时，他们也指出研究运输调度问题中的不确定性因素将有助于构造实际用于动态不确定环境中的运输调度问题的算法。2.2.4 实际应用 Gendreau 和 Povtin【28】指出在动态运输调度实际应用中还有很多问题需要研究。首先是需要研究用于提前构造车辆路径的需求预测。其次，不应该把研究的焦点仅仅集中到服务请求在一定时空范围出现的不确定性上，而应该考虑多种不确定，如请求的取消和服务的延迟。再次，他们还指出偏离预定目的地问题应该值得更多的关注。最后
49、，由于通信技术的发展，人们可以得到大量的在线信息，所以有可能让在预定路线行驶的车辆改道以向新的顾客行驶，他们建议为了评估在计划期内缺乏完全的信息造成的损失，需要研究并行算法的实现以及对最坏情况进行分析。总体而言，国外动态运输调度问题的研究比较充分，已经搭建起了整个动态调度运输问题研究的框架。对照静态运输调度问题，阐明了动态运输调度问题的定义、特征、建模等，针对动态拨召车辆问题等几类典型问题的持续深入研究，发展了适合动态运输调度问题的策略和算法，并且已经广泛应用于实践当中。但随着现代 IT、通讯技术的发展，一些新技术的引入可以为动态运输调度问题的研究提供新的方向，而且如果将动态运输调度问题放到更
50、广阔的环境中，放到物流的网络、放到交通运输的网络中，研究将获得很多新的有意义的成果，可以说，从这些方面动态运输调度问题的研究还有广阔的空间。本文就是基于这一点，引入新从技术多智能体系统技术，来研究和解决动态运输调度问题。在此之前，首先要对动态运输调度问题现有的研究框架的部分细节作一些扩展和补充。这主要是关于动态运输调度问题动态性的度量和周期性的定义。因为虽然现有的研究框架已经有了动态度的概念，但其区分度不高，涵盖的范围也不够。而对于周期性，虽然也有文献提到可以用周期性来预测动态信息，从而减少动态调度问题的动态性，但对周期性的定义，以及度量和如何应用都鲜有研究。其次，要界定出适合多智能体系统技术