)第二节删线路决策20XX年XX月()第二节删线路决策20XX年XX月第二节运输线路决策在整个物流成本中，运输成本所占比列为 33%-67%，所以我们必须关注如何降低运输成本问题，最大化地利用运 输设备和人员，优化运输线路是降低运输成本的关键壹）影响运输线路选择的因素1.成本因素（1）运输成本（2）营运成本（3）运输线路建设成本和土地成本 （4）固定成本2.非成本因素（1）交通因素（2）环保因素（3）政策法规因素（二）运输路线决策运输路线决策就是，找到运输网络中的最佳路线，以尽可能缩短运 输时间或运输距离，达到降低运输成本、改善运输服务的目标运输路 线决策问题有三种基本类型：壹是起点和终点不同的单壹路径规划；二是多个起点和终点的路径规划；三是起点和终点相同的路径规划壹、起点和终点不同的单壹路径规划 此类问题能够描述为在壹个已知交通运输网络中，寻找从出发地到 目的地的最佳路线这里的“最佳”能够指距离最短、时间最省或是费 用最少数学模型——求网络图中二点之间的最短路问题采用网络规划中 求最短路 Dijkstra 算法（标号算法） 除了距离以外，仍需要考虑通过交通网络的时间长短标号算法 1、最短路和最大流例题1例如，从上图中找出V1和V8之间的最短路线。
例题2要把A市的壹批货物运送到市的壹批货物运送到B市例题要把市 的壹批货物运送到市，根据俩个城市之间可选择的行车路线地图，绘制 了图 5—13 的公路网络要的公路网络可选择的行车路线地图，绘制 了图的公路网络求寻找壹条线路最短的运输路线求寻找壹条线路最短 的运输路线解：从终点开始逐步逆向推算(1) 和终点10联接的结点有俩个，即结点9和8；从结点 9到结点 10只有壹条线路，该线路为最短线路，长度100 ， 记为：(9-10)100；同样，结点8到结点10的最短线路为150，记为(8-10)150；(2) 结点6和6联接的只有壹个结点9，6至9的最短里程为200而 9 至终点 10 的最短里程为100．因此6至终点 10的最短里程为200 十 100 二 300记为：(6-9-10)3003) 结点5和5联接的结点有9、8俩个5至9再至终点的最短里程为400十100二500,5至8再至终点的最短里程为250十155二400400 < 500,所以5至终点的最短里程为400,记为：(5-8-10)400 ⑷结点7至终点的最短里程为125十150二275 ,(5)结点 4和 4 联接的结点有 5、6、7 三个。
结点 4 至 6 再到终点的最短里程为 200 十 300=500；结点4至5再到终点的最短里程为175十400二575 ;结点4至7再到终点的最短里程为275十275二550三个里程中以 500 为最小，所以结点 4 至 l0 的最短里程记为 (46—9—10)5006)结点 2 和 3用同样的方法，得到：结点 2 到终点的最短里程为 600记为：(26—9—10)600结点 3 到终点的最短里程为 575记为：(37—8—10)5755)最后见结点 1结点1 能够通过三个结点 2、3、4 连接到终点1通过结点2再到终点的最短里程100十600二700,路径为 (1—2—6—9—10)700结点1通过结点4再到终点的最短里程150十500二650,路径 为(1—4—6—9—10)650结点1通过结点3再到终点的最短里程175十575二750,路径 为(1—3—7—8—10)750之上三个里程中以 650 为最小,即 A 币到 B 市的最短里程,对应 的最短路线为：1—4—6—9—10二、多个起点和多个终点的路径规划问题多个起点和终点的路径优化,需要确定各供求地点之间的最佳供应 关系运用线性规划,数学模型能够描述为：有m个产地Ai,i = 1,2,..,m，可供应量分别为ai, = 1,2，…， m;有n个销地Bj ,j = 1,2,..,n，需要量分别为bj J = 1,2,.., n ；产销平衡，从Ai到Bj运输单位货物的运价（也能够是时间或距 离）为cij。
问如何调运这些货物，使得运费（或时间、吨公里数） 最少？常见的解决方法有：1、单纯形法 2、图表分析法 3、图上作业法 4、表上作业法5、供求不平衡运输模型三、起点和终点相同的路径规划 起点和终点相同的路径规划问题是物流配送业务中的常见问题由 于要求车辆必须返回起点，问题的难度提高了由于要求车辆必须 返回起点，问题的难度提高了解决这类问题的目标是找出途中经 过的点的顺序，使运输工具依次经过问题的目标是找出途中经过的 点的顺序，使运输工具依次经过所有送货点且满足各点对送货时间 的要求且满足各点对送货时间的要求，所有送货点且满足各点对送 货时间的要求，且总出行时间或总距离最短旅行推销员（NP难 题距离最短一一“旅行推销员（TSP）”问题，属于NP难题 旅行推销员TSP ）问题，属于NP难题随着问题中包含节点个数和约束条件的增加，随着问题中包含节 点个数和约束条件的增加，求解问题的复杂程度增加，要找到最优 路径非常困难杂程度增加，要找到最优路径非常困难即使用最 快的计算机进行计算，求最优解的时间也非常长进行计算，求最 优解的时间也非常长启发式求解法是求解这类问题的好方法类 问题的好方法见 p206 页例题 3运输批量越大，运输费率越低。
将小批量货物合且成大批量货物进行运输是降低运输成本的主要方 法输是降低运输成本的主要方法三）合理路线和时间安排的原则原则1将相互接近的停留点的货物装在壹辆车上运送，以便使停留 点之间的运行距离最小化a ）差的串联（b）更好的串联原则 2：将集聚在壹起的停留点安排同壹天送货，要避免不是同壹 天送货的停留点在运行线路上重叠原则 3：合理的运输路线壹辆运货车顺次途经各停车点的路线要呈 凸状，或泪点的路线要呈凸状，壹辆运货车顺次途经各点的路 线要呈凸状滴形，各条线路之间是不交叉原则 4：运行线路从仓库最远的停留点开始，送货车辆壹次装载邻近这个关键停留点的壹些停留点的货物，这辆运货车装载满后， 再安排另壹辆运货车装载另壹个最远的停留点的货物原则 5：有多种规格的车型，应优先使用载重量最大的送货车， 将路线上所有要求运送的货物都装载原则 6：提货应混在送货过程中进行，而不要在运行线路结束 后再运行原则 7：对偏离集聚停车点路线远的单独的停车点能够使用点 点小载重量的车辆专门为这些停车点单独送货另壹个可供选 点择的方案是租用车辆或采用公共服务（如邮政服务）为这些 停车点送货原则 8：应当避免停车点工作时间太短的约束。
2、制定车辆路径优化方法 物流配送路径优化常见的约束条件包括：停车点的工作时间约 束，车辆的类型，最大的运行时间、不同区段的车速限制， 运行途中的障碍物（湖泊、山脉等、交通管制）、司机的 短时间休息等如果问题中包含送货点的个数很多，附加了许多约束条件，问 题求解就变得十分复杂四）运输路线和时刻表的制定方法（1）人工计算方法——扫描法人工计算方法扫描法 问题：对于若干个停车点（客户）安排最优行车路线 第壹步，将仓库（出发点）和所有的停车点位置画在地图上或 坐标图上； 第二步，通过仓库位置放置壹直尺，然后顺时针或逆时针方向 转动，直到直尺交到壹个停车点询问：累计的装货量是否超 过送货的载重量或容积（首先要使用最大的送货车辆）如是， 最后的停车点排除，将路线确定下来然后再从这个停车点开 始继续扫描，开始壹条新的路线这样扫描下去，直至全部的 停留点都被分配到路线上第三步，对每条路线安排运行顺序，以求运行距离最小化方案的误差率在 10%左右例 4 从各客户点提货，然后将货物运回仓库全天的提货量 见图 5-13送货车每次可运载10000 件要求确定：需多少 条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货 车辆服务有关客户点的顺序。
图 5-13 停留点提货量数据停留点提货量数据扫描法:手工计算车的载货量是扫描法手工计算车的载货 量是 10000件需要多少条线手工计算件每条线路上的站点如 何排列？扫描法:手工计算车的载货量是扫描法手工计算车的载货 量是 10000件需要多少条线手工计算件每条线路上的站点如 何让排列？（2）节约法（最优插入法）初始路线（3）相关软件——智能调度系统智能调度系统（IDS ）是采用GIS技术、最优路径算法、运筹 学和数据库等先进技术开发的物流软件，用于车辆调度和服务 线路规划（包括时间计划和线路规划）。