车辆调度与优化

物流配送车辆调度问题是指：在给定运输任务的条件下，如何派车、组织循环运输，使空驶里程最少，运输成本最低。现在我国大多数的物流公司运输资源分派不均、配送路线安排不合理、运力资源浪费严重，而缺少完善的物流配送车辆调度优化方案是造成此现象的重要因素之一。因此对物流配送车辆调度问题的研究含有重要的现实意义。现在对单车场、封闭式物流配送车辆调度问题研究较多，而对多车场开放式物流配送车辆调度问题研究较少，但是多车场开放式物流配送车辆调度问题有很强的应用背景。本文针对此问题，建立了一种灵活的多目的组合优化模型，设计了适合多车场开放式车辆途径问题的通用染色体编码方案，并对遗传算法中的交叉变异操作做了具体阐明。此模型能够方便的增减优化目的值，并通过测试用例验证了本文设计的优化模型和遗传算法在解决多车场多目的开放式物流配送车辆调度问题中的可行性。自动化立体仓库出库端车辆调度方略的设计是物流配送车辆调度中的一种核心问题，好的调度方略能够大大缩短出库端的配货时间。为此本文引入动态优先级理论，并运用该理论对大型AS/RS出库口车辆调度问题进行了进一步研究与分析，提出了基于动态优先级的AS/RS出库端车辆调度方略，并开发了对应的AS/RS出库口发货资源监控系统，即AS/RS出库口车辆调度系统，优化了AS/RS出库端车辆调度方略，大大提高了物流配送当中的配货效率。本文建立的多目的组合优化模型以及设计的遗传算法求解方案，能够有效的缩减物流配送中的送货时间；设计的AS/RS出库端车辆调度优化方略及开发的AS/RS出库端车辆调度系统，能够有效缩减车辆在出库端的配货时间。本文对以上两种物流配送中的车辆调度问题进行研究，大大提高了物流配送效率、减少了物流配送成本。核心词：物流配送；车辆调度；多目的组合优化；遗传算法第一章绪论课题背景物流(Logistics)：指在适宜时间，将适宜的物品以适宜的数量精确地送到顾客手中，它是供应链中最重要的构成部分。普通意义上是指在生产和生活中所涉及的多个物质实体由供应方向需求方的物理性转移过程。这一概念将物流定义在有用的物、供方、需方等几个基本因素之上。也就是说，我们普通所指的物流是指人们在生产和生活中发生的故意义的物流行为。整个物流过程是一种物理过程，只变化时间和空间的状态，不变化其使用价值。其中，时间状态的变化称之为仓储、流通加工等活动，空间状态的变化称之为运输、搬倒等活动。物流配送是物流系统中的一种重要环节，它是指按客户的订货规定，在物流中心进行分货、配工作，并将配好的货品及时送交收货人的物流活动。配送成本直接关系到物流公司和部门的效益，现在我国的大多数的物流公司运输资源分派不均、配送路线安排不合理、运力资源浪费严重,根据中国仓储协会对146个公司的调查显示，用于运输的费用占整个物流费用的比例分别为：在生产公司原料物流中占58%，在生产公司成品物流中占73%，在商业物流中占52%。因此物流配送车辆调度方案的合理优化，对于整个物流运输速度、成本、效益的影响至关重要。运输是指“物”的长距离的移动，任何跨越空间的物质实体的流动，都可称为运输。运输是物流的中心环节之一，被称为国民经济的动脉和当代产业的支柱，从社会经济的角度讲，运输功效的发挥，缩小了物质交流的空间，扩大了社会经济活动的范畴并实现在此范畴内价值的平均化、合理化。在社会经济的发展中，运输的重要性己经被人们所确认，成为国民经济的命脉。从物流系统的观点来看，运输作业的核心因素涉及运输成本和运输速度两个方面。运输成本：是指为两个地理位置的运输所支付的款项，以及管理和维持转移中存货的有关费用，应采用能把系统总成本减少到最低程度的运输方式。运输速度：是指为完毕特定的运输作业所需耗费的时间。运输速度和成本的关系，重要体现在下列两个方面：首先，运输商提供的服务越快速，实际需要收取的费用也就越高。另首先，运输服务越快，转移中的存货就越少，可运用的运输间隔时间越短。因此在选择最合理的运输方式时，至关重要的问题就是如何平衡其服务的速度和成本。运输重要目的就是要以最低的时间、财务和环境资源成本，将产品从原产地转移到规定地点。同时，产品转移所采用的方式必须能满足顾客有关交付推行和装运信息的可得性等方面的规定。因此在物流系统中，必须精确地维持运输成本和服务质量之间的平衡。低成本运输和高质量服务是令人满意的。物流配送车辆调度就是研究如何合理运输的问题，所谓合理运输就是在实现物资产品实体从物流中心至消费地转移的过程中，充足有效地运用多个运输工具的运输能力，以最少的人、财、物消耗，及时、快速、按质、按量和安全的完毕运输任务。其标志是：运输距离最短、运输环节最少、运输时间最短和运输费用最省。据统计运输费约占整个物流费用的40%，占销售收入的%。物流配送车辆调度问题就是指在给定运输任务的条件下，如何派车、组织循环运输，使空驶里程最少，运输成本最低。车辆调度是物流管理最重要的部分，对的合理的调度能够有效减少车辆的空驶率，实现合理途径运输，从而有效减少运输成本，节省运输时间，提高经济效益。课题研究的意义物流产业的发展，将从整体上变化经济运行的方式，提高经济运行效率，对增强国际竞争力将起到巨大的推动作用。我国国民经济的发展呼唤物流的进一步发展，对物流的发展规定以下：(1)减少流通成本在GDP中的比重：在我国现在工业公司生产中，直接劳动成本占总成本的比重不到10％，而物流费用占商品总成本的比重，从账面反映约为40％，全社会物流费用支出约占GDP的20％，而其它发达国家普通在10%左右。这反映了我国物流系统落后，流通成本太高，反映了我国国民经济运行质量不高。通过发呈当代物流业来增进物流合理化，减少流通成本在GDP中的比重，无疑将成为我国新的经济增加点。“十五”期间，如果我国物流费用减少到占GDP的15％，每年将为社会直接节省2400亿元的物流成本。(2)减少公司流动资金占用：我国工业公司和流通公司由于物流基础设施、技术和管理的落后，原材料、半成品、成品积压严重，大量流动资金被占用，周转速度很慢，物流成本过高。据统，1992年，国有独资、控股工业公司流动资金占用1万多亿元，周转速度为次/年；1999年，国有独资、控股工业公司流动资金达31000亿元，周转速度仅次/每年，与发达国家相比非常落后。如果工业公司把物流职能分离出来交给第三方物流公司，通过其先进、科学的专业化服务，就能够减少流动资金占用，提高核心竞争能力，实现从粗放式经营向集约式经营转变。(3)电子商务的发展需要物流做基础：电子商务是流通领域的一场革命，它把3商品买卖虚拟成一种大的市场，使客户在任何地点、任何时间都能够购置商品。但是，电子商务需要将网上订的货品及时送到可能在任何地方的客户手里，这就给物流系统带来很大的挑战。事实上，物流已经成为电子商务发展的瓶颈，需要建立含有响应性、灵活性和可视化的当代物流系统，需要第三方物流公司的服务。世界500强中相称多的公司都是通过第三方物流来解决它的供应链与销售问题的，诸多跨国公司在欧洲、亚洲、美洲等地分别有不同的第三方物流公司为他服务。(4)当代物流产业的发展，将减少由于低水平、条块分割的物流方式造成的巨大物耗：在传统的物流框架下，一件商品从生产出来到最后的消费环节，最少要被搬倒、装运十几次。实施社会化的多式联运、一单究竟，物流过程中的物耗最少能够减少几倍。我国汽车空驶率达37％左右，意味着全国每年有150多万辆载重汽车无活可干，这种潜在浪费最少也在数千亿元。按当代物流规定，合理的流程设计可使空驶率减少到5％下列。在当代物流集约化、一体化的发展中，配送是直接与消费者相连的重要环节，其核心部分为配送车辆的集约、货品配装及送货过程，而配送车辆优化调度是物流系统优化、物流科学化的核心一环，是货品从配送中心送达收货人的过程。配送首要解决的是车辆的调度问题，几十年来这始终是一种研究的热点，在满足和完毕各任务的前提下，对的合理的安排行车路线、提高配送车辆的运用率就能够有效的节省时间从而减少运输成本。另外对出库口车辆调度问题的研究，将有效减少货品装配的时间。因此本文对物流配送车辆调度的研究含有重要意义。国内外研究现状车辆调度问题最早是由Dantzig和Ramsert在上个世纪50年代末期提出，该问题普通称之为VehicleRoutingProblem(VRP)或者VehicleSchedulingProblem(VSP)，现在我们将车辆调度问题一律简称为VRP。VRP提出后就很快引发运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科专家与运输计划制订者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科的专家对该问题进行了大量的理论研究及实验分析，获得了很大进展。国外对物流配送车辆优化调度问题作了大量而进一步的研究，例如早在1962年，Balinski等人首先提出VRP的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简朴的VRP模型；1964年，Clarke和Wright提出了一种启发式节省法来建立车队配送路线；1968年，Rao等人在VRP集分割的基础上引入了列生成办法进行求解，这种算法本质上是最短途径算法，同时结合了分枝定界算法；1971年，Eilon等人提出将动态规划法用于固定车辆数的VRP，通过递归办法求解；1981年，针对带能力约束、时间窗以及无停留时间的VRP，Fisher提出了三下标车辆流方程；Thangiah于1991和Joe于l993分别用遗传算法求解VRP，但是都存在“早熟收敛”的问题；，Tan，Lee，Du结合遗传算法、tabu树搜索算法的优点，形成知识库，用人工智能的办法来求解；，Taranrilis,Kiranondis使用空间决策支持系统来解决车辆途径问题。在国内,有关车辆调度问题的研究是在20世纪90年代后来才逐步兴起的，比国外相对落后。国内研究对象重要是旅行商问题(TravelingSalesmanProblem，简称TSP)、中国邮递员问题(ChinesePostmanProblem，简称CPP)、有向中国邮递员问题(DirectedChinesePostmanProblem，简称DCPP)等，系统性研究还极少见到。西南交通大学的李军专家和郭耀煌专家对车辆优化调度的基础理论及各类问题进行了系统的研究；李大为等以TSP的近来距离启发式为基础，通过设立评价函数来解决时间窗约束，求解了简朴的VRP。另外在运用当代优化算法(如:遗传算法、神经网络办法、模拟退火等)对简朴TSP的求解获得了一定成果。蔡延光等应用模拟退火法针对满载问题进行了求解。总体来说，现在我国对车辆调度问题的理论研究仍相对单薄，需要进一步研究。本文内容的安排本课题的研究以内蒙古蒙牛乳业股份(集团)有限公司的物流配送业务为背景，重要研究两方面内容：首先，对多车场多目的开放式物流配送车辆调度问题做了研究，以此能够优化对客户的派车问题及最佳车辆途径的选择问题。另首先，对AS/RS出库端车辆调度方略做了研究，以本文建立的方略对出库口的车辆分派车位，能够减少车辆的配货时间。本文的研究将在最大程度上减少蒙牛集团的运输成本，给蒙牛集团带来可观的经济效益。本文研究的具体内容以下：第一章绪论：介绍了本文研究的背景以及研究的目的与意义，并对国内外对车辆调度问题的研究现状作了简朴介绍。第二章车辆调度问题概述：首先对物流配送车辆调度问题进行了描述，另首先介绍了车辆调度问题的构成要素和车辆调度问题的分类，最后列举了车辆调度的有关求解算法。第三章遗传算法概述：首先对GA的背景作了简朴的介绍，接着对GA算法的基本概念、工作流程和算法的构成做了具体描述。第四章用遗传算法解决多车场多目的开放式车辆调度问题：首先介绍了两种求解多车场车辆调度的办法，然后对多车场多目的开放式车辆调度问题的研究背景进行了描述，在此基础上拟定了多车场多目的开放式车辆调度问题的数学模型，并具体描述了用遗传算法对多车场多目的开放式车辆调度问题的求解过程，最后用实例证明了用遗传算法求解此问题的可行性。第五章对AS/RS出库端车辆调度方略做了研究，提出了基于动态优先级的AS/RS出库端车辆调度方略，并开发了对应的AS/RS出库端发货资源监控系统，即AS/RS出库口车辆调度系统，以此方略对出库口的车辆分派车位,能够减少车辆的配货时间。第六章总结与展望：归纳与总结了本文的创新之处，并提出进一步研究车辆调度问题的方向。第二章车辆调度问题概述车辆调度问题的描述“配送”一词是日本引进美国物流学时，对英文单词delivery一词的意译，我国转学于日本，也直接用了“配送”这个词。配送是物流系统中由运输派生出的功效，是短距离的运输。含有：①配送距离较短，位于物流系统的最末端，处在支线运输、二次运输和末端运输的位置。②在配送中，也包含着其它的物流功效，是多个功效的组合。③配送是物流系统的缩影，也能够说是一种小范畴的物流系统。从物流来讲，配送几乎涉及了全部物流的要素，车辆调度就是其中一种最重要且故意义的要素，因此本文研究的是物流配送车辆调度问题。物流配送车辆调度优化问题最早是由Dentzing和Ramser在1959年第一次提出的。从此，车辆调度优化问题很快引发运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制订者的极大重视，同时也逐步成为运筹学与组合优化领域的热点研究问题。由于它应用的广泛性和经济上的重大价值，始终受到国内外学者的广泛关注。国外将物流配送车辆优化调度问题归结为或称之为VehicleRoutingProblem和VehicleSchedulingProblem。本课题采用的是后者，也就是将车辆调度问题归结为VSP问题：VehicleSchedulingProblem。物流配送车辆调度问题的普通性定义是：物流配送车辆调度问题是把一系列的装货点和（或）卸货点，有机的组织起来，形成一系列行车线路，使待调度车辆能够高效、节能且有序地通过这些点。固然，这种组织方式是应当在满足一定的约束条件（例如：顾客对货品的需求量、一次性发货量、应交发货时间、单个车场的车辆容量限制、路程约束、时间限制等），最后达成缩短里程、减少开支费用、缩短运输时间、使用车辆数尽量少等优化目的。物流配送车辆调度问题普通研究的是在配送中心及顾客位置均已知、资源及运输能力充足、各顾客需求量己知的前提下，如何合理、高效、低成本的解决分派与运输的问题，也就是说如何将货品从配送中心按照一定的规定发送到若干个顾客点。配送方案应当涉及两个有关的环节：①有哪些顾客要被分派到一条回路上，即有哪些顾客的货品应当安排在同一辆车上；②每条配送路线上顾客的连接次序。物流配送车辆调度的最优解事实上是一种效率最高的运输方案，它应明确的规定应派出的车辆型号、车辆数以及每辆车的具体行车路线。实施这一配送方案，即能够满足顾客的需求，又能够使总的运输行程最短。车辆调度问题的构成要素物流配送车辆调度问题重要涉及货品、车辆、配送中心、客户、运输网络、约束条件、和目的函数等要素。(1)货品货品是我国交通运输领域中的一种特有专用概念，交通运输领域将其经营的对象分为两大类：一类是人，一类是物。“物”这一类的运输目的统称为货品。我们这里所说的货品是指物流配送的对象，每批货品都涉及品名、包装、重量、体积、规定送到(或取走)的时间和地点，能否分批配送等属性。(2)车辆车辆是“车”与车的单位“辆”的总称。所谓车，是指陆地上用轮子转动的交通工具；所谓辆，来源于古代对车的计量办法。本文所说的车辆是指运载货品的工具，车辆的重要属性涉及：类型、工作时间、配送前的停放位置、载重量以及配送任务完毕后的停放位置等。(3)配送中心配送中心是指接受供应者所提供的多品种、小批量的货品，通过存储、保管、分拣、配货以及流通加工、信息解决等作业后，将按需要者订货规定配齐的货品送交顾客的组织机构和物流设施。本文所说的配送中心是指从事配送业务的物流场合或组织，如能够进行货品集中、分拣、配货、送货等的仓库、车站、港口等固定场合。在物流配送系统中，配送中心能够只有一种，也能够同时含有多个。配送中心专业性强，和客户有固定的配送关系，普通实施计划配送，需配送的商品有一定的库存量，普通状况极少超越自己的经营范畴。配送中心的设施及工艺流程是根据配送需要专门设计的，因此配送能力很强，配送距离较远，配送的品种较多，配送数量比较大。使用配送中心配送覆盖面宽，规模大，因此，必须有一套配套的大规模实施配送的设施。本文的研究背景就是基于配送中心的物流配送中车辆调度问题的研究。(4)客户客户指的是物流配送的服务对象，能够是多个零售店，也能够是分仓库，还能够是别的仓库的外调。也就是说客户是有配送任务的对象的统称。客户的属性涉及需求数量、需求时间、需求次数及现在需求的满足动态等。8(5)运输网络本文的运输网络采用了离散数学中对网的介绍，配送中心、客户、停车场等构成网络的顶点、它们之间的交互运输构成了无向边，具体的运输任务被称为由有向弧构成的运输的网络。边、弧的属性涉及方向、权值和交通流量限制等。在运输网络中，边或弧含有一定的权值，该值能够表达为距离、时间或费用。边或弧的权值变化含有下列几个状况：固定不变，不随着时间和车辆的不同而变化；随时间段或者车辆不同而变化；既随着时间的不同而变化，又随着车辆的不同而变化。对运输网络中的定点、边或弧的交通流量规定分为下列几个状况：无流量限制；边、弧限制，即每条边、弧上同时行驶的车辆数有限；顶点限制，即每个顶点上同时装、卸货的车辆数有限；边、弧、顶点都有限制。(6)约束条件物流配送车辆调度问题应满足下列约束条件：能够满足全部客户对货品品种、规格、数量的规定；能够在客户规定或者承受的时间内将货品送到；运输车辆每天的运行时间、运行历程都要有一定的限制，不能超出预定的时间或者里程；在物流配送过程中实际装载的货品不能超出车辆的最大载重规定，也就是不能超载；固然，客户的需求也必须在物流中心现有的运力范畴内，也就是现在有这个能力去完毕待完毕的任务。(7)目的函数目的函数是指所关心的目的(某一变量)与有关的因素(某些变量)的函数关系。简朴的说，就是你求解后所得出的那个函数。在求解前函数是未知的，按照你的思路将已知条件运用起来，去求解未知量的函数关系式，即为目的函数。本课题研究的物流配送车辆调度问题，能够只选用一种目的，也能够同时选用多个目的。使用概率比较多的目的函数重要有：①配送的距离最短，也就是在配送过程中车辆所走的路程最短。在实际的物流配送中，配送里程直接关系到配送车辆的耗油量、磨损程度以及司机疲劳程度等因素。因此，在众多的目的函数中选择配送里程最短的目的，在某种程度上能够直接减少运输成本。②配送车辆的载重量与公里数最少，这种方式的目的是将配送距离与车辆的载重量进行了有机结合，综合来考虑载重量与配送距离之间的关系，以达成最优化的配备，是比较惯用的目的之一。9③综合费用最低，完毕最多的任务，花最少的成本，这是物流配送中的一种根本原则。减少各项开支的综合费用是实现物流配送业务中获得良好经济效益的根本规定。在物流配送中，与配送有关的费用涉及：车辆维护费用、车辆耗油费用、车队管理费用、装卸工所需费用、各部门人员工资费用等。④准时完毕任务，无论是分仓库还是分销点，多个顾客都对需求的交货时间有着严格的规定。配送任务完毕的准时性，很大程度上决定了配送公司在客户心中的地位，决定了公司的信誉度。多个成本即使是必须考虑的因素，也是最实际的因素，但是为提高配送服务质量，准时完毕顾客的需求，有时需要将准时性最高作为配送路线的目的。⑤使用的车辆数最少，该目的考虑的是使用尽量少的车辆去完毕指定的配送任务。前面的目的叙述了各项指标的规定，但是如果车辆跑的距离最短、也是准时达成的，但是使用的车辆都没有满载，这无疑也是对资源的一种浪费，也不能是整体配送效益达成最优，因此必须规定车辆的满载率最高，以充足运用车辆的装载能力。⑥劳动消耗最低，充足考虑人的因素。也就是使用最少的司机数，这固然和前面使用最少的车辆数是一致的，只有车辆少了，司机才会少，只有车辆都装满了，才会使用最少的车辆。只有选择的距离最短了，司机才干工作最短的时间，这些都是重要的目的值。车辆调度问题的分类车辆调度问题(Visual-ScheduleProblem，VSP)被提出后，国内外各学科的学者从不同角度对它进行了多个研究，并各自按不同的原则对其进行了分类。综合起来可分为下列几个：(1)按车场数目分：有单车场车辆调度问题和多车场车辆调度问题。单车场问题指配送系统中仅有一种配送中心，多车场车辆调度问题指配送系统中存在多个配送中心。(2)按配送任务特性分：分为纯送货问题、纯取货问题以及取送混合问题。其中纯送货问题指仅仅考虑从物流中心向客户送货，而不考虑从顾客向配送中心送货；纯取货问题指单纯考虑把各客户供应的货品取到配送中心不考虑配送中心给客户供货问题；取送混合问题是上面两者的有机组合，既要考虑将客户需求的货品从物流中心送到各个客户，同时还考虑将客户提供的货品从客户取到物流中心。(3)按车辆载货状况分：分为满载问题、非满载问题以及满载和非满载混合问题。10满载问题指的是货运量不不大于车辆容量，完毕一项任务需要不少于一辆车；非满载问题指的是货运量不大于车辆容量，多项货品合用一辆车，在实际的车辆配送过程中经常会出现这种处在非满载的状态；满载和非满载混合问题是上述两者的有机组合，既存在一部分客户需求和供应的货品数量不不大于或等于车辆的载重量，同时又存在另一部分客户需求量或供应的货品数量不大于车辆的载重量，上述状况就造成一部分派送车辆满载运行，而另一部分运行在非满载的状态。(4)按客户对货品解决时间的规定分：分为无时间约束问题和有时间约束问题。其中无时间约束问题指的是客户对货品的取走和送到的时间没有严格的规定；有时间约束问题指的是客户规定将其需求的货品在一定的时间范畴内送到，并且将供应的货品在一定的时间范畴内取走。有时间约束问题又分为硬时间窗问题和软时间窗问题，硬时间窗问题指的是对任务的完毕有硬性的时间限制，或者说时间规定。软时间窗问题指的是有一定的时间约束，但是相对比较宽松，尽量在顾客规定的时间范畴内将货品送到或者取走，但是如果超越了规定的时间限制可能要有一定的处分机制。(5)按车辆类型分：分为单车型问题和多车型问题。单车型问题指全部配送车辆类型和容量相似，这种状况方便统一管理和装卸。多车型问题指在执行任务过程中的配送车辆类型和容量不完全相似，这种状况解决起来比较复杂。(6)按车辆对车场合属关系分：分为开放式车辆调度问题和封闭式车辆调度问题。开放式车辆调度问题指的是车辆完毕配送任务后能够不返回其原来发出车场；封闭式车辆调度问题指的是车辆完毕配送任务后必须返回其原来发出车场。本课题是针对开放式车辆调度问题进行的研究。(7)按优化目的数分：分为单目的问题和多目的问题。单目的问题指的是仅考虑一种配送目的；而多目的问题指的是同时考虑多个配送目的。车辆调度的有关求解算法用于解决物流配送车辆调度问题的算法分为：精确算法和启发式算法两大类，精确算法普通用于解决小规模的VRP问题，车辆调度问题应用最为广泛的算法是启发式算法，启发式算法并不追求问题的最优解，而是强调问题解的满意性。因此，启发式算法对于大规模的车辆调度问题能在较短的时间内获得较满意的次优解，并且这些算法的通用性也很强。常见的启发式算法有以下几个：(1)C-WSavings算法C-WSavings算法采用了几何中三角形的边定理，即三角形的两边之和不不大于第三边。当途径中有这样的两个边时用第三边来替代，以达成节省配送距离的目的。我们能够设节点i和节点j之间的节省量为Sij，这两点和节点o之间的距离为Doi和Doj，则Sij=Doi+Doj-Dij（i≠j,i,j=1,2,…n,），算法首先求出全部Sij，并按非增次序排列。然后从最大的Sij开始，拟定与否存在两条途径，其中一条从弧(0,j)开始，而另一条以(i,o)结束。如果存在，则去掉弧(0,j)、(i,o)，引入弧(j,i)合并这两条途径。重复上述过程直到没有途径能够合并。(2)Sweep算法Sweep算法是一种“先分组后路线”的算法。所谓的分组就是：首先计算出要访问的顾客的位置的极坐标，并把这些极坐标按角度大小排序，然后在未分派到任何途径中的顾客中从角度最小的顾客开始，依次将顾客归并到对应的途径中，直到车辆的能力约束满足为止，再重新选择新的车辆，重复上述过程，直到全部的顾客都分派完毕。最后运用TSP的优化算法对各子路经进行优化。(3)ClusterandRoute算法普通有两种办法：先聚类后排序办法(CFRS)和先排序后聚类办法(RFCS)。CFRS最早由等提出，它是先用启发式办法将节点分成若干途径，然后对途径中的点进行排序。RFCS由Besley提出，它先对全部节点进行TSP排序，然后将大的途径分成若干个小途径。(4)遗传算法GA遗传算法使用群体搜索技术，借用适者生存规律进行局部搜索改善，它通过对现在群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，每一次进化则对应解的一次迭代，并逐步使群体进化到包含或靠近最优解的状体。当迭代次数达成最大次数限制或群体中的个体无明显差别时，迭代终止。最先将GA应用于求解车辆调度问题。(5)禁忌搜索算法TSTS的思想由Glover最早提出，它通过对避开某些局部最优解，达成接纳一部分较差解，从而跳出局部搜索的目的。TS是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类思维过程的一种模拟。禁忌搜索算法通过运用一种禁忌表统计已经达成过的局部最优点，并在背面的搜索中，根据某种限制循环的规则和禁忌表中统计的信息在现在搜索邻域中取一种适宜的解。(6)模拟退火算法SA其思想最早有Metropolis1953年提出，Osman于1993年用之解决VRP。模拟退火算法用固体退火模拟组合优化问题，将内能模拟为目的函数值，温度演化成控制参数。由初始解和控制参数初值开始，对现在解重复“产生新解→计算目的函数差→接受或舍弃”的迭代，并逐步衰减控制参数值，算法终止时的现在解即为所得近似最优解。(7)蚁群优化算法ACO蚁群算法模拟了蚁群搜索食物的行为。蚂蚁在寻找食物时，会在它所通过的途径排放一种外激素(pheromone,在算法中称为信息素)作为标记，排放的量则根据途径长度和食物的等级决定。这些外激素能够指导蚂蚁的运动方向，并使蚁群朝着外激素强度高的方向移动。在用蚁群算法解决车辆调度问题时，可根据优化的目的函数个数，构造多组互相协作的人工蚁群，使各组分别优化其中的一种目的函数，并以共用解的方式建立协作关系。在以上求解VRP的算法中，有的算法运用全局信息进行整体搜索适合构解，如GA等；尚有的运用局部信息，适合改善解，如SA、TS等。每种办法都各有所长与局限性，普通来说，根据具体的求解问题，采用两种或两种以上的混合办法，能够得到更加好的解。小结本章从车辆调度基本理论的角度，首先介绍了车辆调度涉及到的基本概念，涉及了问题的描述和构成要素。另首先对车辆调度问题的分类进行的描述，列举了某些有关解决车辆调度问题的算法。第三章遗传算法概述背景介绍遗传算法(GeneticAA)是由美国Michigan大学专家和他的学生发展建立的一类借鉴生物界的进化规律—适者生存、优胜劣汰遗传机制演化而来的概率搜索算法。GA算法是近几年发展起来的一种崭新的全局优化算法，遗传算法作为一种非数值并行算法，其思想来源于生物遗传学适者生存的自然规律，通过自然选择、遗传、变异等作用机制，实现各个体适应性的提高。它是多学科结合与渗入的产物，已经发展成一种自组织、自适应的综合技术，广泛应用在计算机科学、工程技术和社会科学等领域。GA算法是通过对自然进化现象的模拟，运用简朴的编码技术和进化机制来解决复杂的优化问题。特别是由于它不受搜索空间的限制性假设的约束，不必规定诸如持续性、导数存在等假设，以及其固有的并行性。它是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法，其通过给解向量编码，形成初始种群，然后用变异、交叉、重组、自然选择等算子，进行并行迭代求得优化解。由于遗传算法含有不依赖于问题模型采用随机运算，对搜索空间无特殊规定、无需求导，含有全局最优性求解能力、隐含并行性、收敛速度快以及能高效率地解决不同非线性问题的鲁棒性的特点。因此近年来有很快的发展，在组合优化、自适应控制、机器学习等许多领域获得应用，并在电气自动化、计算机和通信以及人工智能的许多领域获得了不凡的成就，特别适合求解NP-hard问题。遗传算法的基本概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化办法，因而在这个算法中要用到多个进化和遗传学的概念。这些概念以下：(1)串(String)它是个体(Indlvidual)的形式，对应于遗传学中的染色体(Chromosome)。(2)群体(Population)个体的集合称为群体，个体是群体的元素。(3)群体大小(Populationsize)在群体中个体的数量称为群体的大小。(4)基因(Gene)基因是串中的元素，基因用于表达个体的特性。例如有一种串S=1010，则其中的1，0，1，0这4个元素分别称为基因。(5)基因位置(GenePosition)一种基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左边向右计算，如在串S=1011中，0基因位置是2。基因位置对应于遗传学中的地点(Locus)。(6)基因特性值(GeneFeature)在用串表达整数时，基因的特性值与二进制数的权一致，如在串S=1011中，第三基因位值上的1，它的基因特性值为2；第一基因位值上的1，它的基因特性值为8。(7)串构造空间S在串中，基因任意组合构成的串的集合称为串构造空间。基因操作是在构造空间中进行的。(8)适应度(Fitness)表达某一种体对于环境的适应程度。为了体现染色体的适应能力，引入了对问题中的每一种染色体都能进行度量的函数—适应度函数，用于计算个体在群体中被使用的概率。(9)选择(Selection)就是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代，故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度来决定其繁殖量的，故有时也称为非均匀再生(Differentia1Reproduction)。(10)交叉(Crossover)就是在选中用于繁殖下一代的个体中，对两个不同的个体随机选用一种子串进行交换，从而产生新的个体。(11)变异(Mutation)就是在选中的个体中，随机选择两点，将两点间的子串按一定的规则进行变异。遗传算法的工作流程遗传算法在整个进化过程中的遗传操作是随机的，但它所呈现出的特性并不是完全随机搜索，它能有效地运用历史信息来推测下一代盼望性能有所提高的寻优点集。这样一代代地不停进化，最后收敛到一种最适应环境的个体上，求得问题的最优解。遗传算法所涉及的五大要素为：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。其流程框图如图所示。图遗传算法流程图从图能够看出，遗传算法的运行为一种典型的迭代过程，其必须完毕的工作内容和基本环节以下：(1)选择编码方略，将解空间中的解数据表达成遗传空间的基因型串构造数据，这些串构造数据的不同组合便构成了不同的编码。(2)定义适应度函数f(x)。(3)拟定遗传方略，涉及选择群体大小n，选择、交叉、变异办法，以及拟定交叉概率pc、变异概率pm等遗传参数。(4)随机初始化生成群体P。(5)计算群体中个体位串解码后的适应度f(x)。(6)按照遗传方略，运用选择、交叉和变异算子作用于群体，形成下一代群体。(7)判断群体性能与否满足某一指标，或者己完毕预定迭代次数，不满足则返回环节(6)，或者修改遗传方略再返回环节(6)。在遗传算法的应用过程中，人们往往结合问题的特性和领域知识对基本遗传算法进行多个变化，形成了多个各样具体的遗传算法，从而使得遗传算法含有求解不同类型优化问题的能力。遗传算法的构成遗传算法重要由六个部分构成：编码方式、初始群体产生的办法、评价函数、遗传操作、算法终止条件、算法参数的设立。要运用遗传算法成功的解决物流配送车辆调度问题，就需要对这六个环节进行设计。编码方式在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操作，而是对表达可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种遗传操作来达成优化的目的，这是遗传算法的特点之一。遗传算法通过这种对个体编码的操作，不停搜索出适应度较高的个体，并在群体中逐步增加其数量，最后谋求出问题的最优解或近似最优解。在遗传算法中如何描述问题的可行解，即把一种问题的可行解从其解空间转换到遗传算法所能解决的搜索空间的转换办法就成为编码。编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一种核心环节。编码办法除了决定了个体的染色体排列形式之外，它还决定了个体从搜索空间的基因型变换到解空间的体现型时的解码办法，编码办法也影响到交叉算子、变异算子等遗传算子的运算办法。由此可见，编码办法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。一种好的编码办法，有可能会使得交叉运算、变异运算等遗传操作能够简朴的实现和执行。而一种差的编码办法，却有可能会使得交叉运算、变异运算等遗传操作难以实现，也有可能会产生诸多在可行解集合内无对应可行解的个体，这些个体经解码解决后所示的解称为无效解。即使有时产生某些无效解并不完全都是有害的，但大部分状况下它却是影响遗传算法运行效率的重要因素之一。针对一种具体应用问题，如何设计一种完美的编码方案始终是遗传算法的应用难点之一，也是遗传算法的一种重要研究方向。能够说现在还没有一套既严密又完整的指导理论及评价准则能够协助我们设计编码方案。作为参考，DeJong曾提出了两条操作性较强的使用编码原则：编码原则一：应使用能易于产生与所求问题有关的且含有低阶、短定义长度模式的编码方案。编码原则二：应使用能使问题得到自然表达或描述的含有最小编码字符集的编码方案。第一种编码原则中，模式是指含有某些基因相似性的个体的集合，而含有短定义长度、低阶且适应度较高的模式称为构造优良个体的积木块或基因块，这里能够把该编码原则理解成应使用易于生成适应度较高的个体的编码方案。第二个编码原则阐明了我们为什么偏爱于使用二进制编码办法的因素，由于它满足这条编码原则的思想规定。事实上，理论分析表明，与其它编码字符集相比，二进制编码方案能包含最大的模式数，从而使得遗传算法的拟定规模的群体中能够解决最多的模式。由于遗产算法应用的广泛性，迄今为止人们己经提出了许多个不同的编码办法。总的来说，惯用的编码办法可分为三大类：二进制编码办法、实数编码办法、有序串编码办法。二进制编码办法是遗传算法中最惯用的一种编码办法，它使用的编码符号集是由二进制符号0和1所构成的二值符号集{0，1}，它所构成的个体基因型是一种二进制编码符号串。在二进制编码方式的遗传算法中，遗传操作是作用在编码空间上的，操作后的二进制串通过解码转换到解空间，在这里进行评定选择(如图3-2所示)。图编码解码操作使用二进制编码办法，在求解高维优化问题时，二进制串会很长，因而算法的搜索效率很低。为了克服二进制编码办法的缺点，对于变量是实向量的状况，能够直接采用实数编码办法。实数编码表达比较自然，较易引入有关领域知识，因此，实数编码还能够使遗传算法更靠近问题空间，避免了编码和解码的过程，其使用将越来越广泛。对诸多组合优化问题，目的函数的值不仅与表达解的字符串中各字符的值有关，并且与其所在字符串的位置有关，这样的问题称为有序问题，用有序串编码办法表达。这类编码办法较多地用在组合优化问题中，如二次分派问(QuadraticAssignmentproblem)，旅行商问题(TravelingSalesmanProblem)我们惯用的是有序串的编码方式。基于遗传算法的以上特点，在本文用遗产算法求解物流配送车辆调度问题时，我们采用有序串编码方式的染色体设计。初始化过程有诸多个，在研究遗传算法时，经常随机产生初始群体，这样做的好处是产生方式不依赖于问题，也就是对于任何问题，我们都能够采用这种方式来生成初始群体，由于本文是对某个特定的非线性规划问题求解，因此我们采用人机交互方式来初始化群体，这样结合人类智慧使算法优化收敛速度更快。适应度函数在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于其生存环境的适应度程度。对生存环境适应程度较高的物种将有更多的繁殖机会；而对生存环境适应程度较低的物种，其繁殖机会就相对较少。与此相似，在遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能达成或靠近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大，而适应度较低的个体遗传到下一代的概率就相对小某些。度量个体适应度的函数就称为适应度函数（FitnessFunction）。遗传算法的一种特点是它仅使用所求问题的目的函数值就能够得到下一步的有关搜索信息。而对目的函数值的使用是通过评价个体的适应度来体现的。评价个体适应度的普通过程是：(1)对个体编码串进行解码解决后，可达成个体的体现型。(2)由个体的体现型可计算出对应个体的目的函数值。(3)根据最优化问题的类型，由目的函数值按一定的转换规则求出个体的适应度。遗传算法中，群体的进化过程就是以群体中各个个体的适应度为根据，通过一种重复迭代过程，不停地谋求出适应度较大的个体，最后就能够得到问题的最优解或者近似最优解。对于本课题的多车场多目的开放式车辆调度模型优化问题，采用函数值来评价解的好坏，这种办法是最直接，也是最方便的办法，取函数值最小的解为最优解。选择方略遗传算法中的选择方略就是用来拟定如何从父代群体中按某种办法选用哪些个体遗传到下一代群体中的一种遗传运算，选择提供了遗传算法的驱动力。如果驱动力过大，遗传搜索将过早地终止，而如果驱动力太小，进化过程将变得难以接受。相对而言，较小的驱动力普通能使群体保持足够的多样性，从而增大了算法收敛到全局最优的概率。选择操作是建立在对个体的适应度进行评价的基础之上的，选择操作的重要目的是为了避免基因缺失、提高全局收敛性和计算效率。下面是遗传算法中较惯用到的几个选择方略。(1)繁殖池(BreedingPool)选择繁殖池选择首先根据现在群体中个体的适应值，按下式计算其相对适应值：其fi是群体中第i个组员的适应值，N是群体规模。则每个个体的繁殖量为：此处Round(x)表达与x距离最小的整数。计算出群体中每个个体的繁殖量，即可将它们分别复制N个以生成一种临时群体，即繁殖池(Breedingpool)再通过在繁殖池中随机地抽取成对个体进行交配，所产生的后裔将取代现在群体形成下一种群体。显然，个体复制到繁殖池的数目越大，则它被选到进行交配的机会也就越多，而对于Ni=0的个体，它们将被裁减出整个演化过程。在实现算法时需要注意的是，繁殖池中个体的数目不一定正好等于N。(2)轮盘赌选择(RouletteWheelSelection)轮盘赌选择是由Holland提出的，是最出名的选择方式之一，其基本原理是根据每个染色体适应值的比例来拟定该个体的选择概率或生存概率。选择的过程就是旋转轮盘若干次（次数等于种群规模），每次为新种群选出一种个体。轮盘赌选择方略在遗传算法中使用的最多，它的具体选择过程为：先计算个体的适应值Pi，然后根据选择概率把轮盘分成N份，其中第i扇形的中心角为2πPi。在进行选择时，先转动轮盘，若某参考点落入到第i个扇形内，则选择个体i。可见，这种选择方式非常类似轮盘赌中的转盘，小扇区的面积越大，骰子落入其中的概率也越大，即个体的适应值越大，它被选择到的机会也越大。从而，其基因构造被遗传到下一代的可能性也越大。(3)锦标赛（Toumament）选择锦标赛选择也是一种基于个体适应度之间大小关系的选择办法。在选择时，每次进行适应度大小比较的个体数目称为竞赛规模，普通状况下，竞赛规模K的取值为2。具体操作过程以下：首先，从群体中随机选用K个个体进行适应度大小的比较，将其中适应度最高的个体作为生成下一代的父体。另首先，将上述过程重复M次，就可得到下一代群体中的M个个体。显然，这种选择方式也使得适应度好的个体含有较大的“生存”机会。同时，由于它只使用适应度的相对值作为选择的原则，而无个体适应度的算术运算。从而它能避免超级个体的影响，在一定程度上，避免发生过早收敛现象和停滞现象。杂交方略交叉运算是指对两个互相配对的染色体按某种方式互相交换其部分基因，从而形成两个新的个体。它在遗传算法中起着核心作用，是产生新个体的重要办法。首先它使原来群体中优良个体的特性能够在一定程度上被遗传和继承，另首先它使算法能够搜索新的基因空间，从而使新群体中的个体含有多样性。交叉或基因重组是遗传算法获取新的优良个体的最重要的手段。经常采用的交叉算子有下列几个：(1)部分映射交叉(PartiallyMappedCrossover，简称PMX)这种算子在构造后裔时通过从一种父体中选用一段途径，并尽量多的保存另一种父体中都市的次序和位置。选择一种途径时，首先随机选用两切割点作为交换操作的边界。例如两父体(两切割点用“|”标记)P1=(123|4567|89)P2=(254|1876|39)产生后裔的过程以下：首先交换两切割点之间的对应段(符号“x”表达现在未知值)，得到Q1=(xxx|1876|xx)Q2=(xxx|4567|xx)这一交换同时定义了一系列的映射：然后从各自的父体中填入无冲突的都市，得到：Q1=(x23|1876|x9)Q2=(2xx|4567|39)最后，后裔Q1中的第一种“x”根据映射14被4替代。类似地，Q1中的第二个“x”用5替代，Q2中的两个“x”分别用8和1替代。因此生成的后裔为Q1=(423|1876|59)Q2=(281|4567|39)(2)次序交叉(OrderCrossover，简称OX)这一算子在构造后裔时通过从一种父体中选用一段途径，并保持另一种父体中都市的相对次序。例如两父体(两切割点用“|”标记)P1=(123|4567|89)P2=(452|1876|93)产生后裔的过程以下：首先，两切割点之间的都市段被复制到后裔中，得到：Q1=(xxx|1876|xx)Q2=(xxx|4567|xx)接着从一种父体的第二个切割点开始，来自另一种父体的都市依同样的次序被复制，省略已经出现的都市。当达成串尾时，则从串首继续。那么，第二个父体从第二个切割点开始的都市序列为：9-3-4-5-2-1-8-7-6移去4，5，6和7这四个在第一种后裔中已出现的都市，得到：9-3-2-1-8依本次序从第二个切割点开始填入第一种后裔得到Q1=(218|4567|93)类似地，可得到另一种后裔Q2=(345|1876|92)OX算子开发了途径表达的一种特性，即重要的是都市间的相对次序，而不是他们的特定位置。也就是，两条途径9-3-4-5-2-18-7-6和4-5-2-事实上是相似的。(3)循环交叉(CycleCrossover，简称CX)这种算子在构造后裔时，每个都市及其所处的位置都来自于某一种父体。循环交叉的过程以下：两父体P1=(123456789)P2=(452687193)产生后裔时，先从第一种父体中取第一种都市作为第一种后裔的起始点，得到Q1=(lxxxxxxxx)。由于后裔中的每一种都市必须取自于某个父体且保持同样位置，因此在起始点我们别无选择。下一种考虑的都市应当是4，由于它是P2中位于所选都市1“下方”的都市，在P1中这个都市位于位置4。因此Q1=(lxx4xxxxx)接着是都市6，由于它是P2中位于所选都市4“下方”的都市。因此Q1=(lxx4x6xxx)按照这样的规则，在第一种后裔中应涉及的下个都市是7。但是注意，选择都市7蒙牛乳业股份有限公司自动化立体仓库出库端车辆调度问题摘要：自动化立体仓库出库端车辆调度方略的设计是物流配送车辆调度中的一种核心问题，好的调度方略能够大大缩短出库端的配货时间。为此本文引入动态优先级理论，并运用该理论对大型AS/RS出库口车辆调度问题进行了进一步研究与分析，提出了基于动态优先级的AS/RS出库端车辆调度方略，并开发了对应的AS/RS出库口发货资源监控系统，即AS/RS出库口车辆调度系统，优化了AS/RS出库端车辆调度方略，大大提高了物流配送当中的配货效率。本文建立的多目的组合优化模型以及设计的遗传算法求解方案，能够有效的缩减物流配送中的送货时间；设计的AS/RS出库端车辆调度优化方略及开发的AS/RS出库端车辆调度系统，能够有效缩减车辆在出库端的配货时间。本文对以上两种物流配送中的车辆调度问题进行研究，大大提高了物流配送效率、减少了物流配送成本。核心词：物流配送；车辆调度；多目的组合优化；一、公司背景蒙牛乳业，是“蒙牛乳业集团”的简称。其总部，设在呼和浩特市和林格尔盛乐经济园区。前后四期工程占地面积55万平方米。蒙牛是一家总部位于中华人民共和国内蒙古的乳制品生产公司，蒙牛是中国大陆生产牛奶、酸奶和乳制品的领头公司之一，1999年成立，至时已成为中国奶制品营业额第二大的公司，其中液态奶和冰淇淋的产量都居全中国第一。蒙牛重要业务是制造液体奶、冰激凌和其它乳制品。1999年8月，内蒙古蒙牛乳业（集团）股份有限公司（简称蒙牛乳业集团）成立，总部设在中国乳都核心区――内蒙古和林格尔经济开发区，拥有总资产100多亿元，职工近3万人，乳制品年生产能力达600万吨。到现在为止，涉及和林基地在内，蒙牛乳业集团已经在全国16个省区市建立生产基地20多个，拥有液态奶、酸奶、冰淇淋、奶品、奶酪五大系列400多个品项，产品以其优良的品质覆盖国内市场，并出口到美国、加拿大、蒙古、东南亚及港澳等多个国家和地区。二、AS/RS出库端车辆调度问题的研究问题的提出自动化立体仓库（AutomaticStorage＆RetrievalSystem）：是指能自动储存和输出货品的仓库，它采用多层货架储存单元货品，用自动化货品搬运设备进行货品的入库和出库。它普通由自动控制与管理系统、货架、巷道式堆垛机、出入库输送机等构成，能按指令自动完毕货品的搬运、存取作业，并能对库存货品进行自动管理。由于自动化立体仓库含有很高的空间运用率、很强的入出库能力、采用计算机进行控制管理便于公司实施当代化管理等特点，已成为公司物流和生产管理不可缺少的仓储技术，自动化立体仓库作为物流中心的重要构成部分，越来越受到公司的重视。现阶段对物流配送车辆调度问题的研究诸多，但大多是对车辆调度线路选择问题的研究，对自动化立体仓库出库端车辆调度问题的研究较少。在物流配送中整个配送时间应涉及两部分：出库端的配货时间和装货完毕后的送货时间，对车辆调度线路选择问题的研究能够有效的缩减物流配送中的送货时间，但通过对出库端车辆调度问题的研究能够有效缩减车辆在出库端的配货时间，对减少物流配送的时间成本有很大的作用。所谓自动化立体仓库出库端车辆调度，即在自动化立体仓库出库端按什么样的原则给待装货车辆分派车位的问题。现阶段出库端车辆调度大多采用先来先服务的原则，即对先到的车辆优先分派车位，此原则的采用能够充足体现车辆调度的公平性，但有诸多局限性。首先当给订货数量特大的订单客户的车辆分派车位后，此客户后的全部小订货数量客户的车辆都需要等待很长时间才干被分派车位，减少了系统在一段时间内解决客户订单的能力，并且此调度方略没有考虑影响出库产品整体销售模式的因素。因此本文对自动化立体仓库出库口车辆调度问题的研究含有重要的实际意义。问题及有关因素描述本文是以内蒙古蒙牛乳业股份有限公司自动化立体仓库出库端车辆调度问题为背景进行研究的。一种大型的立体仓库有多个出库口，每一种出库口对应一种车位，所谓车位就是车辆装货时在出货口的位置，分为常规固定车位和双向固定车位两种类型。常规固定车位用于分派后开门的车辆，双向固定车位用于分派侧开门或两端开门的车辆。其构造如图所示。文章所要解决的问题是如何调度不停到来的客户车辆为其分派车位，使其能在最短的时间内完毕装货任务。车辆从进厂到装完货离开的这段时间我们称为装载时间，影响装载时间的因素诸多，这里我们假设自动化立体仓库有足够大的出库能力，即只要出库口能够装完一盘货品，自动化立体仓库有足够的能力立刻准备好另一盘货。另外假设每个车上的装卸工的装卸速率都是均等的，这样我们要研究的问题只与对不同顾客的车辆的调度次序有关。图AS/RS出库端销售派车单销售派车单是由各事业部的运管部根据销售订单下发，所涉及的重要信息有：出库单号、仓库、数量、品名规格、订单号、订单类型、车辆类型。其它信息涉及：定货单位、收货单位、收货单位地址、联系人、联系电话、运输方式、计划达成日期等。司机达成蒙牛六期AS/RS出库端后应先到储运部登记，保管员按司机达成次序给司机带来的销售派车单据分派优先级，分派原则是先来先分派。优先级高的销售派车单对应的车辆被优先调度，被优先下发出库任务。具体流程图以下所示：图原车辆调度流程图订单的优先级表达为了更加好的调度待装货车辆我们引入订单动态优先级的概念，根据装货车辆达成立体库时所持销售派车单的有关信息拟定销售派车单的优先级，以此拟定车辆调度的优先级并为车辆分派车位。一种完整的销售派车单重要信息以下：车辆类型（Vehicle-Type）：分为集装箱（两个侧开门或两端开门的车）和常规车（有一种后门的车）两类。其中常规车分派在常规固定车位，集装箱分派在双向固定车位。订单类型（Order-Type）：涉及外部调拨订单、内部调拨订单和销售订单。外部调拨订单是集团内部不同事业部之间调拨产品时所用到的单据；内部调拨订单是一种事业部的内部各厂之间调拨产品时所用到的单据；销售订单是客户向我司订购产品时所用到的单据，三者都是立体库出库口进行配货的凭证，重要信息有：单据类型、仓库号、品名规格、数量等。在本文的研究背景中外部调拨订单和销售订单的优先级同等看待。内部调拨优先级高于前两者。运输方式（Transport-Type）：选择何种运输方式，能够在