车辆调度及优化方案

.word.zl-

.word.zl-

中文摘要

物流配送车辆调度问题是指：在给定运输任务的条件下，如何派车、组织循

环运输，使空驶里程最少，运输本钱最低。目前我国大多数的物流企业运输资源

分配不均、配送路线安排不合理、运力资源浪费严重，而缺乏完善的物流配送车

辆调度优化方案是造成此现象的重要因素之一。因此对物流配送车辆调度问题的

研究具有重要的现实意义。

目前对单车场、封闭式物流配送车辆调度问题研究较多，而对多车场开放式

物流配送车辆调度问题研究较少，但是多车场开放式物流配送车辆调度问题有很

强的应用背景。本文针对此问题，建立了一种灵活的多目标组合优化模型，设计

了适合多车场开放式车辆路径问题的通用染色体编码方案，并对遗传算法中的穿

插变异操作做了详细说明。此模型可以方便的增减优化目标值，并通过测试用例

验证了本文设计的优化模型和遗传算法在解决多车场多目标开放式物流配送车

辆调度问题中的可行性。

自动化立体仓库出库端车辆调度策略的设计是物流配送车辆调度中的一个

关键问题，好的调度策略可以大大缩短出库端的配货时间。为此本文引入动态优

先级理论，并利用该理论对大型AS/RS出库口车辆调度问题进展了深入研究与

分析，提出了基于动态优先级的AS/RS出库端车辆调度策略，并开发了相应的

AS/RS出库口发货资源监控系统，即AS/RS出库口车辆调度系统，优化了

AS/RS出库端车辆调度策略，大大提高了物流配送当中的配货效率。

本文建立的多目标组合优化模型以及设计的遗传算法求解方案，可以有效的

缩减物流配送中的送货时间；设计的AS/RS出库端车辆调度优化策略及开发的

AS/RS出库端车辆调度系统，可以有效缩减车辆在出库端的配货时间。本文对以

上两种物流配送中的车辆调度问题进展研究，大大提高了物流配送效率、减少了

物流配送本钱。

关键词：物流配送；车辆调度；多目标组合优化；遗传算法

第一章绪论

课题背景

物流(Logistics)：指在适宜时间，将适宜的物品以适当的数量准确地送到顾客

手中，它是供给链中最重要的组成局部。一般意义上是指在生产和生活中所涉及

的各种物质实体由供给方向需求方的物理性转移过程。这一概念将物流定义在有

用的物、供方、需方等几个根本因素之上。也就是说，我们通常所指的物流是指

人们在生产和生活中发生的有意义的物流行为。整个物流过程是一个物理过程，

只改变时间和空间的状态，不改变其使用价值。其中，时间状态的改变称之为仓

储、流通加工等活动，空间状态的改变称之为运输、搬倒等活动。

物流配送是物流系统中的一个重要环节，它是指按客户的订货要求，在物流

中心进展分货、配工作，并将配好的货物及时送交收货人的物流活动。配送本钱

直接关系到物流企业和部门的效益，目前我国的大多数的物流企业运输资源分配

不均、配送路线安排不合理、运力资源浪费严重,根据中国仓储协会对146个企

业的调查显示，用于运输的费用占整个物流费用的比例分别为：在生产企业原料

物流中占58%，在生产企业成品物流中占73%，在商业物流中占52%。所以物流

配送车辆调度方案的合理优化，对于整个物流运输速度、本钱、效益的影响至关

重要。

运输是指“物〞的长距离的移动，任何跨越空间的物质实体的流动，都可称

为运输。运输是物流的中心环节之一，被称为国民经济的动脉和现代产业的支柱，

从社会经济的角度讲，运输功能的发挥，缩小了物质交流的空间，扩大了社会经

济活动的围并实现在此围价值的平均化、合理化。在社会经济的开展中，运输的

重要性己经被人们所确认，成为国民经济的命脉。

从物流系统的观点来看，运输作业的关键因素包括运输本钱和运输速度两个

方面。运输本钱：是指为两个地理位置的运输所支付的款项，以及管理和维持转

移中存货的有关费用，应采用能把系统总本钱降低到最低限度的运输方式。运输

速度：是指为完成特定的运输作业所需花费的时间。运输速度和本钱的关系，主

要表现在以下两个方面：首先，运输商提供的效劳越快速，实际需要收取的费用

也就越高。其次，运输效劳越快，转移中的存货就越少，可利用的运输间隔时间

越短。因此在选择最合理的运输方式时，至关重要的问题就是如何平衡其效劳的

速度和本钱。运输主要目的就是要以最低的时间、财务和环境资源本钱，将产品

从原产地转移到规定地点。同时，产品转移所采用的方式必须能满足顾客有关交

付履行和装运信息的可得性等方面的要求。所以在物流系统中，必须准确地维持

运输本钱和效劳质量之间的平衡。低本钱运输和高质量效劳是令人满意的。

物流配送车辆调度就是研究怎样合理运输的问题，所谓合理运输就是在实现

物资产品实体从物流中心至消费地转移的过程中，充分有效地运用各种运输工具

的运输能力，以最少的人、财、物消耗，及时、迅速、按质、按量和平安的完成

运输任务。其标志是：运输距离最短、运输环节最少、运输时间最短和运输费用

最省。据统计运输费约占整个物流费用的40%，占销售收入的2.88%。物流配送

车辆调度问题就是指在给定运输任务的条件下，如何派车、组织循环运输，使空

驶里程最少，运输本钱最低。车辆调度是物流管理最重要的局部，正确合理的调

度可以有效减少车辆的空驶率，实现合理路径运输，从而有效减少运输本钱，节

约运输时间，提高经济效益。

课题研究的意义

物流产业的开展，将从整体上改变经济运行的方式，提高经济运行效率，对

增强国际竞争力将起到巨大的推动作用。我国国民经济的开展呼唤物流的进一步

开展，对物流的开展要求如下：

降低流通本钱在GDP中的比重：在我国目前工业企业生产中，直接劳

动本钱占总本钱的比重不到10％，而物流费用占商品总本钱的比重，从账面反

映约为40％，全社会物流费用支出约占GDP的20％，而其他兴旺国家一般在

