运输线路的选择PPT优秀课件.ppt

第二节第二节 运输线路决策运输线路决策1 在整个物流成本中，运输成本所占比列为33%-67%，所以我们必须关注如何降低运输成本问题，最大化地利用运输设备和人员，优化运输线路是降低运输成本的关键2 （一）影响运输线路选择的因素1.成本因素（1）运输成本（2）营运成本（3）运输线路建设成本和土地成本（4）固定成本2.非成本因素（1）交通因素 （2）环保因素（3）政策法规因素3（二）（二）运输路线决策运输路线决策 运输路线决策就是，找到运输网络中的最佳路线，以尽可能缩短运输时间或运输距离，达到降低运输成本、改善运输服务的目标 运输路线决策问题有三种基本类型：运输路线决策问题有三种基本类型： 一是起点和终点不同的单一路径规划； 二是多个起点和终点的路径规划； 三是起点和终点相同的路径规划4一、起点和终点不同的单一路径规划一、起点和终点不同的单一路径规划 此类问题可以描述为在一个已知交通运输网络中，寻找从出发地到目的地的最佳路线这里的“最佳”可以指距离最短、时间最省或是费用最少数学模型——求网络图中二点之间的最短路问题采用网络规划中求最短路Dijkstra算法（标号算法）。

除了距离以外，还需要考虑通过交通网络的时间长短5V5例如，从上图中找出V1与V8之间的最短路线V2V1V4V6V7V9V8V316312262634102431 1、最短路与最大流、最短路与最大流　起点　　起点　　终点　　终点　例题例题1标号算法6例题例题2 要把要把A市的一批货物运送到市的一批货物运送到B市，根据两个城市之间市，根据两个城市之间可选择的行车路线地图，绘制了图可选择的行车路线地图，绘制了图5—13的公路网络要的公路网络要求寻找一条线路最短的运输路线求寻找一条线路最短的运输路线1A市市4523769810B市市100150175300275200175275200300200400250125100150q 图中 为结点，代表起点、目的地和与行车路线相交的其他城市，其中的数字为结点编号q箭头为分支，代表两个结点之间的公路，箭头上标明的数字为运输里程公路网络公路网络17解：从终点开始逐步逆向推算 (1)与终点10联接的结点有两个，即结点9和8； 从结点9到结点10只有一条线路，该线路为最短线路，长度100，记为：（（9-109-10））100100； 同样，结点8到结点10的最短线路为150，记为（（8-108-10））150150； (2)结点6。

与6联接的只有一个结点9，6至9的最短里程为200而9至终点10的最短里程为100．因此6至终点10的最短里程为200十100＝300记为：(6-9-10)300(6-9-10)300 (3)结点5与5联接的结点有9、8两个 5至9再至终点的最短里程为400十100＝500， 5至8再至终点的最短里程为250十155＝400 400＜500，所以5至终点的最短里程为400，记为：(5-8-10)400(5-8-10)400 (4) 结点7至终点的最短里程为125十150＝275，记为：(7-8-10) 275(7-8-10) 275 1A市市4523769810B市市1001501752752001752752003002004002501251001503008(5)结点4与4联接的结点有5、6、7三个 结点4至6再到终点的最短里程为200十300=500； 结点4至5再到终点的最短里程为175十400＝575； 结点4至7再到终点的最短里程为275十275＝550 三个里程中以500为最小，所以结点4至l 0的最短里程记为(4—6—9—10) 500(4—6—9—10) 500。

6)结点2和3 用同样的方法，得到： 结点2到终点的最短里程为600记为：(2—6—9—10)600(2—6—9—10)600 结点3到终点的最短里程为575记为：(3—7—8—10)575(3—7—8—10)575 (5)最后看结点1结点1可以通过三个结点2、3、4连接到终点 结点1通过结点2再到终点的最短里程100十600＝700，路径为（（1—2—6—9—101—2—6—9—10））700700； 结点1通过结点4再到终点的最短里程150十500＝650，路径为（（1—4—6—9—101—4—6—9—10））650650； 结点1通过结点3再到终点的最短里程175十575＝750，路径为（（1—3—7—8—101—3—7—8—10））750750 以上三个里程中以650为最小，即A币到B市的最短里程，对应的最短路线为：1—4—6—9—101—4—6—9—101A市市4523769810B市市1001501752752001752752003002004002501251001503009二、多个起点和多个终点的路径规划问题二、多个起点和多个终点的路径规划问题 多个起点和终点的路径优化，需要确定各供求地点之间的最佳供应关系。

运用线性规划,数学模型可以描述为： 有m个产地 Ai，i =1，2，…，m，可供应量分别为ai，i=1，2，…，m；有n个销地 Bj，j=1，2，…，n，需要量分别为bj，j=1，2，…，n；产销平衡，从Ai到Bj 运输单位货物的运价（也可以是时间或距离）为cij问如何调运这些货物，使得运费（或时间、吨公里数）最少？ 101、单纯形法 2、图表分析法 4、表上作业法 5、供求不平衡运输模型 3、图上作业法常见的解决方法有： 11　　起起点点和和终终点点相相同同的的路路径径规规划划问问题题是是物物流流配配送送业业务务中中的的常常见见问问题 由由于于要要求求车车辆辆必必须须返返回回起起点点，，问问题题的的难难度度提提高高了了解解决决这这类类问问题题的的目目标标是是找找出出途途中中经经过过的的点点的的顺顺序序，，使使运运输输工工具具依依次次经经过过所所有有送送货货点点并并满满足足各各点点对对送送货货时时间间的的要要求求，，且且总总出出行行时时间间或或总总距离最短距离最短——“——“旅行推销员（旅行推销员（TSPTSP））””问题，属于问题，属于NPNP难题 随着问题中包含节点个数和约束条件的增加，求解问题的复随着问题中包含节点个数和约束条件的增加，求解问题的复杂程度增加，要找到最优路径非常困难。

