物流配送车辆调度优化研究_夏新海.docx

《物流配送车辆调度优化研究_夏新海.docx》由会员分享，可在线阅读，更多相关《物流配送车辆调度优化研究_夏新海.docx（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 武汉理工大学硕士学位论文 摘要 物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中，配 送 成本占了相当高的比例。配送车辆调度的合理与否对配送速度、成本、效益 影响很 大，特别是多用户配送车辆调度的确定更为复杂。采用科学、合理的方 法来进行配 送车辆调度，是物流配送中非常重要的一项活动。因此，车辆调度 问题 (Vehicle Scheduling Problem，简记 VSP)成为众多学者竟相研究的热门话题。 在髙度发展 的商业社会中，特别是随着 Internet 的普及和电子商务的发展，消费 者对时间的要 求越来越严格，以往的到货 日 已转换成到货 时 。 VSP 是一个典型的

2、 NP-难题，高效的精确算法存在的可能性不大，启发式 算法 虽能快速求解大型问题，但对解的质量没有保证。近些年来，人们在用遗 传算法解 决现实中的各种组合优化问题上进行了探索，如在生产调度问题中的 应用，但在车 辆调度问题中的应用才刚刚开始。有专家断言遗传算法是用来解 决 NP 完全问题和 NP 难题的趋势。 本论文主要对有时间窗的非满载 VSP 和供应商管理库存 （ Vendor Managed Inventory,简记 VMI)管理思想下的 VSP 进行了研究。 对于有时间窗的非满载 VSP 问题，将货运量约束和时间窗约束转化为目标 约 束，建立了 VSP 模型，使用最大保留交叉、交叉率和

3、变异率的自适应调整等 技术， 设计了给予自然数编码的可同时处理软、硬时间窗约束的遗传算法，实 验分析取得 了较好的结果。本论文丰富了遗传算法在组合优化中的应用，为继 续深入研究 VSP、 JOBSHOP 和物流配送车辆调度优化的计算机实现等打下基 础。 对于 VMI 下的 VSP 问题，可以看作上述 VSP 的问题的延伸。本文分析了 VMI 对于供应链物流配送系统优化的作用。在 VMI 管理方式下，存在库存和配 送运输 可以集成起来进一步优化配送系统成本这一实际情况。接着对此问题建 立了数学模 型和迭代优化算法，实例证明该模型和算法能够起到较好的效果。 I 武 汉 理工 大 学硕 士 学位 论

4、 文 物流配送车辆调度优化，是物流配送优化中关键的一环，也是电子商务活 动不 可缺少的内容。对货运车辆进行调度优化，可以提高物流经济效益、实现 物流科学 化。对货运车辆调度优化理论与方法进行系统研究是物流集约化发展、 建立现代调 度指挥系统、发展智能交通运输系统和开展电子商务的基础。目前， 问题的形式已 有很大发展，该问题以不仅仅局限于汽车运输领域，在水运、 航空、通讯、电力、 工业管理、计算机应用等领域也有一定的应用，其算法 己用于航空乘务员轮班安排、 轮船公司运送货物经过港口与货物安排的优化 设计、交通车线路安排、生产系统中 的计划与控制等多种组合优化问题。 关键 字：物流配送，车辆调度，

5、遗传算法，时间窗 ， VMI 武 汉 理工 大 学硕 士 学位 论 文 Abstract Logistic distribution is an operation linking with consumer directly ,and takes account for considerable proportion in variable costs in logistics. The planning of vehicle scheduling in distribution will be take great effect on the efficiency ,cxst ,and b

6、enefit, especially in distributing for multi consumers. A scientific and reasonable method to vehicle scheduling is an important operation in logistic distribution. So,vehicle scheduling problem had become focus of many scholars to study. In the developed commercial society With popularization of in

7、ternet and development of electronic commerce, requirement of cxmsumer for delivery time is higher and higher so that delivery day formerly had turn to delivery hour now. VSP is a typical strong NP- hard problem,high effective exact algorithm is immposible to it. Heuristic Algorithm can resolve larg

8、e-scale problem,but cannot ensure the quality of the resolution. Recently, genetic algorithm has been tyied to resolve variable combinatorial optimization problems, such as job scheduling problem,but but has began just now in VSP. Some people assert that genetic algorithm has tended to NP-had proble

9、m. This paper attempts to take VSP with time window and VSP in VMI as the tow core problems for further research. On the VSP with time window,while the restraints of capacity and time windows are changed into object restraints,a mathematic model is established.We use technique such as maximum preser