10%左右。这反映了我国物流系统落后，流通本钱太高，反映了我国国民经济运

行质量不高。通过开展现代物流业来促进物流合理化，降低流通本钱在GDP中

的比重，无疑将成为我国新的经济增长点。“十五〞期间，如果我国物流费用降

低到占GDP的15％，每年将为社会直接节约2400亿元的物流本钱。

减少企业流动资金占用：我国工业企业和流通企业由于物流根底设施、

技术和管理的落后，原材料、半成品、成品积压严重，大量流动资金被占用，周

转速度很慢，物流本钱过高。据统，1992年，国有独资、控股工业企业流动资

金占用1万多亿元，周转速度为1.62次/年；1999年，国有独资、控股工业企

业流动资金达31000亿元，周转速度仅1.2次/每年，与兴旺国家相比非常落后。

如果工业企业把物流职能别离出来交给第三方物流企业，通过其先进、科学的专

业化效劳，就可以减少流动资金占用，提高核心竞争能力，实现从粗放式经营向

集约式经营转变。

电子商务的开展需要物流做根底：电子商务是流通领域的一场革命，它

把3商品买卖虚拟成一个大的市场，使客户在任何地点、任何时间都可以购置商

品。但是，电子商务需要将网上订的货物及时送到可能在任何地方的客户手里，

这就给物流系统带来很大的挑战。实际上，物流已经成为电子商务开展的瓶颈，

需要建立具有响应性、灵活性和可视化的现代物流系统，需要第三方物流企业的

效劳。世界500强中相当多的企业都是通过第三方物流来解决它的供给链与销

售问题的，很多跨国公司在欧洲、亚洲、美洲等地分别有不同的第三方物流企业

为他效劳。

现代物流产业的开展，将减少由于低水平、条块分割的物流方式造成的

巨大物耗：在传统的物流框架下，一件商品从生产出来到最终的消费环节，至少

要被搬倒、装运十几次。实行社会化的多式联运、一单到底，物流过程中的物耗

至少可以减少几倍。我国汽车空驶率达37％左右，意味着全国每年有150多万

辆载重汽车无活可干，这种潜在浪费至少也在数千亿元。按现代物流要求，合理

的流程设计可使空驶率降低到5％以下。

在现代物流集约化、一体化的开展中，配送是直接与消费者相连的重要环节，

其核心局部为配送车辆的集约、货物配装及送货过程，而配送车辆优化调度是物

流系统优化、物流科学化的关键一环，是货物从配送中心送达收货人的过程。配

送首要解决的是车辆的调度问题，几十年来这一直是一个研究的热点，在满足和

完成各任务的前提下，正确合理的安排行车路线、提高配送车辆的利用率就可以

有效的节省时间从而减少运输本钱。另外对出库口车辆调度问题的研究，将有效

减少货物装配的时间。所以本文对物流配送车辆调度的研究具有重要意义。

国外研究现状

车辆调度问题最早是由Dantzig和Ramsert在上个世纪50年代末期提出，该

问题一般称之为VehicleRoutingProblem(VRP)或者VehicleScheduling

Problem(VSP)现在我们将车辆调度问题一律简称为

VRP

VRP提出后就很快

引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等

学科专家与运输方案制定者和管理者的极大重视，成为运筹学与组合优化领域的

前沿与研究热点问题。各学科的专家对该问题进展了大量的理论研究及实验分

析，取得了很大进展。

国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1962

年，Balinski等人首先提出VRP的集分割，直接考虑可行解集合，在此根底上进展优化，建立了最简单的VRP模型；1964年，Clarke和Wright提出了一种启发

式节约法来建立车队配送路线；1968年，Rao等人在VRP集分割的根底上引入了列生成方法进展求解，这种算法本质上是最短路径算法，同时结合了分枝定界

算法；1971年，Eilon等人提出将动态规划法用于固定车辆数的VRP,通过递归

方法求解；1981年，针对带能力约束、时间窗以及无停留时间的VRP，Fisher

提出了三下标车辆流方程；Thangiah于1991和Joe于l993分别用遗传算法求解

VRP,但是都存在“早熟收敛〃的问题；2001年，Tan,Lee,Du结合遗传算法、tabu树搜索算法的优点，形成知识库，用人工智能的方法来求解；2002年，Taranrilis,Kiranondis使用空间决策支持系统来解决车辆路径问题。

在国,有关车辆调度问题的研究是在20世纪90年代以后才逐渐兴起的，比国

