运输及配送路线的优化课件

1、六、运输决策及配送路线的优化6.1运输系统的重要性与功能6.2基本运输方式及其运营特点6.3运输合理化6.4运输路线的选择6.5车辆路线、时间安排六、运输决策及配送路线的优化6.1运输系统的重要性与功能6.1运输系统的重要性与功能运输指借助公共运输线及其设施和运输工具来实现人与物空间位移的一种经济活动和社会活动。交通与运输反映的同一过程的两个方面。同一过程：运输工具在运输网路上的流动；两个方面：交通关心的是运输工具的流动情况(流量的大小、拥挤的程度)运输关心的是流动中的运输工具上的载运情况(载人与物的有无与多少，将其输送了多远的距离) 运输是交通的目的运输系统的重要性地域分工专业化规模经济竞争

2、加剧土地价值的提高6.1运输系统的重要性与功能运输指借助公共运输线及其设施交通运输系统的构成要素：（1）运载工具（2）通路（3）场站（4）动力（5）通信（6）经营管理人员和经营机构产品转移运输克服了产品在生产与需求之间存在的空间和时间上的差异。产品存储对产品进行临时存储是指将运输车辆临时作为相当昂贵的存储设施。运输的功能交通运输系统的构成要素：运输的功能运输服务的特征运输服务是一种特殊的产品：运输服务产品具有无形性运输服务的生产和消费不可分离运输服务具有不可存储性异质性，即同一种服务的质量差别 运输服务的特征运输服务是一种特殊的产品：6.2 运输方式及其特征一、铁路运输铁路是国民经济的大动脉，

3、铁路运输是我国货物运输的主要方式。铁路运输的主要特点是能够远距离运输大量货物。由于世界上几乎所有的大都市、我国的绝大部分城市都通铁路，铁路在国际、国内运输中占有相当大的市场份额。 虽然设备和站点等的限制使得铁路运营的固定成本很高，但是铁路运营的变动成本（如维修、管理、耗能等）相对较低，这也使得铁路运输的总成本通常比公路和航空运输低。高固定成本和低变动成本使铁路运输的规模经济十分明显。6.2 运输方式及其特征一、铁路运输铁路运输铁路运输方式的主要优点：运输能力大 运行速度较快，时速一般在80120公里 适应性强，受天气限制条件少，安全可靠性高 运输成本低 环境污染小，环境成本低 铁路运输方式的主

4、要缺点 ：灵活性差对包装的要求较高存在货物被偷盗的危险铁路设施修建成本较高，占地多。 综合考虑，铁路适于在内陆地区作为长途、大批量运送低价值、高密度的一般货物和可靠性要求高的特种货物；从投资的情况来看，在运输量比较大的地区之间建设铁路较为合理。 铁路运输铁路运输方式的主要优点：铁路运输方式的主要缺点 ： 6.2 运输方式及其特征二、公路运输公路运输具有规模巨大，分布极广的道路基础设施体系和机动灵活、适应性强的车辆装备系统。大多数的消费品都是通过公路运输的。公路运输是任何公司物流系统中重要的一部分。公路运输的固定成本很低。汽车承运人在固定基础设施的投资相对较少，多数公路的建设运营由政府进行。公路

5、运输的变动成本相对较高，因为公路的建设和维修费用经常是以税收和收费站的形式向承运人征收的。此外，汽车的能耗、维修费用相对也比较高。燃油税6.2 运输方式及其特征二、公路运输公路运输 公路运输方式的主要优点：原始投资少，资金周转快，投资回收期短机动灵活，门对门运输 快捷可控 包装成本低，货物损失小 公路运输的主要缺点 ：运输能力小劳动生产率低，单位运价高 公路拥挤与污染，环境成本高 公路运输不像其它运输方式那样受到各种线路的限制，其市场覆盖面要高于其它运输方式。公路运输的特点使得公路运输尤其适于短距离、高价值产品的装运，在中间产品和轻工产品的运输方面有较大的优势。 公路运输 公路运输方式的主要优