10、ved crossover and selfadaptability change of probability of crossover and mutation,and design genetic algorithm on nature number,which can deal with soft and hard time windows.The excellent solutions are obtained in the application. VSP in VMI may be looked as the stretch of the VSP above. On the VS

11、P in VMI,this paper analyses the contribution of the optimization of logistic distributions system.Being aimed at looking for the optimal distribution policy,this paper put delivery routing and inventory into consideration jointly,and brings forward an mathematic model and its algorithm.Consequently

12、,results from 武 汉 理工 大 学硕 士 学位 论 文 VSP is both a pivotal tache in logistic distribution optimization and indispensable in electronic commerce.lt can increase logistic economic benefit and realize logistic rationalization.The systemic study on the theory and method of VSP is the base on the growth of

13、 logistic intensivism ,the establishment of modem chain of command,the development of ITS and EC.Now,the problem is not only applied to the field of auto transportation,but also to ship 、 avigation 、 communication、 electricity、 industry management computer application etc.The algorithm has been appl

14、ied into many combinatorial optimization problems such as the trainman shift arrangement in avigation、 the optimization design of cargo arrangement in ship company、 traffic routing arrangement、 and the plan and Key words: logistic distribution, vehicle scheduling problem, genetic algorithm, time win

15、dows, VMI 武 汉 理工 大 学硕 士 学位 论 文 目 录 第 1 章 概 述 . 1 1. 1 研究背景 . 1 1. 2 论文研究的目的和意义 . 1 1. 3 物流配送 VSP 的研究动态和水平 . 2 1. 4 论文的主要工作 . 10 第 2 章物流配送及其 VSP . 11 2. 1 配送的概念 . 11 2.2 配送的功能要素 . 11 2.3 配送的一般流程 . 13 2.4 物流配送 VSP 概述 . 13 第 3 章遗传算法基本理论 . 15 3.1 遗传算法的基本原理 . 15 3.2 适应度函数 . 18 3.3 遗传算法的基因操作 . 20 3.4 遗传算法

16、的控制参数设定 . 26 3.5 基于自然数编码的模式理论 . 27 第 4 章有时间窗的非满载 VSP 的数学模型及其求解 . 28 4. 1 问题描述 . 28 4.2 数学模型 . 29 4- 3 算法设计 . 32 4.4 算例分析 . 37 第 5 章 VMI 下的 VSP 算法 . 40 5. 1 VMI 的产生 . 40 5. 2 VMI 的实施 . 42 5. 3 VSP 下的数学模型及其求解 . 42 5.4 实例计算 . 47 第 6 章 结 论 与 展 望 . 49 6. 1 主要研究结论 . 49 6. 2 研究展望 . 50 参考文献 . 52 . 54 攻读硕士学位

17、期间发表的论文 . 55 武 汉 理工 大 学硕 士 学位 论 文 第 1 章 概 述 1 . 1 研究背景 在物流配送系统中，物流配送中心的成立可有效的简化配送程序与减少配 送的频率， 以 m 个供应商和 n 个零售商为例，传统的配送模式是假设 n 个零售 商的需求都是由 m 个 供应商自行配送，则一共有 mxn 次的运送，如图 1-1 所示。 假设零售商与供应商之间通 过一个物流配送中心来配送，则只需 m+n 次配送， 如图 1-2 所示，如此一来即可减少 （ mxn-(m+ii)的配送次数，当供应商与零售 商数目越多，节省的配送次数也就会越多。 而物流配送中心作业的重点是如何将车辆有效的

18、使用并决定其最经济的行 驶路 线图，使商品能在最短的时间内送到顾客的手中。国外将此类问题称之为 车辆优化 调度问题 （ Vehicle Scheduling Problem)，简称为 VSP 问题。目前有关 VSP 的研 究，多致力于单一车种或多车种优化调度问题，很少涉及结合时间窗 口的 VSP 问题。 所谓时间窗口是指配送车辆或顾客希望服务或被服务的时间范 围。由于消费者需求 趋于多样化，对送货时间的要求日趋严格，尤其是运送有 时效性的商品，例如海产 品、花卉、蔬菜等讲究新鲜度的货物，除了因缺货造 成的机会成本的损失外，由于 配送不及时也会造成货物价值的大大降低。因此， 在配送运输上，时间因

