2013-7-10
高开周
35
（一）起讫点不同的单一路线选择问题
车辆路线的实际问题包括配送中心配送、公共汽 车路线制定、信件和报纸投递、航空和铁路时间表 安排、工业废品收集等。
2013-7-10 高开周 6
车辆路径问题的类型
一般而言车辆路线问题大致可以分为以下三种 类型（Ballou，1992）：
1、相异的单一起点和单一终点。
2、相同的单一起点和终点。
3、多个起点和终点。
2013-7-10
高开周
21
车辆路线问题研究现状
1995年，Fisher曾将求解车辆路线问题的算法分 成三个阶段。第一阶段是从1960年到1970年，属于 简单启发式方式，包括有各种局部改善启发式算法 和贪婪法（Greedy）等；第二阶段是从1970年到 1980年，属于一种以数学规划为主的启发式解法， 包括指派法、集合分割法和集合涵盖法；第三阶段 是从1990开始至今，属于较新的方法，包括利用严 谨启发式方法、人工智能方法等。
2013-7-10 高开周 27
成本比较法
某公司欲将产品从座落位置A的工厂运往座落位置B的公 司自有仓库，年运量D为700,000件，每件产品的价格C为30元， 每年的存货成本I为产品价格的30％。公司希望选择使总成本 最小的运输方式。据估计，运输时间每减少一天，平均库存 可以减少1％。各种运输服务的参数如图。 在途运输年存货成本为ICDT/365，两端储存点的存货 成本各为，但其中C值有差别，工厂的储存点C为产品的价格， 购买者储存点的C为产品价格加上运费之和。 问题：选择哪种运输方式的方案最优？
2013-7-10
高开周
10
数学解析法
1、分枝界限法把问题的可行解展开如树的分枝，再 经由各个分枝中寻找最佳解。
2、整数规划法在数学模式中加入变量必须为整数的 限制式，将问题列出目标方程序以及限制式来求 解，能够将实际情形化做限制条件加入模式中， 让一般人较容易理解及方便使用。这个解法会随 限制式的增加而趋于复杂，使得演算复杂度大为 提高。
2013-7-10
高开周
28
2013-7-10
高开周
29
制定车辆运行路线
采用扫描法制定行车路线，由两个阶段组成：
•
将停留点的货运量分配给送货车；
• 安排停留点在路线上的顺序。 扫描法的步骤：
• 在地图上或者方格图中确定所有站点（含仓 库）的位置；
2013-7-10
高开周
30
自仓库开始沿任一方向向外划一直线，沿着顺时针 或者逆时针方向旋转该直线与某点相交。同时要考
2013-7-10 高开周 13
先分群再排路线
2 1 3 0 5
6
4 7 8
2013-7-10
高开周
14
先排路线再分群
2 1 3 0 5
6
4 7 8
2013-7-10
高开周
15
节省法
5+6-4=7
2
4
1
6+4-8=2
8 4 4
3
6 6
0
5 5 10
5+4-10=-1
2013-7-10
高开周
16
虑如果在某线路上再增加该站点，是否会超过车辆
的载货能力？如没有，继续旋转该直线直到与下一 个站点相交。再次计算累计货运量是否超过车辆的
运载能力（先使用最大的车辆）。如超过，就去掉
最后的站点，并确定路线。最后，从不包括在上一 条路线中的站点开始，继续旋转以寻找新路线。直 到所有点被安排在路线中； 排定各路线上每个站点的顺序，使行车路线最短。
2013-7-10
高开周
20
车辆路线问题研究现状
求解方法
综合过去有关车辆路线问题的求解方法，可以分 为 精 确 算 法 （ exact algorithm ） 与 启 发 式 解 法 （heuristics），其中精密算法有分支界限法、分 支切割法、集合涵盖法等；启发式解法有节约法、 模拟退火法、确定性退火法、禁忌搜寻法、基因 算法、神经网络、蚂蚁算法等。
2013-7-10 高开周 25
2013-7-10
高开周
26
他们再将每月的运输总支出，根据运送的次数进 行了计算，并对单程与往返、自营与外包进行了比较， 见表2。
结果发现，不论是以单程还是以往返计算，如果 货流量足以使运送次数保持在3趟或以上，自营将比 “外包”更经济。由于自营车辆每辆每月的最大往返 次数为5趟，所以只有在货流量在6～7趟时，对于自 营车辆无力运送的部分才可能采取外包。
2013-7-10
高开周
3
车辆路径问题的概念
由 此 定 义 不 难 看 出 ， 旅 行 商 问 题 （ Traveling Saleman Problem,TSP ） 是 VRP 的 特 例 ， 由 于 Gaery已证明TSP问题是NP难题，因此，VRP也属 于NP难题。
车辆路线问题自1959年提出以来，一直是网络优 化问题中最基本的问题之一，由于其应用的广泛性 和经济上的重大价值，一直受到国内外学者的广泛 关注。车辆路线问题可以描述如下（如图1）：
不同运输方式的技术和经济运作特征对比
铁路 成本 速度 频率 可靠性 可用性 距离 规模 能力
2013-7-10
公路 中 快 很高 好 有限 中，短 小 强
高开周
航空 高 很快 高 好 有限 很长 小 弱
水路 低 慢 有限 有限 很有限 很长 大 最强
管道 很低 很慢 连续 很好 专业化 长 大 最弱
高开周
2013-7-10
31
1000
3000 2000
4000
2000 3000 3000
1000 2000 2000
汽车站 2000 停留点提货量数据
2000
1000 3000 2000
4000
2000 3000
3000
1000 汽车站 2000 2000
2000
2000
扫描法解决方案
2013-7-10 高开周 32
2013-7-10 高开周 12
人机互动法
人机互动法是利用人的经验和计算机的运算所 合成的方法，而根据Bodin(1983)等人的描述，人机 互动法是一种将人的反应能力，纳入问题求解过程 的一般性解法。其具备人的实际情况和计算机强力 的计算能力等综合优势，这种方法是先将使用者或 是规划者的规划直觉、经验、及能力纳入求解的重 要因子，并数据话统整后交由计算机依一定的公式 来运算其派车路线的最佳解，并在获得路线的解只 后再重新由使用者依据现实层面的考虑因素进行修 改更正。
2013-7-10 高开周 11
数学解析法
3、动态规划法主要是将一个大问题分解成几 个小问题来求解，以反向工作的方式，求 解路径中连接两点的最短距离，但是动态 规划法缺乏效率，比较适合小问题和批次 问题。Bodin（1983）等人同时也指出，此 类方法虽然可以求得最佳解，但其求解范 围太小，当需求点数目大于25时便无法使 用。
2013-7-10 高开周 19
车辆路线问题研究现状
车 辆 多 次 使 用 的 车 辆 路 线 问 题 （ vehicle
routingproblems with multiple use of vehicle ， VRPM ） 、 考 虑 收 集 的 车 辆 路 线 问 题 （ vehicle routingproblems with backhauls，VRPB）、随机 需求车辆路线问题（vehicle routing problem with stochastic demand，VRPSD）等。
2013-7-10 高开周 4
车辆路径问题的概念
2013-7-10
高开周
5
车辆路径问题的概念
设有一场站（depot），共有M 辆货车，车辆容 量为Q，有N位顾客（customer），每位顾客有其需 求量D。车辆从场站出发对客户进行配送服务最后 返回场站，要求所有顾客都被配送，每位顾客一次 配送完成，且不能违反车辆容量的限制，目的是所 有车辆路线的总距离最小。
改善或交换法
1.线路内路线交换或节点交换 2.路线间部分线路交换
3.路线间节点交换
2013-7-10
高开周
17
车辆路线问题研究现状
经过几十年的研究发展，车辆路线问题研究取 得了大量成果。下面从车辆路线问题的现有研究型 态和求解方法两个方面介绍车辆路线问题的研究现 状。
2013-7-10
高开周
18
2013-7-10
高开周
8
数学解析法
最佳解法又称“精确解法”、数学解析法， 就是标准的”最佳化法”，将车辆配送问题， 通过严谨的数学模型或计算机数据结构规划， 利用数学法则或数据结构搜寻的方式，求得 问题的解1。
2013-7-10
高开周
9
数学解析法
常见的有:
分枝界限法（Branch and Bound）、 整数规划法（Integer Programming）、 动态规划法（Dynamic Programming）。
安排车辆运行时间
将所有运输路线首尾相连顺序排列，使车辆的 空闲时间最短，就此决定车辆数，并排出配车计划。
2013-7-10
高开周
33
最优运输计划安排表
1号线 9号线 5号线 2号线
10号线 4号线 8号线 7号线 3号线
6号线
2013-7-10
高开周
34
单一路线选择
• 运输线路的选择影响到运输设备和人员的 利用，正确地确定合理的运输线路可以缩 短运输时间，降低运输成本，因此运输线 路的的选择是运输决策的一个重要领域。 • 运输线路选择问题尽管种类繁多，但我们 可以简单划分为单一路线选择和多起讫点 路线选择两种类型。