6、点：公路运输的主要缺点 ： 6.2运输方式及其特征三、水路运输水路运输在世界外贸运输中始终保持主导地位，在经济合作和交流中起着纽带作用。受自然条件的制约，水路运输的运营范围和运输速度受到限制，但是却有其它运输方式不可比拟的优势和潜力。水运中水道的改良维护通常由政府负责，港口的开发和维护各国不同，但一般也由政府统一进行，而运输公司只需支付一定的费用就可以使用港口和其它码头设施。因此，在固定成本方面，水路运输在铁路和公路运输之间。水路运输的变动成本较低，主要包括运营中的成本，其规模经济的效应更加明显。6.2运输方式及其特征三、水路运输水路运输 水路运输方式的主要优点：单位运输工具的装载量大，运输能

7、力高，运输距离长 水路运输成本低，基础设施投资节省，单位运价低廉 能源消耗少 水路运输方式的主要缺点：运输速度慢 受天气和其它自然条件影响大，线路迂回 货物破损较多 可靠性差 与上述特点相对应，水路运输适于运送数量巨大、低价值、时效性要求不高的货物，如矿石、煤炭、石油农产品等。水路运输是大宗货物长距离运输的理想选择。 水路运输 水路运输方式的主要优点：水路运输方式的主要缺点：6.2 运输方式及其特征四、航空运输航空货运的主要优点在于运输速度快。随着航空运输技术的不断成熟，航空运输在远距离运输，特别是跨国运输中显示出无可比拟的优势。只有在运输高价值的和对时效性要求高于对成本要求的产品时，航空运输

8、才有其合理性。航空的固定成本较低。空中航线和管制系统由国家拥有，航空港的建设运营由国家投资，航空公司的固定成本主要与购买飞机有关，也与所需的搬运系统和货物集装箱有关。航空运输的变动成本是极高的，其燃料消耗、飞行器的维修保养以及飞行人员和地勤人员的费用都是一笔可观的支出。6.2 运输方式及其特征四、航空运输航空运输航空运输的主要优点：运行速度快 灵活、机动性大 航空运输服务质量高、安全可靠 航空运输的主要缺点：运输成本高 运输能力小 有些货物禁用空运 受天气影响较大 综合上述优缺点，航空运输适用于长途旅客运输和紧急需要的、时效性要求高的、单位价值高的货物运输。 航空运输航空运输的主要优点：航空运

9、输的主要缺点： 6.2 运输方式及其特征五、管道运输管道是很独特的运输方式，它所能运送的货物种类很有限，主要通过管道运输的货物是：石油及成品油、天然气、化学制品。管道运输的优势：费用低。货损、货差率低。另外，因为管道运输速度很慢，还可以将管道作为仓库。可靠性好、不受天气影响、很少有机械故障管道运输的缺点：管道线路是相对固定的，因此有地域灵活性或可达性的限制。管道运输的产品有局限性，并且只能提供单向服务。6.2 运输方式及其特征五、管道运输各种运输方式技术经济特征比较表运输方式基建投资运载量运输成本速度连续性灵活性生产率安全性线路运具铁路622431343河运343266424海运1311555

10、15公路455522166管道514343631航空266614252 注：表中数字表示各种运输方式在某一方面的优劣次序。各种运输方式技术经济特征比较表运输方式基建投资运载量运输成本影响运输决策的成本因素影响承运人定价的成本因素与运距有关的成本与运量有关的成本与速度有关的成本直送v.s中转影响承运人运力组合的成本因素固定成本运营成本影响运输决策的成本因素影响承运人定价的成本因素运输特性规模特性随着一次装运量的增大，使每单位重量的运输成本下降。距离特性随着一次运输距离的增加，运输费用的增加会变的越来越缓慢，或者说单位运输距离的费用减少，运输成本与一次运输的距离有关。速度特性完成特定的运输所需的时