19、素显得越 来越重要。 有时间窗的 VSP 问题也称为 VSPTW (Vehicle Scheduling Problem with Time Windows)，根据时间约束的严格与否，分为软时间窗和硬时间窗的 VSP。由于 有 时间窗的 VSP 是典型的 NP-难题，会随着节点的增加出现组合爆炸的现象， 因此求 解的困难度及时效性会有影响，然而遗传算法具有随机与多点搜寻特性， 求解时不 易陷入局部最优解，因此应用遗传算法求解 VSPTW 问题是一种有效的 途径。 目前国外发达国家从实际上和理论上都认识到供应商管理库存（ VMI)对于 整体供应 链物流系统巨大优化作用，在 VMI 管理方式下，存

20、在库存和配送运输 可以集成起来进一 步优化配送系统成本这一实际情况，对于 VMI 下的 VSP 也有 研究的必要。 1 . 2 论文研究的目的和意义 武 汉 理工 大 学硕 士 学位 论 文 本论文研究的目的为： (1) 构建以配送成本最小与顾客满意度最大为目标的车辆优化调度模型。 (2) 利用遗传算法的原理和其在组合优化方面的优点，为物流配送车辆调 度 问题的求解提供一个切实可行的算法，求得一个较优的可行解，并说明其有 效性。 (3) 对 VMI 下的 VSP 问题进行初步研究，将运输成本与库存成本综合起 来 考虑。 意义为 .“ 物流配送车辆调度优化，是物流配送优化中关键的一环，也是电 子

21、 商务活动不可缺少的内容。对货运车辆进行路径优化，可以提高物流经济效 益、实 现物流科学化。对货运车辆路径优化理论与方法进行系统研究是物流集 约化发展、 建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的 基础。 近些年来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探 索， 如在生产调度问题中的应用，但在车辆路径问题中的应用才刚刚开始。有 专家断言 遗传算法是用来解决 NP 完全问题和 NP 难题的趋势。本文丰富了遗传 算法在组合 优化中的应用，为继续深入研究 VSP、 JOB SHOP 和物流配送车辆 调度优化的 计算机实现等打下基础。 1 . 3 物流配送 VSP 的研究

22、动态和水平 1.3. 1 问题的提出 物流配送车辆优化调度问题最早是由 Dantzig 和 Ramser 于 1959 年首次 提出，自此， 很快引起运筹学、应用数学、组合数学、图论与网络分析、物 流科学、计算机应用等学 科的专家与运输计划制定者和管理者的 _极大重视， 成为运筹学与组合优化领域的前沿与 研究热点问题。各学科专家对该问题进 行了大量的理论研究及实验分析，取得了很大的 进展。 该问题一般定义为：对一系列装货点或卸货点，组织适当的行车线路，使 车辆 有序的通过它们，再满足一定的约束条件（如货物需求量、发送量、交发 货时间、 车辆容量限制等）下，达到一定的目标（如路程最短、费用最少、

23、使 用车辆尽量少 等 )。 武 汉 理工 大 学硕 士 学位 论 文 国外对物流配送车辆调度问题作了大量而深入的研究，例如早在 1983 年 Bodin、 Golden 等人在他们的综述文章中就列举了 700 余篇文献。在 Christofides(1985)， Golden 和 Assad(1988)编辑的论文集，以及 Altinkemer 和 Gavish(1991)， Laporte(1992),SalM(1993)等的综述文章中都进行了详尽的阐述。 该领域的代表人物有 odin， Christofides， Golden， Assad， BaU,Laporte， Rinnooy Kan

24、， Lenstra， Desrosiers 和 Desrochers 等人。 目前，问题的形式己有很大发展，该问题以不仅仅局限于汽车运输领域， 在水运、 航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用， 其算法己用于航空 乘务员轮班安排、轮船公司运送货物经过港口与货物安排 的优化设计、交通车线路安排、 生产系统中的计划与控制等多种组合优化问 题。 供应商（ S) 零售商（ R) 图 1-1 传统的物流配送模式 武 汉 理工 大 学硕 士 学位 论 文 供应商（ S) 零售商（ R) 图 1-2 以物流为中心的配送模式 国内对 VSP 的研究相当少，主要研究对象是旅行商问题 （ Tr

25、aveling Salesman Problem，简称 TSP)、中国邮递员问题 （ Chinese Postman Problem， 简称 CPP)、 有向中国邮递员问题 （ Directed Chinese Postman Problem,简称 DCPP)等，系统 性研究还尚未见到。李大为等（ 1998)以 TSP 的最近距离启 发式为基础，通过设置 评价函数来处理时间窗约束，求解了简单的 VSP。张 震（ 1995)针对单车场满载问 题，提出了考虑运输行程约束的优化方法。遗 传算法和神经网络方法对简单 TSP 的 求解取得了一定成果。蔡延光等（ 1998) 应用并行表搜索法和模拟退火法针

