运输线路的选择(课堂PPT).ppt

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