11、间越短，其效用价值越高。单位货物运输成本运输距离距离与运输成本的关系单位货物运输成本装载重量载重量与运输成本的关系运输效用送达时间送达时间与运输效用的关系运输特性规模特性单位货物运输成本运输距离距离与运输成本的关系影响承运人运力组合的成本因素影响承运人运力组合的成本因素n the number of time periods into which the time horizon of a year is decomposed (for example, n = 52 if the time period corresponds to a week)v the decision variabl

12、e corresponding to the number of owned vehiclesvt , t = 1,.,n, the required number of vehicles at time period t;m the number of time periods per year in which vt v.cF fixed cost （ an owned vehicle）cV variable cost （ an owned vehicle）cH be the cost per time period of hiring a vehicle (clearly, c F +

13、c V c H ). n the number of time periodAs the two summations in Equation are equal to the areas below and above the line vt = v, respectively , then their derivatives are equal to m and m, respectively. Consequently, C(v) is minimal whenAs the two summations in Equat运输及配送路线的优化影响托运人决策的成本因素服务水平成本（运输时间-

14、速度）运输成本（运输方式、运输规模）库存成本交易成本影响托运人决策的成本因素服务水平成本（运输时间-速度）运输服务的选择 运输成本、速度和对库存的影响是决策者心目中最重要的运输服务要素，因此，这三项是运输服务选择的基础。运输对库存的影响有以下几点：较慢的运输模式会引起较大的中转或运输库存；较大运量的运输方式会出现订单批量超过需求量的情况，从而增加库存；不可靠的运输模式会引起安全库存的提高。在选择运输方式时，就需要考虑库存持有成本可能升高，而抵消运输服务成本降低的情况。运输服务的选择 运输成本、速度和对库存的影响是决策者心目中最运输服务的选择的定量分析法基于运输成本与库存成本的总成本分析方法【例

15、】某公司欲将产品从位置A的工厂运往位置B的公司自有仓库，年运量D=700000件，产品价值C=30元，年存货成本I=产品价格的30。公司希望选择使总成本最小的运输方式。据估计，运输时间每减少一天，平均库存成本可以减少1。各种运输服务方式的有关参数见表：运输服务的选择的定量分析法基于运输成本与库存成本的总成本分析运输服务的选择的定量分析法运输方式 费率R(元/件) 时间T(天) 年运送批次 平均存货量Q/2 铁路 0.12110100000水运 0路 0.252042000航空1.424020250考虑安全库存运输服务的选择的定量分析法运输方式 费率R(元/件) 时间T

16、运输服务的选择的定量分析法分析：以年总成本最低为原则来选择合适的运输方式。这里，总成本=运输费用+库存成本；其中，运输费用=运输量费率库存成本=在途运输库存成本+工厂存货成本+仓库存货成本在途运输库存费用=ICDT/365工厂存货成本=ICQ/2仓库存货成本=I（C+R）Q/2代入各种运输方式的基本数据信息，将相应的成本计算结果列入表2。D年运量；C产品单价； I年存货成本（产品价格的30）；T运输时间； R费率 (元/件) ； Q/2平均存货量运输服务的选择的定量分析法分析：二、运输方式选择的定量分析法由表中结果可知，总成本最低的是公路运输方式，总成本为984821元，其次是水路运输，成本最

17、高的是铁路运输。按照总成本最低的原则，适合选择公路运输方式。 成本类型 计算公式 铁路运输 水路运输 公路运输 航空运输 运输成本 RD 70000105000140000980000在途库存 ICDT/365 345205241644 8630134521工厂存货 ICQ/2 900000416500378000182250仓库存货 I(C+R)Q/2903000420593380520190755总成本 221820511857379848211387526二、运输方式选择的定量分析法由表中结果可知，总成本最低的是公6.4运输路线的选择1起、止点不同的单一路径规划2多个起、止点的路径规划3