26、对简单 情形对满载问题进行了求解。 对于 VMI 下的综合考虑库存成本和运输成本的 VSP 的问题，一些学者正 从理 论上进行探索，往往将实际问题进行简化，用近似方法进行处理。 1.3.2 VSP 问题的解法回顾 针对早期与现今的车辆配送问题模型，己有相当多的文献提出求解方法， 可分为以 下四大 () 系统仿真法（ Simulation) 此方法最早由 Golden 和 Skiscim 于 1986 年提出，主要应用于行车线路与物 武 汉 理工 大 学硕 士 学位 论 文 流中心区位的选择，优点在于可直接观察系统安排的效率与效果，但由于问题 的实 际情况多变且具有不确定性，是否能将实际的配送情

27、形系统逻辑化为仿真程 序，往 往另人质疑。 (二） 人机互动法 此方法结合人类决策与计算机计算能力，在求解的过程中，通过高度的人 机 交互模式，结合专家的决策信息，并据以计算出结果；优点是寻优的过程中， 决策 者可以很清楚地看到各约束条件之间的替代关系，以及参数变化可能导致 的成本变 化。 (三） 精确解法 （ Exact procedures ) 精确解法将车辆配送问题，通过严谨的数学模型或计算机数据结构规划， 利 用数学法则或数据结构搜寻的方式，求得问题的解。由于两种方法都在所有 可行解 集合 （ Feasible Solution Set)寻找最优解，所以所求的解均为最优解。随 着变量的

28、 增加，车辆配送问题的解集合会有组合爆炸 （ Combinatorial Explosion) 的现象， 求解时间也呈指数函数的趋势增长，不能在有限的时间 （ Polynomial Time)给予决 策者一个可行解，是这种方法最大的缺点。常见的精确解法有动 态规划法 （ Dynamic programming)、分枝定界法 （ Branch and bound)与切平面 法（ Cuttingplanes)， 详细内容分述如下： (1) 动态规划法 （ Dynamic programming) 此方法的核心观念为最佳化原理，其运用数学逻辑来处理一连串相互关连 的 决策问题，并采取系统化步骤以求得

29、以整体最有利的策略。求解方法与步骤 如下所 述： 步骤一 “ 将整个问题分解为许多相互关联的局部问题，以便个别分析处理。 步骤二：从最后一个阶段的各种状态中，找出最有利的决策方案。 步骤三 “利用 反策推算法 ，自最后一个阶段逐步向前项阶段推进，直到 各阶段的最有利策略均找出为止。 Held 和 Karp 运用此法于求解巡回推销员问题，因其计算时间与计算机内 存 空间均随变量的增加而呈指数增加，所以虽然此方法可求得最优解，但仅适 用于规 模较小的问题。 (2) 分枝定界法 （ Branch and bound) 此方法是组合优化问题的有效求解方法，其步骤如下所述： 步骤一：如果问题的目标为最小

30、化，则设定目前最优解的值 武 汉 理工 大 学硕 士 学位 论 文 步骤二 ： 根据分枝法则 （ Branchingrule)，从尚未被洞悉（ Fathomed)节点 (局部 解）中选择一个节点，并在此节点的下 阶层中分为几个新的节点。 步骤三：计算每一个新分枝出来的节点的下限值 （ Lower bound; LB) 步骤四：对每一节点进行洞悉条件测试，若节点满足以下任意一个条件， 则此节点 可洞悉而不再被考虑： 1 此节点的下限值大于等于 Z 值。 2 已找到在此节点中，具最小下限值的可行解；若此条件成立，则需比较 此可行 解与 Z 值，若前者较小，则需更新 Z 值，燕以此为可行解的值。 3

31、 此节点不可能包含可行解。 步骤五：判断是否仍有尚未被洞悉的节点，如果有，则进行步骤二，如果 已 无尚未被洞悉的节点，则演算停止，并得到最优解 . Kolen at al.曾利用此方法求解含时间窗约束的车辆巡回问题，其实验的节 点 数范围为 6-15。当节点数为 6 时，计算机演算所花费的时间大约 1 分钟（计 算机型 为 VAZ11/785)，当节点数扩大至 12 时，计算机有内存不足的现象产生， 所以分枝 定界法比较适用于求解小型问题。 Held 和 Karp 指出分枝定界法的求解 效率，与其 界限设定的宽紧有极大的关系。 (3)切平面法（ Cuttingplanes) 此方法与分枝界限法