外相对落后。国研究对象主要是旅行商问题(TravelingSalesmanProblem,简称TSPb中国邮递员问题(ChinesePostmanProblem简称CPP)、有向中国邮递员问题(DirectedChinesePostmanProblem简称DCPP)等，系统性研究还很少见到。西南交通大学的军教授和郭耀煌教授对车辆优化调度的根底理论及各类问题进展

了系统的研究；大为等以TSP的最近距离启发式为根底，通过设置评价函数来

处理时间窗约束，求解了简单的VRP。另外在利用现代优化算法（如:遗传算法、

神经网络方法、模拟退火等）对简单TSP的求解取得了一定成果。蔡延光等应用

模拟退火法针对满载问题进展了求解。总体来说，目前我国对车辆调度问题的理

论研究仍相对薄弱，需要进一步研究。

本文容的安排

本课题的研究以蒙牛乳业股份（集团）的物流配送业务为背景，主要研究两方

面容：首先，对多车场多目标开放式物流配送车辆调度问题做了研究，以此可以

优化对客户的派车问题及最正确车辆路径的选择问题。其次，对AS/RS出库端

车辆调度策略做了研究，以本文建立的策略对出库口的车辆分配车位，可以减少

车辆的配货时间。本文的研究将在最大程度上减少蒙牛集团的运输本钱，给蒙牛

集团带来可观的经济效益。本文研究的具体容如下：

第一章绪论：介绍了本文研究的背景以及研究的目的与意义，并对国外对车

辆调度问题的研究现状作了简单介绍。

第二章车辆调度问题概述：首先对物流配送车辆调度问题进展了描述，其次

介绍了车辆调度问题的构成要素和车辆调度问题的分类，最后列举了车辆调度的

相关求解算法。

第三章遗传算法概述：首先对GA的背景作了简单的介绍，接着对GA算法

的根本概念、工作流程和算法的组成做了详细描述。

第四章用遗传算法解决多车场多目标开放式车辆调度问题：首先介绍了两种

求解多车场车辆调度的方法，然后对多车场多目标开放式车辆调度问题的研究背

景进展了描述，在此根底上确定了多车场多目标开放式车辆调度问题的数学模

型，并详细描述了用遗传算法对多车场多目标开放式车辆调度问题的求解过程，

最后用实例证明了用遗传算法求解此问题的可行性。

第五章对AS/RS出库端车辆调度策略做了研究，提出了基于动态优先级的

AS/RS出库端车辆调度策略，并开发了相应的AS/RS出库端发货资源监控系统，

即AS/RS出库口车辆调度系统，以此策略对出库口的车辆分配车位,可以减少车

辆的配货时间。

第六章总结与展望：归纳与总结了本文的创新之处，并提出进一步研究车辆

调度问题的方向。

第二章车辆调度问题概述

车辆调度问题的描述

“配送〞一词是日本引进美国物流学时，对英文单词delivery一词的意译，

我国转学于日本，也直接用了“配送〞这个词。配送是物流系统中由运输派生出

的功能，是短距离的运输。具有：①配送距离较短，位于物流系统的最末端，处

于支线运输、二次运输和末端运输的位置。②在配送中，也包含着其他的物流功

能，是多种功能的组合。③配送是物流系统的缩影，也可以说是一个小围的物流

系统。从物流来讲，配送几乎包括了所有物流的要素，车辆调度就是其中一个最

重要且有意义的要素，所以本文研究的是物流配送车辆调度问题。

物流配送车辆调度优化问题最早是由Dentzing和Ramse依1959年第一次提

出的。从此，车辆调度优化问题很快引起运筹学、应用数学、组合数学、图论与

网络分析、物流科学、计算机应用等学科的专家与运输方案制定者的极大重视，

同时也逐渐成为运筹学与组合优化领域的热点研究问题。由于它应用的广泛性和

经济上的重大价值，一直受到国外学者的广泛关注。国外将物流配送车辆优化调

度问题归结为或称之为VehicleRoutingProblem^口VehicleSchedulingProblem本

课题采用的是后者，也就是将车辆调度问题归结为VSP问题：VehicleScheduling

Problem。

物流配送车辆调度问题的一般性定义是：物流配送车辆调度问题是把一系列

的装货点和〔或〕卸货点，有机的组织起来，形成一系列行车线路，使待调度车

辆能够高效、节能且有序地通过这些点。当然，这种组织方式是应该在满足一定

的约束条件〔例如：用户对货物的需求量、一次性发货量、应交发货时间、单个

车场的车辆容量限制、路程约束、时间限制等〕，最终到达缩短里程、减少开支

费用、缩短运输时间、使用车辆数尽量少等优化目标。

物流配送车辆调度问题一般研究的是在配送中心及用户位置均、资源及运输

能力充分、各用户需求量己知的前提下，如何合理、高效、低本钱的解决分配与

运送的问题，也就是说如何将货物从配送中心按照一定的要求发送到假设干个用

户点。配送方案应该包括两个相关的环节：①有哪些用户要被分配到一条回路上，

即有哪些用户的货物应该安排在同一辆车上；②每条配送路线上用户的连接顺

序。物流配送车辆调度的最优解实际上是一个效率最高的运输方案，它应明确的

规定应派出的车辆型号、车辆数以及每辆车的具体行车路线。实施这一配送方案，

即可以满足用户的需求，又可以使总的运输行程最短。

车辆调度问题的构成要素

物流配送车辆调度问题主要包括货物、车辆、配送中心、客户、运输网络、

约束条件、和目标函数等要素。

货物

货物是我国交通运输领域中的一个特有专用概念，交通运输领域将其经营的

对象分为两大类：一类是人，一类是物。“物〞这一类的运输目标统称为货物。

我们这里所说的货物是指物流配送的对象，每批货物都包括品名、包装、重量、

体积、要求送到(或取走)的时间和地点，能否分批配送等属性。

车辆

车辆是“车〞与车的单位“辆〞的总称。所谓车，是指陆地上用轮子转动的

交通工具；所谓辆，来源于古代对车的计量方法。本文所说的车辆是指运载货物

的工具，车辆的主要属性包括：类型、工作时间、配送前的停放位置、载重量以

及配送任务完成后的停放位置等。

配送中心

配送中心是指承受供给者所提供的多品种、小批量的货物，通过存储、保管、

分拣、配货以及流通加工、信息处理等作业后，将按需要者订货要求配齐的货物

送交顾客的组织机构和物流设施。本文所说的配送中心是指从事配送业务的物流

场所或组织，如可以进展货物集中、分拣、配货、送货等的仓库、车站、港口等

固定场所。在物流配送系统中，配送中心可以只有一个，也可以同时具有多个。

配送中心专业性强，和客户有固定的配送关系，一般实行方案配送，需配送的商

品有一定的库存量，一般情况很少超越自己的经营围。配送中心的设施及工艺流

程是根据配送需要专门设计的，所以配送能力很强，配送距离较远，配送的品种

较多，配送数量比拟大。使用配送中心配送覆盖面宽，规模大，因此，必须有一

套配套的大规模实施配送的设施。本文的研究背景就是基于配送中心的物流配送

中车辆调度问题的研究。

客户

客户指的是物流配送的效劳对象，可以是各种零售店，也可以是分仓库，还

可以是别的仓库的外调。也就是说客户是有配送任务的对象的统称。客户的属性

包括需求数量、需求时间、需求次数及目前需求的满足动态等。8

运输网络

本文的运输网络采用了离散数学中对网的介绍，配送中心、客户、停车场等

构成网络的顶点、它们之间的交互运输构成了无向边，具体的运输任务被称为由

有向弧组成的运输的网络。边、弧的属性包括方向、权值和交通流量限制等。在

运输网络中，边或弧具有一定的权值，该值可以表示为距离、时间或费用。边或

弧的权值变化具有以下几种情况：固定不变，不随着时间和车辆的不同而变化；

随时间段或者车辆不同而变化；既随着时间的不同而变化，又随着车辆的不同而

变化。对运输网络中的定点、边或弧的交通流量要求分为以下几种情况：无流量

限制；边、弧限制，即每条边、弧上同时行驶的车辆数有限；顶点限制，即每个

顶点上同时装、卸货的车辆数有限；边、弧、顶点都有限制。

约束条件

物流配送车辆调度问题应满足以下约束条件：能够满足所有客户对货物品

种、规格、数量的要求；能够在客户要求或者承受的时间将货物送到；运输车辆

每天的运行时间、运行历程都要有一定的限制，不能超过预定的时间或者里程；

在物流配送过程中实际装载的货物不能超过车辆的最大载重要求，也就是不能超

载；当然，客户的需求也必须在物流中心现有的运力围，也就是目前有这个能力

去完成待完成的任务。

目标函数

目标函数是指所关心的目标(某一变量)与相关的因素(某些变量)的函数关

系。简单的说，就是你求解后所得出的那个函数。在求解前函数是未知的，按照

你的思路将条件利用起来，去求解未知量的函数关系式，即为目标函数。本课题研究的物流配送车辆调度问题，可以只选用一个目标，也可以同时选用多个目标。

使用概率比拟多的目标函数主要有：

①配送的距离最短，也就是在配送过程中车辆所走的路程最短。在实际的物

流配送中，配送里程直接关系到配送车辆的耗油量、磨损程度以及司机疲劳程度

等因素。因此，在众多的目标函数中选择配送里程最短的目标，在某种程度上可

以直接减少运输本钱。

②配送车辆的载重量与公里数最少，这种方式的目标是将配送距离与车辆的

载重量进展了有机结合，综合来考虑载重量与配送距离之间的关系，以到达最优

化的配置，是比拟常用的目标之一。9

③综合费用最低，完成最多的任务，花最少的本钱，这是物流配送中的一个

根本原那么。降低各项开支的综合费用是实现物流配送业务中取得良好经济效益

的根本要求。在物流配送中，与配送相关的费用包括：车辆维护费用、车辆耗油

费用、车队管理费用、装卸工所需费用、各部门人员工资费用等。

④准时完成任务，无论是分仓库还是分销点，各种用户都对需求的交货时间

有着严格的要求。配送任务完成的准时性，很大程度上决定了配送公司在客户心

中的地位，决定了公司的信誉度。各种本钱虽然是必须考虑的因素，也是最实际

的因素，但是为提高配送效劳质量，按时完成用户的需求，有时需要将准时性最

高作为配送路线的目标。

⑤使用的车辆数最少，该目标考虑的是使用尽量少的车辆去完成指定的配送

任务。前面的目标表达了各项指标的要求，但是如果车辆跑的距离最短、也是按

时到达的，但是使用的车辆都没有满载，这无疑也是对资源的一种浪费，也不能

是整体配送效益到达最优，所以必须要求车辆的满载率最高，以充分利用车辆的

.word.zl-

.word.zl-

. .word.zl-

装载能力。

⑥劳动消耗最低，充分考虑人的因素。也就是使用最少的司机数，这当然和

前面使用最少的车辆数是一致的，只有车辆少了，司机才会少，只有车辆都装满

了，才会使用最少的车辆。只有选择的距离最短了，司机才能工作最短的时间，

这些都是重要的目标值。

车辆调度问题的分类

车辆调度问题(Visual-ScheduleProblemVSP液提出后，国外各学科的学者从

不同角度对它进展了各种研究，并各自按不同的标准对其进展了分类。综合起来

可分为以下几种：

按车场数目分：有单车场车辆调度问题和多车场车辆调度问题。单车场

问题指配送系统中仅有一个配送中心，多车场车辆调度问题指配送系统中存在多

个配送中心。

按配送任务特征分：分为纯送货问题、纯取货问题以及取送混合问题。

其中纯送货问题指仅仅考虑从物流中心向客户送货，而不考虑从用户向配送中心

送货；纯取货问题指单纯考虑把各客户供给的货物取到配送中心不考虑配送中心

给客户供货问题；取送混合问题是上面两者的有机组合，既要考虑将客户需求的

货物从物流中心送到各个客户，同时还考虑将客户提供的货物从客户取到物流中

心。

按车辆载货状况分：分为满载问题、非满载问题以及满载和非满载混合

问题。10满载问题指的是货运量不小于车辆容量，完成一项任务需要不少于一

辆车；非满载问题指的是货运量小于车辆容量，多项货物合用一辆车，在实际的

车辆配送过程中经常会出现这种处于非满载的状态；满载和非满载混合问题是上

述两者的有机组合，既存在一局部客户需求和供给的货物数量大于或等于车辆的

载重量，同时又存在另一局部客户需求量或供给的货物数量小于车辆的载重量，

上述情况就造成一局部配送车辆满载运行，而另一局部运行在非满载的状态。

按客户对货物处理时间的要求分：分为无时间约束问题和有时间约束问

题。其中无时间约束问题指的是客户对货物的取走和送到的时间没有严格的要

求；有时间约束问题指的是客户要求将其需求的货物在一定的时间围送到，并且

将供给的货物在一定的时间围取走。有时间约束问题又分为硬时间窗问题和软时

间窗问题，硬时间窗问题指的是对任务的完成有硬性的时间限制，或者说时间要

求。软时间窗问题指的是有一定的时间约束，但是相比照拟宽松，尽量在用户规

定的时间围将货物送到或者取走，但是如果超越了规定的时间限制可能要有一定

的处分机制。

按车辆类型分：分为单车型问题和多车型问题。单车型问题指所有配送

车辆类型和容量一样，这种情况方便统一管理和装卸。多车型问题指在执行任务

过程中的配送车辆类型和容量不完全一样，这种情况处理起来比拟复杂。

按车辆对车场所属关系分：分为开放式车辆调度问题和封闭式车辆调度

问题。开放式车辆调度问题指的是车辆完成配送任务后可以不返回其原来发出车

场；封闭式车辆调度问题指的是车辆完成配送任务后必须返回其原来发出车场。

本课题是针对开放式车辆调度问题进展的研究。

按优化目标数分：分为单目标问题和多目标问题。单目标问题指的是仅

考虑一个配送目标；而多目标问题指的是同时考虑多个配送目标。

车辆调度的相关求解算法

用于解决物流配送车辆调度问题的算法分为：准确算法和启发式算法两大

类，准确算法一般用于解决小规模的VRP问题，车辆调度问题应用最为广泛的

算法是启发式算法，启发式算法并不追求问题的最优解，而是强调问题解的满意

性。所以，启发式算法对于大规模的车辆调度问题能在较短的时间获得较满意的

次优解，并且这些算法的通用性也很强。常见的启发式算法有如下几种：

C-WSaving^法

C-WSavings算法采用了几何中三角形的边定理，即三角形的两边之和大于

第三边。当路径中有这样的两个边时用第三边来代替，以到达节约配送距离的目

的。我们可以设节点i和节点j之间的节约量为Sij,这两点和节点o之间的距离

为Doi和Doj,那么Sij=Doi+Doj-Dij〔iwj,i,j=1,2,,算汨苜先求出所有Sij,

并按非增顺序排列。然后从最大的Sij开场，确定是否存在两条路径，其中一条

从弧(0,j)开场，而另一条以(i,o)完毕。如果存在，那么去掉弧(0,j)、(i,o),引入弧

(j,i)合并这两条路径。重复上述过程直到没有路径可以合并。

⑵SweepB^

Sweep®法是一种“先分组后路线〃的算法。所谓的分组就是：首先计算出

要访问的顾客的位置的极坐标，并把这些极坐标按角度大小排序，然后在未分配

到任何路径中的顾客中从角度最小的顾客开场，依次将顾客归并到相应的路径

中，直到车辆的能力约束满足为止，再重新选择新的车辆，重复上述过程，直到

所有的顾客都分配完毕。最后利用TSP的优化算法对各子路经进展优化。

ClusterandRoutes法

一般有两种方法：先聚类后排序方法(CFRS和先排序后聚类方法(RFCS)

CFRS最早由G.Gillett等提出，它是先用启发式方法将节点分成假设干路径，然后对路径中的点进展排序。RFCS由Besley®出，它先对所有节点进展TSP排序,然后将大的路径分成假设干个小路径。

遗传算法GA

遗传算法使用群体搜索技术，借用适者生存规律进展局部搜索改良，它通过

对当前群体施加选择、穿插、变异等一系列遗传操作，从而产生出新一代的群体，

每一次进化那么对应解的一次迭代，并逐步使群体进化到包含或接近最优解的状

体。当迭代次数到达最大次数限制或群体中的个体无显著差异时，迭代终止。

J.Lawrencel1先将GA应用于求解车辆调度问题。

禁忌搜索算法TS

TS的思想由Glover最早提出，它通过对避开一些局部最优解，到达接纳一

局部较差解，从而跳出局部搜索的目的。TS是对局部邻域搜索的一种扩展，是

一种全局逐步寻优算法，是对人类思维过程的一种模拟。禁忌搜索算法通过利用

一个禁忌表记录已经到达过的局部最优点，并在后面的搜索中，根据某种限制循

环的规那么和禁忌表中记录的信息在当前搜索邻域中取一个适宜的解。

模拟退火算法SA

其思想最早有Metropolis1953年提出，Osman于1993年用之解决VRP。模

拟退火算法用固体退火模拟组合优化问题，将能模拟为目标函数值，温度演化成

控制参数。由初始解和控制参数初值开场，对当前解重复“产生新解-计算目标函数差-承受或舍弃〃的迭代，并逐步衰减控制参数值，算法终止时的当前解即为所得近似最优解。

蚁群优化算法ACO

蚁群算法模拟了蚁群搜索食物的行为。蚂蚁在寻找食物时，会在它所经过的

路径排放一种外激素(pheromone,在算法中称为信息素)作为标记，排放的量那

么根据路径长度和食物的等级决定。这些外激素可以指导蚂蚁的运动方向，并使

蚁群朝着外激素强度高的方向移动。在用蚁群算法解决车辆调度问题时，可根据

优化的目标函数个数，构造多组相互协作的人工蚁群，使各组分别优化其中的一

个目标函数，并以共用解的方式建立协作关系。在以上求解VRP的算法中，有

的算法利用全局信息进展整体搜索适合构解，如GA等；还有的利用局部信息，

适合改良解，如SA、TS等。每种方法都各有所长与缺乏，一般来说，根据具体

的求解问题，采用两种或两种以上的混合方法，能够得到更好的解。

小结

本章从车辆调度根本理论的角度，首先介绍了车辆调度涉及到的根本概念，

包括了问题的描述和构成要素。其次对车辆调度问题的分类进展的描述，列举了

一些相关解决车辆调度问题的算法。

第三章遗传算法概述

背景介绍

遗传算法(GeneticAIgorithm.GA)是由美国Michigan大学J.Holland教授和他

的学生开展建立的一类借鉴生物界的进化规律—适者生存、优胜劣汰遗传机制

演化而来的概率搜索算法。GA算法是近几年开展起来的一种崭新的全局优化算

法，遗传算法作为一种非数值并行算法，其思想起源于生物遗传学适者生存的自

然规律，通过自然选择、遗传、变异等作用机制，实现各个体适应性的提高。它

是多学科结合与渗透的产物，已经开展成一种自组织、自适应的综合技术，广泛

应用在计算机科学、工程技术和社会科学等领域。

GA算法是通过对自然进化现象的模拟，利用简单的编码技术和进化机制来

解决复杂的优化问题。特别是由于它不受搜索空间的限制性假设的约束，不必要

.word.zl-

.word.zl-

. .word.zl-

求诸如连续性、导数存在等假设，以及其固有的并行性。它是一种以自然选择和遗传理论为根底，将生物进化过程中适者生存规那么与同一群染色体的随机信息

变换机制相结合的搜索算法，其通过给解向量编码，形成初始种群，然后用变异、

穿插、重组、自然选择等算子，进展并行迭代求得优化解。

由于遗传算法具有不依赖于问题模型采用随机运算，对搜索空间无特殊要

求、无需求导，具有全局最优性求解能力、隐含并行性、收敛速度快以及能高效

率地解决不同非线性问题的鲁棒性的特点。因此近年来有很快的开展，在组合优

化、自适应控制、机器学习等许多领域获得应用，并在电气自动化、计算机和通

信以及人工智能的许多领域取得了非凡的成就，尤其适合求解NP-hard问题。

遗传算法的根本概念

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，因而在

这个算法中要用到各种进化和遗传学的概念。这些概念如下：

串(String)

它是个体(Individual)的形式，对应于遗传学中的染色体(Chromosome)

群体(Population)

个体的集合称为群体，个体是群体的元素。

(3)群体大小(Populationsize并群体中个体的数量称为群体的大小。

基因(Gene)

基因是用中的元素，基因用于表示个体的特征。例如有一个用S=1010,那

么其中的1，0，1，0这4个元素分别称为基因。

基因位置(GenePosition)

一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的

左边向右计算，如在串S=1011中，0基因位置是2。基因位置对应于遗传学中的

地点(Locus)。

基因特征值(GeneFeature)

在用串表示整数时，基因的特征值与二进制数的权一致，如在串S=1011中，

第三基因位值上的1，它的基因特征值为2；第一基因位值上的1，它的基因特

征值为8。

串构造空间S

在串中，基因任意组合构成的串的集合称为串构造空间。基因操作是在构造

空间中进展的。

适应度(Fitness)

表示某一个体对于环境的适应程度。为了表达染色体的适应能力，引入了对

问题中的每一个染色体都能进展度量的函数—适应度函数，用于计算个体在群体

中被使用的概率。

选择(Selection)

就是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代，

故有时也称这一操作为再生(Reproduction｝由于在选择用于繁殖下一代的个体

时，是根据个体对环境的适应度来决定其繁殖量的，故有时也称为非均匀再生

(Differentia1Reproduction。)

穿插(Crossover)

就是在选中用于繁殖下一代的个体中，对两个不同的个体随机选取一个子串

进展交换，从而产生新的个体。

变异(Mutation)

就是在选中的个体中，随机选择两点，将两点间的子用按一定的规那么进展

变异。

传算法的工作流程

遗传算法在整个进化过程中的遗传操作是随机的，但它所呈现出的特性并不

是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻

优点集。这样一代代地不断进化，最后收敛到一个最适应环境的个体上，求得问

题的最优解。遗传算法所涉及的五大要素为：参数编码、初始群体的设定、适应

度函数的设计、遗传操作的设计和控制参数的设定。其流程框图如图3.1所示。

评彷群体

遗化舞作

确定时间问题参型集

(1)位串解砖卷帘数

C2J计，目龌函数

(3)函效侑f适应值

U)适应值调整

三个厘小党子:

(1＞选样

121交叉

图3.1遗传算法流程图

从图3.1可以看出，遗传算法的运行为一个典型的迭代过程，其必须完成的

工作容和根本步骤如下：

选择编码策略，将解空间中的解数据表示成遗传空间的基因型串构造数

据，这些串构造数据的不同组合便构成了不同的编码。

定义适应度函数f(x)。

(3)确定遗传策略，包括选择群体大小n,选择、穿插、变异方法，以及确

定穿插概率pc、变异概率pm等遗传参数。

随机初始化生成群体P。

计算群体中个体位串解码后的适应度f(x)。

按照遗传策略，运用选择、穿插和变异算子作用于群体，形成下一代群

体。

判断群体性能是否满足某一指标，或者己完成预定迭代次数，不满足那

么返回步骤(6)，或者修改遗传策略再返回步骤(6)。

在遗传算法的应用过程中，人们往往结合问题的特征和领域知识对根本遗传

算法进展各种改变，形成了各种各样具体的遗传算法，从而使得遗传算法具备求

解不同类型优化问题的能力。

3.4遗传算法的组成

遗传算法主要由六个局部组成：编码方式、初始群体产生的方法、评价函数、

遗传操作、算法终止条件、算法参数的设置。要利用遗传算法成功的解决物流配

送车辆调度问题，就需要对这六个步骤进展设计。

编码方式

在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进展操

作，而是对表示可行解的个体编码施加选择、穿插、变异等遗传运算，通过这种

.word.zl-

.word.zl-

遗传操作来到达优化的目的，这是遗传算法的特点之一。遗传算法通过这种对个

体编码的操作，不断搜索出适应度较高的个体，并在群体中逐渐增加其数量，最

终寻求出问题的最优解或近似最优解。在遗传算法中如何描述问题的可行解，即

把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方

法就成为编码。

编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步

骤。编码方法除了决定了个体的染色体排列形式之外，它还决定了个体从搜索空

间的基因型变换到解空间的表现型时的解码方法，编码方法也影响到穿插算子、

变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了如何

进展群体的遗传进化运算以及遗传进化运算的效率。一个好的编码方法，有可能

会使得穿插运算、变异运算等遗传操作可以简单的实现和执行。而一个差的编码

方法，却有可能会使得穿插运算、变异运算等遗传操作难以实现，也有可能会产

生很多在可行解集合无对应可行解的个体，这些个体经解码处理后所表示的解称

为无效解。虽然有时产生一些无效解并不完全都是有害的，但大局部情况下它却

是影响遗传算法运行效率的主要因素之一。

针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应

用难点之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密

又完整的指导理论及评价准那么能够帮助我们设计编码方案。作为参考，DeJong

曾提出了两条操作性较强的使用编码原那么：

编码原那么一：应使用能易于产生与所求问题相关的且具有低阶、短定义长

度模式的编码方案。

编码原那么二：应使用能使问题得到自然表示或描述的具有最小编码字符集

的编码方案。

第一个编码原那么中，模式是指具有某些基因相似性的个体的集合，而具有短定义长度、低阶且适应度较高的模式称为构造优良个体的积木块或基因块，这里可以把该编码原那么理解成应使用易于生成适应度较高的个体的编码方案。

第二个编码原那么说明了我们为何偏爱于使用二进制编码方法的原因，因为

它满足这条编码原那么的思想要求。事实上，理论分析说明，与其他编码字符集相比，二进制编码方案能包含最大的模式数，从而使得遗传算法确实定规模的群体中能够处理最多的模式。

由于遗产算法应用的广泛性，迄今为止人们己经提出了许多种不同的编码方法。总的来说，常用的编码方法可分为三大类：二进制编码方法、实数编码方法、有序用编码方法。二进制编码方法是遗传算法中最常用的一种编码方法，它使用

的编码符号集是由二进制符号0和1所组成的二值符号集{0,1},它所构成的个体基因型是一个二进制编码符号用。在二进制编码方式的遗传算法中，遗传操作是作用在编码空间上的，操作后的二进制用通过解码转换到解空间，在这里进展评估选择（如图3-2所示）。

解码

l1►:

编码空M遗传运兑解空间评估与选择

[

编码

图3.2编码解码操作

使用二进制编码方法，在求解高维优化问题时，二进制申会很长，因而算法

的搜索效率很低。为了克制二进制编码方法的缺点，对于变量是实向量的情况，

可以直接采用实数编码方法。实数编码表示比拟自然，较易引入相关领域知识，因此，实数编码还可以使遗传算法更接近问题空间，防止了编码和解码的过程，

其使用将越来越广泛。对很多组合优化问题，目标函数的值不仅与表示解的字符

串中各字符的值有关，而且与其所在字符串的位置有关，这样的问题称为有序问

题，用有序串编码方法表示。这类编码方法较多地用在组合优化问题中，如二次

分配问(QuadraticAssignmentproblem])旅行商问题(TravelingSalesmanProblem)们常用的是有序串的编码方式。

基于遗传算法的以上特点，在本文用遗产算法求解物流配送车辆调度问题

时，我们采用有序串编码方式的染色体设计。初始化过程有很多种，在研究遗传

算法时，常常随机产生初始群体，这样做的好处是产生方式不依赖于问题，也就

是对于任何问题，我们都可以采用这种方式来生成初始群体，由于本文是对某个

特定的非线性规划问题求解，所以我们采用人机交互方式来初始化群体，这样结

合人类智慧使算法优化收敛速度更快。

适应度函数

在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来

度量某个物种对于其生存环境的适应度程度。对生存环境适应程度较高的物种将

有更多的繁殖时机；而对生存环境适应程度较低的物种，其繁殖时机就相对较少。

与此相似，在遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计

算中有可能到达或接近于或有助于找到最优解的优良程度。适应度较高的个体遗

传到下一代的概率就较大，而适应度较低的个体遗传到下一代的概率就相对小一

些。度量个体适应度的函数就称为适应度函数〔FitnessFunction〕。

遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步

.word.zl-

.word.zl-

的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来表达的。评

价个体适应度的一般过程是：

对个体编码串进展解码处理后，可到达个体的表现型。

由个体的表现型可计算出对应个体的目标函数值。

根据最优化问题的类型，由目标函数值按一定的转换规那么求出个体的

适应度。

遗传算法中，群体的进化过程就是以群体中各个个体的适应度为依据，通过

一个反复迭代过程，不断地寻求出适应度较大的个体，最终就可以得到问题的最

优解或者近似最优解。对于本课题的多车场多目标开放式车辆调度模型优化问

题，采用函数值来评价解的好坏，这种方法是最直接，也是最方便的方法，取函

数值最小的解为最优解。

选择策略

遗传算法中的选择策略就是用来确定如何从父代群体中按某种方法选取哪

些个体遗传到下一代群体中的一种遗传运算，选择提供了遗传算法的驱动力。如

果驱动力过大，遗传搜索将过早地终止，而如果驱动力太小，进化过程将变得难

以承受。相对而言，较小的驱动力一般能使群体保持足够的多样性，从而增大了

算法收敛到全局最优的概率。选择操作是建立在对个体的适应度进展评价的根底

之上的，选择操作的主要目的是为了防止基因缺失、提高全局收敛性和计算效率。

下面是遗传算法中较常用到的几种选择策略。

(1)繁殖池(BreedingPool选择

繁殖池选择首先根据当前群体中个体的适应值，按下式计算其相对适应值：

Re/：=&

j-i

其fi是群体中第i个成员的适应值，N是群体规模。那么每个个体的繁殖量为：

Ni-round(Re/xNJ

此处Round(x/示与x距离最小的整数。

计算出群体中每个个体的繁殖量，即可将它们分别复制N个以生成一个临

时群体，即繁殖池(Breedingpool再通过在繁殖池中随机地抽取成对个体进展交配，所产生的后代将取代当前群体形成下一个群体。显然，个体复制到繁殖池的

数目越大，那么它被选到进展交配的时机也就越多，而对于Ni=0的个体，它

们将被淘汰出整个演化过程。在实现算法时需要注意的是，繁殖池中个体的数目不一定正好等于No

(2)轮盘赌选择(RouletteWheelSelection)

轮盘赌选择是由Holland提出的，是最知名的选择方式之一，其根本原理是根据每个染色体适应值的比例来确定该个体的选择概率或生存概率。选择的过程

就是旋转轮盘假设干次〔次数等于种群规模〕，每次为新种群选出一个个体。轮盘赌选择策略在遗传算法中使用的最多，它的具体选择过程为：先计算个体的适

应值Pi,然后根据选择概率把轮盘分成N份，其中第i扇形的中心角为2九£在进展选择时，先转动轮盘，假设某参照点落入到第i个扇形，那么选择个体i<

可见，这种选择方式非常类似轮盘赌中的转盘，小扇区的面积越大，骰子落入其

中的概率也越大，即个体的适应值越大，它被选择到的时机也越大。从而，其基因构造被遗传到下一代的可能性也越大。

(3)锦标赛〔ToumamenU选择

锦标赛选择也是一种基于个体适应度之间大小关系的选择方法。在选择时，

每次进展适应度大小比拟的个体数目称为竞赛规模，一般情况下，竞赛规模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)

这一交换同时定义了一系列的映射：

lc48o57o6和607。

然后从各自的父体中填入无冲突的城市，得到：

Q1=(x23|1876|x9)Q2=(2xx|4567|39)

最后，后代Q1中的第一个“x根据映射4被4代替。类似地，Q1中

的第二个“x用代替，Q2

中的两个“x分别处和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

.word.zl-

.word.zl-

. .word.zl-

依此次序从第二个切割点开场填入第一个后代得到

Q1=(218|4567|93)

类似地，可得到另一个后代

Q2=(345|1876|92)

OX算子开发了路径表示的一个特性，即重要的是城市间的相对次序，而不

是他们的特定位置。也就是，两条路径9-3-4-5-2-18-7-6和4-5-2-1-8-7-6-9-3实际

上是一样的。

(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年成立，至2005年时已成为中国奶制品营业额第二大的公司，其中

液态奶和冰淇淋的产量都居全中国第一。蒙牛主要业务是制造液体奶、冰激凌和

其他乳制品。

1999年8月，蒙牛乳业〔集团〕股份〔简称蒙牛乳业集团〕成立，总部设在

中国乳都核心区――和林格尔经济开发区，拥有总资产100多亿元，职工近3万

人，乳制品年生产能力达600万吨。

到目前为止，包括和林基地在，蒙牛乳业集团已经在全国16个省区市建立

生产基地20多个，拥有液态奶、酸奶、冰淇淋、奶品、奶酪五大系列400多个

品项，产品以其优良的品质覆盖国市场，并出口到美国、加拿大、蒙古、东南亚

及港澳等多个国家和地区。

二、AS/RS出库端车辆调度问题的研究

问题的提出

自动化立体仓库〔AutomaticStorage＆RetrievalSystem〕：是指能自动储存

和输出货物的仓库，它采用多层货架储存单元货物，用自动化货物搬运设备进展

货物的入库和出库。它一般由自动控制与管理系统、货架、巷道式堆垛机、出入

库输送机等构成，能按指令自动完成货物的搬运、存取作业，并能对库存货物进

展自动管理。由于自动化立体仓库具有很高的空间利用率、很强的入出库能力、

采用计算机进展控制管理便于企业实施现代化管理等特点，已成为企业物流和生

产管理不可缺少的仓储技术，自动化立体仓库作为物流中心的重要组成局部，越

来越受到企业的重视。

现阶段对物流配送车辆调度问题的研究很多，但大多是对车辆调度线路选择

问题的研究，对自动化立体仓库出库端车辆调度问题的研究较少。在物流配送中

整个配送时间应包括两局部：出库端的配货时间和装货完成后的送货时间，对车

辆调度线路选择问题的研究可以有效的缩减物流配送中的送货时间，但通过对出

库端车辆调度问题的研究可以有效缩减车辆在出库端的配货时间，对减少物流配送的时间本钱有很大的作用。

所谓自动化立体仓库出库端车辆调度，即在自动化立体仓库出库端按什么样

的原那么给待装货车辆分配车位的问题。现阶段出库端车辆调度大多采用先来先

效劳的原那么，即对先到的车辆优先分配车位，此原那么的采用可以充分表达车

辆调度的公平性，但有很多缺乏。首先当给订货数量特大的订单客户的车辆分配

车位后，此客户后的所有小订货数量客户的车辆都需要等待很长时间才能被分配

车位，减少了系统在一段时间处理客户订单的能力，并且此调度策略没有考虑影

响出库产品整体销售模式的因素。所以本文对自动化立体仓库出库口车辆调度问

题的研究具有重要的实际意义。

问题及相关因素描述

本文是以蒙牛乳业股份自动化立体仓库出库端车辆调度问题为背景进展研

究的。一个大型的立体仓库有多个出库口，每一个出库口对应一个车位，所谓车

位就是车辆装货时在出货口的位置，分为常规固定车位和双向固定车位两种类

型。常规固定车位用于分配后开门的车辆，双向固定车位用于分配侧开门或两端

开门的车辆。其构造如图5.1所示。文章所要解决的问题是如何调度不断到来的

客户车辆为其分配车位，使其能在最短的时间完成装货任务。车辆从进厂到装完

货离开的这段时间我们称为装载时间，影响装载时间的因素很多，这里我们假设

自动化立体仓库有足够大的出库能力，即只要出库口能够装完一盘货物，自动化

立体仓库有足够的能力立即准备好另一盘货。另外假设每个车上的装卸工的装卸

速率都是均等的，这样我们要研究的问题只与对不同用户的车辆的调度顺序有

关。

.word.zl-

.word.zl-

▼环穿小午

一।।,装货车辆

车位io:更工

“位"।友一+常规车位

自动化立体仓库

车位1

埔

送

口

输

这

U

出库环穿

车位9

WiT|CZZ

军位13m

图2.1AS/RS出库端

2.2.1销售派车单

销售派车单是由各事业部的运管部根据销售订单下发，所包括的主要信息

有：出库单号、仓库、数量、品名规格、订单号、订单类型、车辆类型。其他信息包括：定货单位、收货单位、收货单位地址、联系人、联系、运输方式、方案

到达日期等。司机到达蒙牛六期AS/RS出库端后应先到储运部登记，保管员按

司机到达顺序给司机带来的销售派车单据分配优先级，分配原那么是先来先分

配。优先级高的销售派车单对应的车辆被优先调度，被优先下发出库任务。具体

流程图如下所示：

开始

核实

是

III

结束

图2.2原车辆调度流程图

2.2.2订单的优先级表示

为了更好的调度待装货车辆我们引入订单动态优先级的概念，根据装货车辆

到达立体库时所持销售派车单的相关信息确定销售派车单的优先级，以此确定车辆调度的优先级并为车辆分配车位。一个完整的销售派车单主要信息如下:

车辆类型〔Vehicle-Typd：分为集装箱〔两个侧开门或两端开门的车〕和常规车〔有一个后门的车〕两类。其中常规车分配在常规固定车位，集装箱分配在双向固定车位。

.word.zl-

.word.zl-

订单类型〔Order-Type〕：包括外部调拨订单、部调拨订单和销售订单。外

部调拨订单是集团部不同事业部之间调拨产品时所用到的单据；部调拨订单是一

个事业部的部各厂之间调拨产品时所用到的单据；销售订单是客户向本公司订购

产品时所用到的单据，三者都是立体库出库口进展配货的凭证，主要信息有：单

据类型、仓库号、品名规格、数量等。在本文的研究背景中外部