18、起点和终点相同的路径规划Traveling Salesman Problem (TSP)Vehicle Routing Problem (VRP)6.4运输路线的选择1起、止点不同的单一路径规划6.4运输路线的选择1起、止点不同的单一路径规划这类路径规划问题称为最短路问题。最短路径问题是线路优化模型理论中最为基础的问题之一。问题描述：假设有一n个节点和m条弧的连通图G（Vn,Em),并且图中的每条弧（i,j)都有一个长度cij(或者费用cij)，则最短路径问题为：在连通图中找到一条从节点1到节点n距离最短（或费用最低）的路径。求解此类最短路径问题，主要有以下几种算法：（1）Dijkstra算法

19、；（2）Floyd算法；（3）逐次逼近法6.4运输路线的选择1起、止点不同的单一路径规划1起、止点不同的单一路径规划例 某运输公司签订了一项运输合同，要把A市的一批货物运送到B市，该公司根据这两个城市之间可选择的行车路线的地图绘制了如图所示的公路网络。图中，圆圈也称节点，代表起点、目的地和与行车路线相交的其他城市。链代表两个结点之间的公路，每一条公路都标明运输里程。A市B市1起、止点不同的单一路径规划例 某运输公司签订了一项运输合解答：最短路的计算方法（1）找出第n个距起点最近的节点。对n=1,2,，重复此过程，直到所找出的最近节点是终点。（2）在前面的迭代过程中找出（n-1）个距起点最近的节

20、点，及其距起点最短的中径和距离，这些节点和起点统称为已解的节点，其余的称为未解节点。（3）每个已解的节点和一个或多外未解的节点相连接，就可以得出一个候选点连接距离最短的未解点。如果有多个距离相等的最短连接，则有多个候选点。（4）将每个已解节点与其候选点之间的距离累加到该已解节点与起点之间最短路径的距离上，所得出的总距离最短的候选点就是第n个最近的节点，其最短路径就是得出该距离的路径（若多个候选点都得出相等的最短距离，则都是已解节点）。解答：最短路的计算方法步骤直接连接到未解节点的已解节点与其直接连接的未解结点相关总成本第n个最近解点最小成本最新连接11123411241-22122345114

21、+7=114+2=6562-5312553446114+7=116+3=96+8=14495-4414453366119+1=109+4=136+8=143104-3534566610+2=129+4=136+8=146123-6通过上表的计算，最短路径为1-2-5-4-3-6，最短距离为12。步骤直接连接到未解节点的已解节点与其直接连接的未解结点相关总Floyd算法F算法的基本思路:F算法使用距离矩阵和路由矩阵。距离矩阵是一个nn矩阵，以图G的n个节点为行和列。记为W=wij n n， wij表示图G中vi和vj两点之间的路径长度。路由矩阵是一个nn矩阵，以图G的n个节点为行和列。记为R =

22、rij n n ，其中rij表示vi至vj经过的转接点（中间节点）。F算法的思路是首先写出初始的W阵和R阵，接着按顺序依次将节点集中的各个节点作为中间节点，计算此点距其他各点的径长，每次计算后都以求得的与上次相比较小的径长去更新前一次较大径长，若后求得的径长比前次径长大或相等则不变。以此不断更新和，直至W中的数值收敛。按顺序，依次作为中间节点，（按顺序，后面的点不作为中间节点）考察所有通过此中间节点的路径Floyd算法F算法的基本思路:1245310561543123451310235310615456454W0123451234521345312454123551234R0124531056

23、154312345131023512453105615431234513102313531013615456454W1123451234521145311454123551234R1124531056154312345131023131245310561543123451310823135310136154856454W2123451232521145311454223551234R212453105615431234513108231312453105615431234513108252313528310136154856454W3123451232321143311454223551234