32、类似，也是在求解与整数规划相对应的线性规划上， 不断地增 加新的约束，也就是另外加入线性约束条件，以切掉对应于非整数规 划的所有可行解的 集合，以使问题可达到整数线性规划求解的形式，从而获得 最优解。 上述三种精确解法的优点在于可求得最优解，缺点在于求解时间过长。 (四）启发式算法（ Heuristics) 由于上述三种方法的求解效率较差，所以大部分的学者都致力于启发式解 法 的发展。该方法在解题时可减少搜寻的次数，所以是一种容易且快速求解困 难问题 的算法。 Solomon 曾提出数个时间窗约束车辆巡回问题的启发式解法，包 括节省法 （ Saving method)、最邻近法 （ Neare

33、st neighbor)、插入法（ Insertion) 及扫描法 （ Sweeping)。由于上述各解法起初都用于求解 VSP 问题，如果应用于 求解 VRPTW 问题时，则在求解过程中必须增加时间可行性的检验的目的在于 确保配送行程能满 足顾客的时间窗的要求：所以当顾客被排入路径时，需检验 该排入时点是否违反该 顾客与其后影响的时间窗的限制。以下针对各启发式解 其中 dfcO) 代 表 顾 客 / 至 场 站 的 点 Z 与 y 间 的 节 省 值 时 ， 应 先 计 武汉理丨 :大学硕士学位论文 法进行探讨。 (1)节省法 Clarke & Wright 于 1964 年提出该方法以求解

34、车辆巡回问题，其思想在于按 节 省值（较短路径与原路径之差）由大至小排序，在车辆容量限制下，依序将 对应的 两顾客点排入路径中，直至所有顾客都被排入路径为止。 Solomon 于 1983 年将此法 应用于求解时间窗约束的车辆巡回问题，关键在于当节省值较大的两 顾客点被排入 路径时，除需考虑车辆容量限制外，更需要考虑到时间窗的限制， 也就是时间窗上 界较早者，应优先被配送，并检验其时间可行性，此方法的优 点是提高车辆的利用 率，而两节点间的节省值的计算公式与意义如下所示： 距 离 ，则 代 表 顾 客 / 至 / 的 距 离 a 计 算 两 节 算 原 路 径 中 各 往 返 路 径 的 总

35、和 ， 再 以 之 与较短路的总路径和相比较；两节点的原路径与较短路如图 2-5 所示。 图 1-3 节省法的图示 (2) 最邻近法 . Solomon 于 1983 年所提出的求解的 VSPTW 的方法，该方法的思想如下所 述： 出配送中心开始搜寻，若 /为离配送中心最邻近的节点 .最小）则其优先 排入路径中， 接着搜寻另一节点 J 以排入路径的下一位，且该节点加入后必须满 足以下条件，满足 者称为可排入点； 1. 之前尚被排入路径的节点 2. cl； /最小者 3. 车辆载量限制与时窗限制的时间可行性 武 汉 理工 大 学硕 士 学位 论 文 若其它尚未排入路径的节点中皆无法找到可排入点，

36、则构造另一新路径， 直到 所有顾客点都被排入所有路径为止。而决定节点是否为最邻近点的要素有 以下三点： 1. 两顾客节点间的距离心 2. 两顾客节点间的运输时间 & 3. 配送下顾客时所需等待服务的时间 在决定两节点间的最邻近法总成本时，场站应先评估对些三要素的权重组 合， 且总和应为 1，所以最邻近法总成本的计算公式如下所示： Cij + 2ij + 其中 ) |, - U j +Ixij s / -U s/ 式中一般可令 t 点 f 在线路的第 f 部访问； u, =(0 否则。 那 么 在 一 条 线 路 中 ， 若 存 在 弧 ( / , _ / ) ， 即 则 有 f (f +1)+

37、 / -1 如果没有弧 (/， /“) ，即 ;c, y= 0 , 那 么 有 Mi -Uj l , U j fel) 式（ 4-9)为变量的取值约束。 4.2.2 有时间窗 VSP 模型 设完成任务 需要的时间（装货或卸货）表示为 I；，又设任务 /的开始时间需 在 一 定 的 时 间 范 围 内 ， 其 中 + 为 任 务 / 的 允 许 最 早 开 始 时 间 ， 为 任 务 / 的 允许最迟开始时间。如果车辆到达 /的时间早于 a,，则车辆需在 /处等待，如果 车 辆 到 达 时 间 晚 于 则 任 务 i 要延迟执行。求满足货运要求的费用最少的车辆 行使线路。此问题称之为有时间窗的车