即使用最快的计算机杂程度增加，要找到最优路径非常困难即使用最快的计算机进行计算，求最优解的时间也非常长启发式求解法是求解这进行计算，求最优解的时间也非常长启发式求解法是求解这类问题的好方法类问题的好方法 三、起点和终点相同的路径规划三、起点和终点相同的路径规划　　12见p206页例题313运输批量越大，运输费率越低运输批量越大，运输费率越低将小批量货物合并成大批量货物进行运将小批量货物合并成大批量货物进行运输是降低运输成本的主要方法输是降低运输成本的主要方法14原则１原则１. . 将相互接近的停留点的货物装在一辆车上运送，以便使停留点之间的运行距离最小化 （b）更好的串联 （a）差的串联 （三）合理路线和时间安排的原则仓库仓库仓库仓库15DD16原原则则2 2：：将集聚在一起的停留点安排同一天送货，要避免不是同一天送货的停留点在运行线路上重叠原则原则3 3：： 合理的运输路线合理的运输路线 一辆运货车顺次途经各一辆运货车顺次途经各停车点的路线要呈凸状，或泪点的路线要呈凸状，或泪滴形，各条线路之间是滴形，各条线路之间是不交叉不交叉的仓库库仓库17原则原则4 4：：运行线路从仓库最远的停留点开始，送货车辆一次装载邻近这个关键停留点的一些停留点的货物，这辆运货车装载满后，再安排另一辆运货车装载另一个最远的停留点的货物仓库仓库18原原则则5 5：：有多种规格的车型，应优先使用载重量最大的送货车，将路线上所有要求运送的货物都装载。

原原则则6 6：： 提货应混在送货过程中进行，而不要在运行线路结束后再运行原原则则7 7：： 对偏离集聚停车点点路线远的单独的停车点点可以使用小载重量的车辆专门为这些停车点点单独送货另一个可供选择的方案是租用车辆或采用公共服务（如邮政服务）为这些停车点点送货原则原则8 8：： 应当避免停车点点工作时间太短的约束19 物流配送路径优化常见的约束条件包括：停车点的工作时间约束，车辆的类型，最大的运行时间、不同区段的车速限制，运行途中的障碍物（湖泊、山脉等、交通管制）、司机的短时间休息等 如果问题中包含送货点的个数很多，附加了许多约束条件，问题求解就变得十分复杂 2 2、制定车辆路径优化方法、制定车辆路径优化方法 20（四）运输路线和时刻表的制定方法（四）运输路线和时刻表的制定方法（（1 1）人工计算方法）人工计算方法————扫描法扫描法 问题：对于若干个停车点（客户）安排最优行车路线第一步，将仓库（出发点）和所有的停车点位置画在地图上或坐标图上；第二步，通过仓库位置放置一直尺，然后顺时针或逆时针方向转动，直到直尺交到一个停车点询问：累计的装货量是否超过送货的载重量或容积（首先要使用最大的送货车辆）。

如是，最后的停车点排除，将路线确定下来然后再从这个停车点开始继续扫描，开始一条新的路线这样扫描下去，直至全部的停留点都被分配到路线上 第三步，对每条路线安排运行顺序，以求运行距离最小化方案的误差率在10%左右21100030002000400030003000200020002000200020001000仓库图图5-13停留点提货量数据停留点提货量数据例4 从各客户点提货，然后将货物运回仓库全天的提货量见图5-13送货车每次可运载10000件要求确定：需多少条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货车辆服务有关客户点的顺序22　　扫描法　　扫描法:手工计算车的载货量是手工计算车的载货量是10000件需要多少条线件需要多少条线路？每条线路上的站点如何排列？路？每条线路上的站点如何排列？D30003000100030002000200020002000200010002000400023　　扫描法　　扫描法:手工计算车的载货量是手工计算车的载货量是10000件需要多少条线件需要多少条线路？每条线路上的站点如何排列？路？每条线路上的站点如何排列？D300030001000300020002000200020002000100020004000D30003000100030002000200020002000200010002000400024（（2 2）节约法）节约法 ( (最优插入法最优插入法) )初始路线初始路线——线路里程线路里程将两个站点合并到同一路线上的里程将两个站点合并到同一路线上的里程节约的距离为 S=dAO+dOB-dABABOABO25（3）相关软件——智能调度系统 智能调度系统（IDS）是采用GIS技术、最优路径算法、运筹学和数据库等先进技术开发的物流软件，用于车辆调度和服务线路规划（包括时间计划和线路规划）26个人观点供参考，欢迎讨论。