24、R31245310561543123451310825231124531056154312345131081223115931011610485645129104D4123451232421444314444223554444S412453105615431234513108122312多个起、止点的路径规划当有多个货源和多个目的地时，就需要指定目的地的供货地，同时要找到供货地、目的地之间的最佳路径。例 某公司下属三个仓库，供应四个客户的需要，三个仓库的供应量和四个客户的需求量，以及由各仓库到各客户的运输单价如下表所示。求运输费用最少的运输方案。 销地客户1客户2客户3客户4供应量运价产地仓库

25、A311310700仓库B1928400仓库C74105900需求量30060050060020002多个起、止点的路径规划当有多个货源和多个目的地时，就需要表上做业法，该方法适合于对相对简单的问题进行求解，求解过程方便直观，而且由于计算量不大，可以用手工直接完成。利用表上作业法有两个基本步骤：（1）确定初始调运方案 最小元素法是按运价表依次挑选运费小的供-需点组合，尽量优先安排运费最低组合的方法。 3113101928734105 销地客户1客户2客户3客户4供应量运价产地仓库A400300700仓库B300100400仓库C600300900需求量300600500600表5.4 初始调运

26、方案表上做业法，该方法适合于对相对简单的问题进行求解，求解过程方（2）初始方案的检验最优方案的数字特征检验数：闭回路： 从理论上讲，对于表上作业法的初始方案来说，从调运方案表上的一个空格出发，存在一条且仅存在一条以该空格（用xij表示）为起点，以其他填有数字的点为其他顶点的闭合回路，简称闭回路。这个闭回路有以下性质：每个顶点都是转角点；闭合回路是一条封闭折线，每一条边都是水平或垂直的；每一行（列）若有闭合回路的顶点，则必有两个。 只有从空格出发，其余各转角点所对应的方格内均填写数字时，所构成的闭合回路才是我们所说的闭回路；另外，过任一空格的闭合回路不仅是存在的，而且是唯一的。（2）初始方案的检

27、验 销地客户1客户2客户3客户4供应量产地仓库A400300700仓库B300100400仓库C600300900需求量300600500600 表6.5给出了单元格（1，1）和（3，1）所形成的闭回路：（1，1）（1,3）(2，3)（2，1）（1，1）；（3，1）（2，1）（2，3）（1，3）（1，4）（3，4）（3，1）。其他空格的闭回路与此同理。 在调运方案内的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运费是增加还是减少。我们把所计算出来的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其为检验数。如果检验数小于0，表示在该空格的闭回路上调整运量会使运费减

28、少；相反，如果检验数大于0，则会使运费增加。表8.5 初始调运方案 销地客户1客户2客户3客户4供应量产地仓库A400用闭回路法求检验数时，需给每一空格找一条闭回路。当产销点很多时，这种计算很繁，可以用较为简便的方法“位势法”求解。设u1,u2,um；v1,v2,vn，是对应运输问题的m+n个约束条件的对偶变量。在初始调运方案中x13,x14,x21,x23,x32,x34是基变量，这时对应的检验数是：基变量 检验数x21 c21-( u2+v1)=0 设v1=0，并且c21=1 所以 u2=1x23 c23-(u2+v3)=0 2-( u2+v3)=0 x13 c13-(u1+v3)=0 3

29、-( u1+v3)=0 x14 c14-(u1+v4)=0 10-( u1+v4)=0 x34 c34-(u3+v4)=0 5-( u3+v4)=0 x22 c22-(u2+v2)=0 4-( u2+v2)=0用闭回路法求检验数时，需给每一空格找一条闭回路。当产销点很多通过这些方程可以求得u1=2 u2=1 u3= -3 v1=0 v2=7 v3=1 v4=8在初始解调运方案中增加一行一列，在列中填入ui,在行中填入vi。接着，按ij=cij-(ui+vj)计算所有空格的检验数。完成后的表格见表5.6。3113101928734105 销地客户1客户2客户3客户4ui运价产地仓库A12002仓

