1、六、运输决策及配送路线的优化六、运输决策及配送路线的优化6.1运输系统的重要性与功能运输系统的重要性与功能6.2基本运输方式及其运营特点基本运输方式及其运营特点6.3运输合理化运输合理化6.4运输路线的选择运输路线的选择6.5车辆路线、时间安排车辆路线、时间安排6.1运输系统的重要性与功能运输系统的重要性与功能q运输运输指借助公共运输线及其设施和运输工具来实现人指借助公共运输线及其设施和运输工具来实现人与物空间位移的一种经济活动和社会活动。与物空间位移的一种经济活动和社会活动。q交通交通与运输反映的同一过程的两个方面。与运输反映的同一过程的两个方面。v 同一过程：运输工具在运输网路上的流动；同
2、一过程：运输工具在运输网路上的流动；v 两个方面：两个方面：v 交通关心的是运输工具的流动情况交通关心的是运输工具的流动情况(流量的大小、拥挤的程度流量的大小、拥挤的程度)v 运输关心的是流动中的运输工具上的载运情况运输关心的是流动中的运输工具上的载运情况(载人与物的有无与载人与物的有无与多少，将其输送了多远的距离多少，将其输送了多远的距离)v 运输是交通的目的运输是交通的目的q运输系统的重要性运输系统的重要性v 地域分工专业化地域分工专业化v 规模经济规模经济v 竞争加剧竞争加剧v 土地价值的提高土地价值的提高q交通运输系统的构成要素：v（1）运载工具（2）通路（3）场站（4）动力（5）通信
3、（6）经营管理人员和经营机构q产品转移v运输克服了产品在生产与需求之间存在的空间和时间上的差异。q产品存储v对产品进行临时存储是指将运输车辆临时作为相当昂贵的存储设施。运输的功能运输的功能运输服务的特征运输服务的特征q运输服务是一种特殊的产品：运输服务是一种特殊的产品：v运输服务产品具有无形性运输服务产品具有无形性v运输服务的生产和消费不可分离运输服务的生产和消费不可分离v运输服务具有不可存储性运输服务具有不可存储性v异质性，即同一种服务的质量差别异质性，即同一种服务的质量差别 6.2 运输方式及其特征运输方式及其特征一、铁路运输一、铁路运输q铁路是国民经济的大动脉，铁路运输是我国货物运输的主
4、要铁路是国民经济的大动脉，铁路运输是我国货物运输的主要方式。铁路运输的主要特点是能够远距离运输大量货物。由方式。铁路运输的主要特点是能够远距离运输大量货物。由于世界上几乎所有的大都市、我国的绝大部分城市都通铁路，于世界上几乎所有的大都市、我国的绝大部分城市都通铁路，铁路在国际、国内运输中占有相当大的市场份额。铁路在国际、国内运输中占有相当大的市场份额。q虽然设备和站点等的限制使得铁路运营的固定成本很高，但虽然设备和站点等的限制使得铁路运营的固定成本很高，但是铁路运营的变动成本（如维修、管理、耗能等）相对较低，是铁路运营的变动成本（如维修、管理、耗能等）相对较低，这也使得铁路运输的总成本通常比公
5、路和航空运输低。这也使得铁路运输的总成本通常比公路和航空运输低。q高固定成本和低变动成本使铁路运输的规模经济十分明显。铁路运输铁路运输铁路运输方式的铁路运输方式的主要优点：q运输能力大运输能力大 q运行速度较快，时速一般运行速度较快，时速一般在在8080120120公里公里 q适应性强，受天气限制条适应性强，受天气限制条件少，安全可靠性高件少，安全可靠性高 q运输成本低运输成本低 q环境污染小，环境成本低环境污染小，环境成本低 铁路运输方式的铁路运输方式的主要缺点 ：q灵活性差灵活性差q对包装的要求较高对包装的要求较高q存在货物被偷盗的危险存在货物被偷盗的危险q铁路设施修建成本较高，铁路设施修
6、建成本较高，占地多。占地多。6.2 6.2 运输方式及其特征运输方式及其特征二、公路运输二、公路运输q公路运输具有规模巨大，分布极广的道路基础设施体系和公路运输具有规模巨大，分布极广的道路基础设施体系和机动灵活、适应性强的车辆装备系统。大多数的消费品都机动灵活、适应性强的车辆装备系统。大多数的消费品都是通过公路运输的。是通过公路运输的。q公路运输是任何公司物流系统中重要的一部分。q公路运输的固定成本很低。汽车承运人在固定基础设施的公路运输的固定成本很低。汽车承运人在固定基础设施的投资相对较少，多数公路的建设运营由政府进行。投资相对较少，多数公路的建设运营由政府进行。q公路运输的变动成本相对较高
7、，因为公路的建设和维修费公路运输的变动成本相对较高，因为公路的建设和维修费用经常是以税收和收费站的形式向承运人征收的。此外，用经常是以税收和收费站的形式向承运人征收的。此外，汽车的能耗、维修费用相对也比较高。汽车的能耗、维修费用相对也比较高。q燃油税燃油税公路运输公路运输 公路运输方式的主要优点：公路运输方式的主要优点：q原始投资少，资金周转快，原始投资少，资金周转快，投资回收期短投资回收期短q机动灵活，门对门运输机动灵活，门对门运输 q快捷可控快捷可控 q包装成本低，货物损失小包装成本低，货物损失小 公路运输的主要缺点公路运输的主要缺点 ：q运输能力小运输能力小q劳动生产率低，单位运价劳动生
8、产率低，单位运价高高 q公路拥挤与污染，环境成公路拥挤与污染，环境成本高本高 公路运输不像其它运输方式那样受到各种线路的限制，其市场覆盖面要高于其它运输方式。公路运输的特点使得公路运输尤其适于短距离、高价值产品的装运，在中间产品和轻工产品的运输方面有较大的优势。6.26.2运输方式及其特征运输方式及其特征三、水路运输三、水路运输q水路运输在世界外贸运输中始终保持主导地位，在经济合作水路运输在世界外贸运输中始终保持主导地位，在经济合作和交流中起着纽带作用。和交流中起着纽带作用。q受自然条件的制约，水路运输的运营范围和运输速度受到限受自然条件的制约，水路运输的运营范围和运输速度受到限制，但是却有其
9、它运输方式不可比拟的优势和潜力。制，但是却有其它运输方式不可比拟的优势和潜力。q水运中水道的改良维护通常由政府负责，港口的开发和维护水运中水道的改良维护通常由政府负责，港口的开发和维护各国不同，但一般也由政府统一进行，而运输公司只需支付各国不同，但一般也由政府统一进行，而运输公司只需支付一定的费用就可以使用港口和其它码头设施。一定的费用就可以使用港口和其它码头设施。q水路运输的水路运输的，主要包括运营中的成本，其规模主要包括运营中的成本，其规模经济的效应更加明显。经济的效应更加明显。水路运输水路运输 水路运输方式的主要优点：水路运输方式的主要优点：q单位运输工具的装载量大，单位运输工具的装载量
10、大，运输能力高，运输距离长运输能力高，运输距离长 q水路运输成本低，基础设水路运输成本低，基础设施投资节省，单位运价低施投资节省，单位运价低廉廉 q能源消耗少能源消耗少 水路运输方式的主要缺点：水路运输方式的主要缺点：q运输速度慢运输速度慢 q受天气和其它自然条件影受天气和其它自然条件影响大，线路迂回响大，线路迂回 q货物破损较多货物破损较多 q可靠性差可靠性差 与上述特点相对应，水路运输适于运送数量巨大、低价值、时效性要求不高的货物，如矿石、煤炭、石油农产品等。水路运输是大宗货物长距离运输的理想选择。6.2 6.2 运输方式及其特征运输方式及其特征四、航空运输四、航空运输q航空货运的主要优点
11、在于运输速度快。航空货运的主要优点在于运输速度快。q随着航空运输技术的不断成熟，航空运输在远距离运输，特随着航空运输技术的不断成熟，航空运输在远距离运输，特别是跨国运输中显示出无可比拟的优势。别是跨国运输中显示出无可比拟的优势。q只有在运输高价值的和对时效性要求高于对成本要求的产品只有在运输高价值的和对时效性要求高于对成本要求的产品时，航空运输才有其合理性。时，航空运输才有其合理性。q航空的固定成本较低。空中航线和管制系统由国家拥有，航航空的固定成本较低。空中航线和管制系统由国家拥有，航空港的建设运营由国家投资，航空公司的固定成本主要与购空港的建设运营由国家投资，航空公司的固定成本主要与购买飞
12、机有关，也与所需的搬运系统和货物集装箱有关。买飞机有关，也与所需的搬运系统和货物集装箱有关。q航空运输的变动成本是极高的，其燃料消耗、飞行器的维修航空运输的变动成本是极高的，其燃料消耗、飞行器的维修保养以及飞行人员和地勤人员的费用都是一笔可观的支出。保养以及飞行人员和地勤人员的费用都是一笔可观的支出。航空运输航空运输航空运输的主要优点：航空运输的主要优点：q运行速度快运行速度快 q灵活、机动性大灵活、机动性大 q航空运输服务质量高、安航空运输服务质量高、安全可靠全可靠 航空运输的主要缺点：航空运输的主要缺点：q运输成本高运输成本高 q运输能力小运输能力小 q有些货物禁用空运有些货物禁用空运 q
13、受天气影响较大受天气影响较大 综合上述优缺点，航空运输适用于长途旅客运输和紧急需要的、时效性要求高的、单位价值高的货物运输。6.2 运输方式及其特征运输方式及其特征q五、管道运输五、管道运输q管道是很独特的运输方式，它所能运送的货物种类很有限，管道是很独特的运输方式，它所能运送的货物种类很有限，主要通过管道运输的货物是：石油及成品油、天然气、化主要通过管道运输的货物是：石油及成品油、天然气、化学制品。学制品。q管道运输的优势：管道运输的优势：v 费用低。费用低。v 货损、货差率低。货损、货差率低。v 另外，因为管道运输速度很慢，还可以将管道作为仓库。另外，因为管道运输速度很慢，还可以将管道作为
14、仓库。v 可靠性好、不受天气影响、很少有机械故障可靠性好、不受天气影响、很少有机械故障q管道运输的缺点：管道运输的缺点：v 管道线路是相对固定的，因此有地域灵活性或可达性的限制。管道线路是相对固定的，因此有地域灵活性或可达性的限制。v 管道运输的产品有局限性，并且只能提供单向服务。管道运输的产品有局限性，并且只能提供单向服务。各种运输方式技术经济特征比较表各种运输方式技术经济特征比较表运输方运输方式式基建投资基建投资运载运载量量运输成运输成本本速速度度连续连续性性灵活灵活性性生产生产率率安全安全性性线路线路运具运具铁路铁路6 62 22 24 43 31 13 34 43 3河运河运3 34
15、43 32 26 66 64 42 24 4海运海运1 13 31 11 15 55 55 51 15 5公路公路4 45 55 55 52 22 21 16 66 6管道管道5 51 14 43 34 43 36 63 31 1航空航空2 26 66 66 61 14 42 25 52 2 注：表中数字表示各种运输方式在某一方面的优劣次序。注：表中数字表示各种运输方式在某一方面的优劣次序。影响运输决策的成本因素影响运输决策的成本因素q影响承运人定价的成本因素影响承运人定价的成本因素v与运距有关的成本与运距有关的成本v与运量有关的成本与运量有关的成本v与速度有关的成本与速度有关的成本直送v.s
16、中转q影响承运人运力组合的成本因素影响承运人运力组合的成本因素v固定成本固定成本v运营成本运营成本运输特性运输特性q规模规模特性特性q随着一次装运量的增大，使每单位重量的运输成本下降。随着一次装运量的增大，使每单位重量的运输成本下降。q距离距离特性特性q随着一次运输距离的增加，运输费用的增加会变的越来越缓慢，或者随着一次运输距离的增加，运输费用的增加会变的越来越缓慢，或者说单位运输距离的费用减少，运输成本与一次运输的距离有关。说单位运输距离的费用减少，运输成本与一次运输的距离有关。q速度速度特性特性q完成特定的运输所需的时间越短，其效用价值越高。完成特定的运输所需的时间越短，其效用价值越高。单
17、位货物运输成本运输距离单位货物运输成本装载重量运输效用送达时间影响承运人运力组合的成本因素影响承运人运力组合的成本因素qn 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)qv the decision variable corresponding to the number of owned vehiclesqvt,t=1,.,n,the required number
18、 of vehicles at time period t;qm the number of time periods per year in which vt v.qcF fixed cost（an owned vehicle）qcV variable cost（an owned vehicle）qcH be the cost per time period of hiring a vehicle(clearly,c F+c V c H).qAs the two summations in Equation are equal to the areas below and above the
19、 line vt=v,respectively,then their derivatives are equal to m and m,respectively.qConsequently,C(v)is minimal when影响托运人决策的成本因素影响托运人决策的成本因素v服务水平成本（运输时间-速度）v运输成本（运输方式、运输规模）v库存成本v交易成本运输服务的选择运输服务的选择q 的影响是决策者心目中的影响是决策者心目中最重要的运输服务要素，因此，这三项是运输服最重要的运输服务要素，因此，这三项是运输服务选择的基础。务选择的基础。q运输对库存的影响有以下几点：运输对库存的影响有以下几点
20、：q在选择运输方式时，就需要考虑库存持有成本可在选择运输方式时，就需要考虑库存持有成本可能升高，而抵消运输服务成本降低的情况。能升高，而抵消运输服务成本降低的情况。运输服务的选择的定量分析法运输服务的选择的定量分析法q基于运输成本与库存成本的总成本分析方法基于运输成本与库存成本的总成本分析方法v【例例】某公司欲将产品从位置某公司欲将产品从位置A的工厂运往位的工厂运往位置置B的公司自有仓库，年运量的公司自有仓库，年运量D=700000件，产件，产品价值品价值C=30元，年存货成本元，年存货成本I=产品价格的产品价格的30。公司希望选择使总成本最小的运输方式。据估公司希望选择使总成本最小的运输方式
21、。据估计，运输时间每减少一天，平均库存成本可以计，运输时间每减少一天，平均库存成本可以减少减少1。各种运输服务方式的有关参数见表：。各种运输服务方式的有关参数见表：运输服务的选择的定量分析法运输服务的选择的定量分析法运输方式运输方式 费率费率R(元元/件件)时间时间T(天天)年运送批年运送批次次 平均存货平均存货量量Q/2 铁路铁路 0.12110100000水运水运 0.15142046500公路公路 0.252042000航空航空1.424020250运输服务的选择的定量分析法运输服务的选择的定量分析法q分析：分析：v以年总成本最低为原则来选择合适的运输方式。这里，以年总成本最低为原则来选
22、择合适的运输方式。这里，总成本总成本=运输费用运输费用+库存成本；库存成本；v其中，其中，运输费用运输费用=运输量运输量 费率费率v库存成本库存成本=在途运输库存成本在途运输库存成本+工厂存货成本工厂存货成本+仓库存货仓库存货成本成本v在途运输库存费用在途运输库存费用=ICDT/365v工厂存货成本工厂存货成本=ICQ/2v仓库存货成本仓库存货成本=I（C+R）Q/2v代入各种运输方式的基本数据信息，将相应的成本计算代入各种运输方式的基本数据信息，将相应的成本计算结果列入表结果列入表2。vD年运量；年运量；C产品单价；产品单价；I年存货成本（产品价格年存货成本（产品价格的的30）；）；vT运输
23、时间；运输时间；R费率费率(元元/件件)；Q/2平均存货量平均存货量二、运输方式选择的定量分析法二、运输方式选择的定量分析法由表中结果可知，总成本最低的是公路运输方式，总成本为由表中结果可知，总成本最低的是公路运输方式，总成本为984821元，其次是水路运输，成本最高的是铁路运输。按照元，其次是水路运输，成本最高的是铁路运输。按照总成本最低的原则，适合选择公路运输方式。总成本最低的原则，适合选择公路运输方式。成本类成本类型型 计算公式计算公式 铁路运输铁路运输 水路运输水路运输 公路运输公路运输 航空运输航空运输 运输成运输成本本 R D 70000105000140000980000在途库在
24、途库存存 ICDT/365 345205241644 8630134521工厂存工厂存货货 ICQ/2 900000416500378000182250仓库存仓库存货货 I(C+R)Q/2903000420593380520190755总成本总成本 2218205118573798482113875266.4运输路线的选择运输路线的选择q1 1起、止点不同的单一路径规划起、止点不同的单一路径规划q2 2多个起、止点的路径规划多个起、止点的路径规划q3 3起点和终点相同的路径规划起点和终点相同的路径规划vTraveling Salesman Problem(TSP)Traveling Sales
25、man Problem(TSP)vVehicle Routing Problem(VRP)Vehicle Routing Problem(VRP)6.4运输路线的选择运输路线的选择q1起、止点不同的单一路径规划起、止点不同的单一路径规划q这类路径规划问题称为最短路问题。最短路径问题是线路优化模型理论中最为基础的问题之一。q问题描述：假设有一n个节点和m条弧的连通图G（Vn,Em),并且图中的每条弧（i,j)都有一个长度cij(或者费用cij)，q求解此类最短路径问题，主要有以下几种算法：q（1）Dijkstra算法；（2）Floyd算法；（3）逐次逼近法1起、止点不同的单一路径规划起、止点不同
26、的单一路径规划例例 某运输公司签订了一项运输合同，要把A市的一批货物运送到B市，该公司根据这两个城市之间可选择的行车路线的地图绘制了如图所示的公路网络。图中，圆圈也称节点，代表起点、目的地和与行车路线相交的其他城市。链代表两个结点之间的公路，每一条公路都标明运输里程。A市市B市市解答：最短路的计算方法解答：最短路的计算方法（1 1）找出第）找出第n n个距起点最近的节点。对个距起点最近的节点。对n=1,2,n=1,2,，重复此过程，直到所，重复此过程，直到所找出的最近节点是终点。找出的最近节点是终点。（2 2）在前面的迭代过程中找出（）在前面的迭代过程中找出（n-1n-1）个距起点最近的节点，
27、及其距起）个距起点最近的节点，及其距起点最短的中径和距离，这些节点和起点统称为已解的节点，其余的称为点最短的中径和距离，这些节点和起点统称为已解的节点，其余的称为未解节点。未解节点。（3 3）每个已解的节点和一个或多外未解的节点相连接，就可以得出一）每个已解的节点和一个或多外未解的节点相连接，就可以得出一个候选点个候选点连接距离最短的未解点。如果有多个距离相等的最短连接，连接距离最短的未解点。如果有多个距离相等的最短连接，则有多个候选点。则有多个候选点。（4 4）将每个已解节点与其候选点之间的距离累加到该已解节点与起点）将每个已解节点与其候选点之间的距离累加到该已解节点与起点之间最短路径的距离
28、上，所得出的总距离最短的候选点就是第之间最短路径的距离上，所得出的总距离最短的候选点就是第n n个最近个最近的节点，其最短路径就是得出该距离的路径（若多个候选点都得出相等的节点，其最短路径就是得出该距离的路径（若多个候选点都得出相等的最短距离，则都是已解节点）。的最短距离，则都是已解节点）。通过上表的计算，最短路径为通过上表的计算，最短路径为1-2-5-4-3-6，最短距离为，最短距离为12。FloydFloyd算法算法qF F算法的基本思路算法的基本思路:qF算法使用距离矩阵距离矩阵和路由矩阵路由矩阵。q距离矩阵距离矩阵是一个nn矩阵，以图G的n个节点为行和列。记为W=w wijij n n
29、，w wijij表示图G中vi和vj两点之间的路径长度。q路由矩阵路由矩阵是一个nn矩阵，以图G的n个节点为行和列。记为R=r rijij n n，其中r rijij表示vi至vj经过的转接点（中间节点）。qF算法的思路是首先写出初始的W阵和R阵，接着按顺序依次将节点集中的各个节点作为中间节点，计算此点距其他各点的径长，每次计算后都以求得的与上次相比较小的径长去更新前一次较大径长，若后求得的径长比前次径长大或相等则不变。以此不断更新和，直至W中的数值收敛。q按顺序，依次作为中间节点，（按顺序，后面的点不作为（按顺序，后面的点不作为中间节点）中间节点）q考察所有所有通过此中间节点的路径12453
30、10561543123451310235310615456454W0123451234521345312454123551234R012453105615431234513102313531013615456454W1123451234521145311454123551234R11245310561543123451310823135310136154856454W2123451232521145311454223551234R212453105615431234513108252313528310136154856454W3123451232321143311454223551234R31
31、24531056154312345131081223115931011610485645129104D4123451232421444314444223554444S42多个起、止点的路径规划当有多个货源和多个目的地时，就需要指定目的地的供货地，同时当有多个货源和多个目的地时，就需要指定目的地的供货地，同时要找到供货地、目的地之间的最佳路径。要找到供货地、目的地之间的最佳路径。例例 某公司下属三个仓库，供应四个客户的需要，三个仓库的供应量某公司下属三个仓库，供应四个客户的需要，三个仓库的供应量和四个客户的需求量，以及由各仓库到各客户的运输单价如下表所示。和四个客户的需求量，以及由各仓库到各客户
32、的运输单价如下表所示。求运输费用最少的运输方案。求运输费用最少的运输方案。销地销地客户客户1客户客户2客户客户3客户客户4供应量供应量运价运价产地产地仓库仓库A311310700仓库仓库B1928400仓库仓库C74105900需求量需求量3006005006002000表上做业法表上做业法，该方法适合于对相对简单的问题进行求解，求解过程方便，该方法适合于对相对简单的问题进行求解，求解过程方便直观，而且由于计算量不大，可以用手工直接完成。利用表上作业法有两直观，而且由于计算量不大，可以用手工直接完成。利用表上作业法有两个基本步骤：个基本步骤：（1 1）确定初始调运方案）确定初始调运方案 最小元
33、素法是按运价表依次挑选运费小的供最小元素法是按运价表依次挑选运费小的供-需点组合，尽量优需点组合，尽量优先安排运费最低组合的方法。先安排运费最低组合的方法。3113101928734105 销销地地客户客户1客户客户2客户客户3客户客户4供应量供应量运价运价产地产地仓库仓库A400300700仓库仓库B300100400仓库仓库C600300900需求量需求量300600500600表表5.4 初始调运方案初始调运方案（2 2）初始方案的检验）初始方案的检验最优方案的数字特征最优方案的数字特征检验数：检验数：闭回路：闭回路：从理论上讲，对于表上作业法的初始方案来说，从调运方案从理论上讲，对于表
34、上作业法的初始方案来说，从调运方案表上的一个空格出发，存在一条且仅存在一条以该表上的一个空格出发，存在一条且仅存在一条以该空格空格（用（用xijxij表表示）为起点，以示）为起点，以其他填有数字的点其他填有数字的点为其他顶点的闭合回路，简称闭为其他顶点的闭合回路，简称闭回路。这个闭回路有以下性质：回路。这个闭回路有以下性质：每个顶点都是转角点；每个顶点都是转角点；闭合回路是一条封闭折线，每一条边都是水平或垂直的；闭合回路是一条封闭折线，每一条边都是水平或垂直的；每一行（列）若有闭合回路的顶点，则必有两个。每一行（列）若有闭合回路的顶点，则必有两个。只有从空格出发，其余各转角点所对应的方格内均填
35、写数字时，只有从空格出发，其余各转角点所对应的方格内均填写数字时，所构成的闭合回路才是我们所说的闭回路；另外，过任一空格的闭所构成的闭合回路才是我们所说的闭回路；另外，过任一空格的闭合回路不仅是存在的，而且是唯一的。合回路不仅是存在的，而且是唯一的。销地销地客户客户1客户客户2客户客户3客户客户4供应量供应量产地产地仓库仓库A400300700仓库仓库B300100400仓库仓库C600300900需求量需求量300600500600 表表6.56.5给出了单元格（给出了单元格（1 1，1 1）和（）和（3 3，1 1）所形成的闭回路：（）所形成的闭回路：（1 1，1 1）（1,31,3）(2
36、(2，3)3)（2 2，1 1）（1 1，1 1）；（）；（3 3，1 1）（2 2，1 1）（2 2，3 3）（1 1，3 3）（1 1，4 4）（3 3，4 4）（3 3，1 1）。其他空格的闭回路与此同）。其他空格的闭回路与此同理。理。在调运方案内的每个空格所形成的闭回路上，作单位物资的运量调整，在调运方案内的每个空格所形成的闭回路上，作单位物资的运量调整，总可以计算出相应的运费是增加还是减少。我们把所计算出来的每条闭回路上总可以计算出相应的运费是增加还是减少。我们把所计算出来的每条闭回路上调整单位运量而使运输费用发生变化的增减值，称其为检验数。调整单位运量而使运输费用发生变化的增减值，
37、称其为检验数。如果检验数小如果检验数小于于0 0，表示在该空格的闭回路上调整运量会使运费减少；相反，如果检验数大，表示在该空格的闭回路上调整运量会使运费减少；相反，如果检验数大于于0 0，则会使运费增加。，则会使运费增加。表8.5 初始调运方案用闭回路法求检验数时，需给每一空格找一条闭回路。当产销点很多时，这种计算很繁，可以用较为简便的方法可以用较为简便的方法“位势法位势法”求解。求解。设u1,u2,um；v1,v2,vn，是对应运输问题的m+n个约束条件的对偶变量。在初始调运方案中x13,x14,x21,x23,x32,x34是基变量，这时对应的检验数是：基变量基变量 检验数检验数x21 c
38、21-(u2+v1)=0 x21 c21-(u2+v1)=0 设设v1=0v1=0，并且，并且c21=1 c21=1 所以所以 u2=1u2=1x23 c23-(u2+v3)=0 2-(u2+v3)=0 x23 c23-(u2+v3)=0 2-(u2+v3)=0 x13 c13-(u1+v3)=0 3-(u1+v3)=0 x13 c13-(u1+v3)=0 3-(u1+v3)=0 x14 c14-(u1+v4)=0 10-(u1+v4)=0 x14 c14-(u1+v4)=0 10-(u1+v4)=0 x34 c34-(u3+v4)=0 5-(u3+v4)=0 x34 c34-(u3+v4)=
39、0 5-(u3+v4)=0 x22 c22-(u2+v2)=0 4-(u2+v2)=0 x22 c22-(u2+v2)=0 4-(u2+v2)=0通过这些方程可以求得通过这些方程可以求得u1=2 u2=1 u3=-3 v1=0 v2=7 v3=1 v4=8u1=2 u2=1 u3=-3 v1=0 v2=7 v3=1 v4=8在初始解调运方案中增加一行一列，在初始解调运方案中增加一行一列，在列中填入在列中填入ui,ui,在行中填入在行中填入vivi。接着，。接着，按按ij=cij-(ui+vj)ij=cij-(ui+vj)计算所有空格的检验数。完成后的表格见表计算所有空格的检验数。完成后的表格见
40、表5.65.6。3113101928734105 销地销地客户客户1客户客户2客户客户3客户客户4ui运价运价产地产地仓库仓库A12002仓库仓库B010-11仓库仓库C100120-3vi0718表表5.6 检验数表格检验数表格（3 3）方案调整）方案调整 判定一个初始调运方案不是最优调运方案的标准，是在检验数表格中判定一个初始调运方案不是最优调运方案的标准，是在检验数表格中出现负值的检验数。如果检验数的负值不止个时，一般选择负检验数绝对出现负值的检验数。如果检验数的负值不止个时，一般选择负检验数绝对值最大的空格作为具体调整对象。值最大的空格作为具体调整对象。从表从表5.65.6可以发现，单
41、元格可以发现，单元格x x2424的检验数是负数，因此对其进行调整，的检验数是负数，因此对其进行调整，具体过程如表具体过程如表5.75.7所示。所示。x13400+100=500 x14300-100=200 x23100-100=0 x240+100=100表表5.7 5.7 调动方案调整表调动方案调整表 从单元格从单元格x x2424开始，沿闭回路在各奇数次转角点中挑选运量的最小数值开始，沿闭回路在各奇数次转角点中挑选运量的最小数值作为调整量。在此将作为调整量。在此将x x2323单元格的单元格的100100作为调整量，将亮个数填入单元格作为调整量，将亮个数填入单元格x x2424内，内，
42、同时调整该闭回路中其他转角点上的运量，使各行、列保持原来的供需平衡，同时调整该闭回路中其他转角点上的运量，使各行、列保持原来的供需平衡，这样注得到一个新的调运方案，如表这样注得到一个新的调运方案，如表5.75.7所示。所示。3113101928734105 销地客户客户1客户客户2客户客户3客户客户4供应量供应量 运价产地仓库仓库A500200700仓库仓库B300100400仓库仓库C600300900需求量需求量300600500600表表6.7 6.7 调整后的方案调整后的方案按新方案计算调运物资的运输费用为：按新方案计算调运物资的运输费用为：3 3500+10500+10200+820
43、0+8100+4100+4600+5600+5300=8500300=8500元元新方案是否最优方案，还需再进行检验。经计算，该新方案新方案是否最优方案，还需再进行检验。经计算，该新方案的所有检验数都是非负数，说明该方案已经是最优方案了。的所有检验数都是非负数，说明该方案已经是最优方案了。找出检验数找出检验数 ij为最小负值的格子的闭回路为最小负值的格子的闭回路 在满足所有约束条件的情况下，尽可能增大这在满足所有约束条件的情况下，尽可能增大这个格子的个格子的xij值值 调整此闭回路上其他顶点的值调整此闭回路上其他顶点的值 检验新解的最优性检验新解的最优性 重复上步骤直至得到最优解为止。重复上步
44、骤直至得到最优解为止。3起点和终点相同的路径规划起点和终点相同的路径规划起点和终点重合的路径问题一般被称为起点和终点重合的路径问题一般被称为“旅行商旅行商”问题（问题（TSP,TSP,Traveling Salesman ProblemTraveling Salesman Problem），是运筹学、图论和组合优化中的），是运筹学、图论和组合优化中的典型问题。典型问题。TSPTSP问题一般描述如下：问题一般描述如下：一个旅行者从出发地出发，经过所有要到达的城市后，返回到出发一个旅行者从出发地出发，经过所有要到达的城市后，返回到出发地，要求合理安排其旅行路线，地，要求合理安排其旅行路线，使得总旅
45、行距离（或旅行费用、旅使得总旅行距离（或旅行费用、旅行时间等）最短。行时间等）最短。TSPTSP问题特性：问题特性：p单一车辆单一车辆p无车辆容量限制无车辆容量限制p求解复杂度属于求解复杂度属于NP-hard，大规模问题难以求得最佳解，现，大规模问题难以求得最佳解，现实中常采取实中常采取”启发式方法启发式方法(Heuristics)“求解求解TSPTSP问题数学规划模型问题数学规划模型 Mins.t.ijijijxcAin allfor 1,011ijxNjxNixijiijjijTSPTSP问题求解算法问题求解算法q真正解法真正解法(只能处理非常小的问题只能处理非常小的问题)vEnumera
46、tion穷举法穷举法vAssignment algorithm指派算法指派算法vLittles method分枝定界法分枝定界法(Branch-and-Bound)q传统启发式解法传统启发式解法(Heuristics)大致可归纳为以下三大致可归纳为以下三种：种：v路线构建路线构建(route construction)邻点法、插入法.v路线改善路线改善(route improvement)k-Opt交换法、Or-Opt交换法v综合型综合型(composite)合并执行路线构建及路线改善Assignment Procedure For TSP1 1、将、将A A到到A A，B B到到B,CB,C
47、到到C C的费用转换成无限的费用转换成无限大，以防止返回。大，以防止返回。Assignment Procedure For TSPq2、应用指派问、应用指派问题的匈牙利算题的匈牙利算法，使得表中法，使得表中不同行、不同不同行、不同列都含有列都含有0q此时，若完成此时，若完成路径的选择，路径的选择，最少的费用为最少的费用为9Assignment Procedure For TSPq可行解尚未找到。可行解尚未找到。q此时考虑此时考虑 增加一增加一个个“费用最小的费用最小的非非0路径路径”，看，看看是否有可行解。看是否有可行解。得到：得到：仍然没有可行解。仍然没有可行解。此时考虑此时考虑 再再增加一
48、个增加一个“费用最小的非费用最小的非0 0路径路径”，或增加一个或增加一个“费用次小的费用次小的非非0 0”路径看看是否有可行路径看看是否有可行解。解。得到：得到：Littles method分枝定界法分枝定界法(Branch-and-Bound)q1、计算出所有不、计算出所有不走走“0费用费用”路径路径的惩罚成本的惩罚成本q2、选择惩罚成本、选择惩罚成本最大的路径最大的路径q3、简化计算表，消除已经选择的路径，形成新的计算表；、简化计算表，消除已经选择的路径，形成新的计算表；继续分支定界。继续分支定界。同时，为了防止返回，同时，为了防止返回，E到到C设为设为；再检查是否每一行、每；再检查是否
49、每一行、每一列都有一列都有“0费用费用”路径，若没有在此行路径，若没有在此行/列减去最小元素。列减去最小元素。E行减去行减去1，得到：，得到：D同时，为了防止返回，同时，为了防止返回，E到到B设为设为；再检查是否每一行、每；再检查是否每一行、每一列都有一列都有“0费用费用”路径，若没有在此行路径，若没有在此行/列减去最小元素。列减去最小元素。A列减去列减去1，得到：，得到：假设选择假设选择E,D路径，得到：路径，得到：假设不选择假设不选择E,D路径：路径：传统启发式解法传统启发式解法q1、最近邻点法、最近邻点法(Nearest-neighbor Heuristic)1.任选一节点为起点任选一节
50、点为起点x2.寻找距离节点寻找距离节点x最近的节点最近的节点y作为下一个造访的节点作为下一个造访的节点3.寻找距离节点寻找距离节点y最近的节点最近的节点z作为下一个造访的节点作为下一个造访的节点4.重复以上步骤，直到所有节点均已造访重复以上步骤，直到所有节点均已造访5.连接最后一个节点与起点，即形成一个连接最后一个节点与起点，即形成一个TSP的可行解的可行解1、最近邻点法、最近邻点法142357438755348142351234514738247553773443538585482、插入法插入法(Insertion Method)(Insertion Method)1.任选一节点为起点任选一