30、库B010-11仓库C100120-3vi0718表5.6 检验数表格通过这些方程可以求得3113101928734105 （3）方案调整 判定一个初始调运方案不是最优调运方案的标准，是在检验数表格中出现负值的检验数。如果检验数的负值不止个时，一般选择负检验数绝对值最大的空格作为具体调整对象。 从表5.6可以发现，单元格x24的检验数是负数，因此对其进行调整，具体过程如表5.7所示。x13400+100=500 x14300-100=200 x23100-100=0 x240+100=100表5.7 调动方案调整表 从单元格x24开始，沿闭回路在各奇数次转角点中挑选运量的最小数值作为调整量。在

31、此将x23单元格的100作为调整量，将亮个数填入单元格x24内，同时调整该闭回路中其他转角点上的运量，使各行、列保持原来的供需平衡，这样注得到一个新的调运方案，如表5.7所示。（3）方案调整x14x23x24表5.7 调动方案调整表 3113101928734105 销地客户1客户2客户3客户4供应量 运价产地仓库A500200700仓库B300100400仓库C600300900需求量300600500600表6.7 调整后的方案按新方案计算调运物资的运输费用为：3500+10200+8100+4600+5300=8500元新方案是否最优方案，还需再进行检验。经计算，该新方案的所有检验数都是

32、非负数，说明该方案已经是最优方案了。3113101928734105 销地客户1客户2客运输方案的改进的改进找出检验数ij为最小负值的格子的闭回路 在满足所有约束条件的情况下，尽可能增大这个格子的xij值 调整此闭回路上其他顶点的值 检验新解的最优性 重复上步骤直至得到最优解为止。运输方案的改进的改进找出检验数ij为最小负值的格子的闭回3起点和终点相同的路径规划起点和终点重合的路径问题一般被称为“旅行商”问题（TSP, Traveling Salesman Problem），是运筹学、图论和组合优化中的典型问题。 TSP问题一般描述如下：一个旅行者从出发地出发，经过所有要到达的城市后，返回到出

33、发地，要求合理安排其旅行路线，使得总旅行距离（或旅行费用、旅行时间等）最短。TSP问题特性：单一车辆无车辆容量限制求解复杂度属于NP-hard，大规模问题难以求得最佳解，现实中常采取”启发式方法(Heuristics)“求解3起点和终点相同的路径规划起点和终点重合的路径问题一般被称TSP问题数学规划模型 Mins.t.TSP问题数学规划模型 MinTSP问题求解算法真正解法(只能处理非常小的问题)Enumeration穷举法Assignment algorithm指派算法Littles method分枝定界法(Branch-and-Bound)传统启发式解法(Heuristics)大致可归纳为

34、以下三种：路线构建(route construction)邻点法、插入法.路线改善(route improvement)k-Opt交换法、Or-Opt交换法综合型(composite)合并执行路线构建及路线改善TSP问题求解算法真正解法(只能处理非常小的问题)Assignment Procedure For TSP1、将A到A，B到B,C到C的费用转换成无限大，以防止返回。Assignment Procedure For TSP1、Assignment Procedure For TSP2、应用指派问题的匈牙利算法，使得表中不同行、不同列都含有0此时，若完成路径的选择，最少的费用为9Assig

35、nment Procedure For TSP2、Assignment Procedure For TSP可行解尚未找到。此时考虑 增加一个“费用最小的非0路径” ，看看是否有可行解。得到：仍然没有可行解。此时考虑 再增加一个“费用最小的非0路径” ，或增加一个“费用次小的非0”路径看看是否有可行解。得到：Assignment Procedure For TSP可行Littles method分枝定界法(Branch-and-Bound)1、计算出所有不走“0费用”路径的惩罚成本2、选择惩罚成本最大的路径Littles method分枝定界法(Branch-an3、简化计算表，消除已经选择的路

36、径，形成新的计算表；继续分支定界。同时，为了防止返回，E到C设为；再检查是否每一行、每一列都有“0费用”路径，若没有在此行/列减去最小元素。E行减去1，得到：3、简化计算表，消除已经选择的路径，形成新的计算表；继续分支D同时，为了防止返回，E到B设为；再检查是否每一行、每一列都有“0费用”路径，若没有在此行/列减去最小元素。A列减去1，得到：D同时，为了防止返回，E到B设为；再检查是否每一行、每一列假设选择E,D路径，得到：假设选择E,D路径，得到：假设不选择E,D路径：假设不选择E,D路径：运输及配送路线的优化传统启发式解法1、最近邻点法(Nearest-neighbor Heuristic

37、)任选一节点为起点x寻找距离节点x最近的节点y作为下一个造访的节点寻找距离节点y最近的节点z作为下一个造访的节点重复以上步骤，直到所有节点均已造访连接最后一个节点与起点，即形成一个TSP的可行解传统启发式解法1、最近邻点法(Nearest-neighbo1、最近邻点法142357438755348142351234514738247553773443538585481、最近邻点法142357438755348142351232、插入法(Insertion Method)任选一节点为起点a寻找距离节点a最近的节点b作为下一个造访的节点，形成a-b-a的子回路寻找距离子回路最近的节点k作为下一个插

38、入点寻找插入成本最小的位置(i-j)，将k插入i-j之间，形成新的子回路。插入成本：Cik+Ckj-Cij重复步骤34，直到所有节点均已插入回路之中，即形成一个TSP的可行解2、插入法(Insertion Method)任选一节点为起2、插入法14235743875534814141333373337317224525727421455885845455582145542、插入法14235743875534814141333373、 2-opt 交换法先构建一个起始可行解在可行解中任选两个不相邻的节线(a b, c d)，以及另外两条对应之替换节线(a c, b d)，计算替换后总成本是否降低

39、 (即检查替换成本是否小于0)。替换成本：Cac+Cbd-Cab-Ccd (对称型TSP)若替换后总成本有降低，则予以替换，同时变更中间相关弧线的行走方向重复步骤23，直到所有可能的替换均无法再降低成本为止3、 2-opt 交换法先构建一个起始可行解3、 2-opt 交换法1423574387553483、 2-opt 交换法1423574387553484、常见的宏启发式方法(Meta-heuristics)禁忌搜索法(Tabu Search, TS)基因算法(Genetic Algorithm, GA)模拟退火法(Simulated Annealing, SA)门限值接受法(Thresho

40、ld Accepting, TA)神经网络(Neural Network, NN)蚁群算法(Ant Colony Optimization, ACO)其它4、常见的宏启发式方法(Meta-heuristics)禁忌6.4 车辆路线、时间安排车辆路线安排车辆路线安排问题（VRP, Vehicle Routing Problem）是指对物流配送的车辆进行优化调度。该问题一般可以描述如下：对一系列装货点或（和）卸货点，组织适当合理的行车路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、交发货时间、车辆容量、数目限制、车辆行驶里程、时间限制等）下，达到一定的目标（如最短路程、最

41、小费用、最短时间、最少车辆等）。该问题涉及了多辆交通工具的服务对象的选择和路径（服务顺序）确定两方面的问题 VRP问题是组合优化领域著名的NP难题之一，求解方法一般相当复杂，通常的做法是应用相关技术问题分解或者转化为一个或多个已经研究过的基本问题（如旅行商问题、指派问题、最短路问题等），再使用相对比较成熟的基本理论和方法进行求解。6.4 车辆路线、时间安排车辆路线安排运用VRP模型对实际问题进行研究时，一般需要考虑以下几个方面的问题：（1）仓库。仓库的级数，每级仓库的数量、地点和规模。（2）车辆。车辆的型号和数量，每种车辆的容积和运作费用，出发时间和返回时间，司机休息时间，最大的里程和时间限制

42、。（3）时间窗口。由于各处的工作时间不同，每个站点每天只允许在特定的时间内取货和/或送货。（4）顾客。顾客需求，装载、卸载，所处的地理位置，分离需求，优先等级。（5）道路信息。车流密度，道路交通费用，距离或时间属性。（6）货物信息。货物的种类多少，兼容性，货物的保鲜。（7）运输规章。工人每天的工作时间，车辆的周期维护。运用VRP模型对实际问题进行研究时，一般需要考虑以下几个方面（1）安排车辆负责相互距离最接近的站点的货物运输。（2）安排车辆各日途经站点时，应注意使站点群更加紧凑。如果一周内各日服务的站点不同，就应该对一周内每天的路线和时刻表问题分别进行站点群划分。各日站点群的划分应避免重叠。（

43、3）从距仓库最远的站点开始设计路线（4）卡车的行车路线应呈水滴状。（5）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的。（6）取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。（7）对过于遥远而无法归入群落的站点，可以采用其它配送方式。（8）避免时间窗口过短。简化的原则：（1）安排车辆负责相互距离最接近的站点的货物运输。简化的原则整数规划法（Integer Programming）启发式方法（Heuristics）节约法（Clarke and Wright Procedure）两阶段法 ETS (Extension of Traveling Salesman Procedu

44、re)扫描法考虑返程 Backtracking整数规划法（Integer Programming）1、整数规划法1、整数规划法运输及配送路线的优化运输及配送路线的优化运输及配送路线的优化2、节约法（Clarke and Wright Procedure） 节约法的目标是使所有车辆的行驶总里程最短，并且为所有站点提供服务的卡车数量最少。该方法先假设每一个站点都有一辆虚拟的车辆提供服务，随后返回仓库，如图(a)所示，这时的路线里程最长。下一步，将两个站点合并到同一条行车路线上，减少一辆运输车，相应地缩短路线里程，选择节约距离最多的一对站点合并在一起，修订后的路线如图(b)。d0,AdA,0d0,B

45、dB,0ABO仓库dA,Bd0,AdB,0a) 初始路线里程=dO,A+dA,O+dO,B+dB,Ob) 两个站点合并后的路线里程=dO,A+dA,B+dB,O 节约里程：dA,O+dB,O-dA,B2、节约法（Clarke and Wright Proced例：1、按距离中心的距离，从小到大排序2、计算出所有两点间的节省距离，写在左边Capacity of a Truck =153、按照节约量，从大到小选取路线，同时满足装载量卡车容量例：1、按距离中心的距离，从小到大排序2、计算出所有两点间的4、形成一条路线，划去已经过的节点，继续寻找其他路线4、形成一条路线，划去已经过的节点，继续寻找其他

46、路线两阶段法 ETS (Extension of Traveling Salesman Procedure)第一阶段：1、找到由TSP问题确定的行走路径；2、根据货车容量，初步给出各条货车的行驶路径。第二阶段：根据货车的剩余容量（Slack），对初步行驶路径进行调整。例：Capacity of a Truck =10两阶段法 ETS (Extension of TravelThe traveling salesman route is O-B-A-E-C-D-O根据货车容量限制，初步给出各条货车的行驶路径，同时保证节省距离0第一阶段：The traveling salesman route i运输及配送路线的优化第二阶段：从剩余容量（Slack）最大的线路开始，进行节点的交换调整，并计算节点交换后的节约里程数，若为正，则可交换节点。剩余容量（Slack）最大的线路：O-E-O考虑E点相邻的A点和C点。将C点交换到O-E-O路径，则节省路程：第二阶段：从剩余容量（Slack）最大的线路开始，进行节点的调整后的路线：剩余容量（Slack）最大的线路：O-B-O结果与节约法计算的一样。与节约法相比，对于小规模问题，ETS法计算量较小。调整后的路线：剩余容量