物流系统工程课件运输教学提纲.ppt

物流系统工程课件运输X 坐标坐标饮料客户和仓库所在位置的网络图饮料客户和仓库所在位置的网络图1514913161019201817121114732586D8765432100 1 2 3 4 5 6 7 8Y 坐标坐标2X 坐标坐标a)饮料客户饮料客户 和仓库所在位和仓库所在位 置的网络图置的网络图 Y 坐标坐标1514913 161019201817121114732586D8765432100 1 2 3 4 5 6 7 8X 坐标坐标b)建议的路径建议的路径 Y 坐标坐标1514913 161019201817121114732586D8765432100 1 2 3 4 5 6 7 83 内容：内容：u合理路线和时期表的制定原则合理路线和时期表的制定原则u行车路线和时刻表的制定方法行车路线和时刻表的制定方法u运输路线的安排运输路线的安排 思考题：思考题：你将采取什么措施帮助卡车调度员接受和使用本章介绍的行车路线和时你将采取什么措施帮助卡车调度员接受和使用本章介绍的行车路线和时刻表制定方法刻表制定方法?6.4行车路线和时刻表的制定行车路线和时刻表的制定46.4.1 合理路线和时期表的制定原则合理路线和时期表的制定原则 运用八条原则，经过一番周折，决策者运用八条原则，经过一番周折，决策者(如车辆调度员如车辆调度员)可以制定出合理行可以制定出合理行车路线和时刻表。这八条原则简述如下：车路线和时刻表。这八条原则简述如下：（1）安排车辆负责相互距离最接近的站点的货物运输。）安排车辆负责相互距离最接近的站点的货物运输。卡车的行车路线围绕卡车的行车路线围绕相互靠近的站点群进行相互靠近的站点群进行计划，以使站点之间的计划，以使站点之间的行车时间最短。图行车时间最短。图6-8a表示的是安排车辆装运表示的是安排车辆装运时应避免的划分方式，时应避免的划分方式，图图6-8b表示的则是比较表示的则是比较合理划分方式。合理划分方式。5 （2）安排车辆各日途经的站点时，应注意使站点群更加紧凑）安排车辆各日途经的站点时，应注意使站点群更加紧凑 （3）从距仓库最远的站点开始设计路线）从距仓库最远的站点开始设计路线 （4）卡车的行车路线应呈水滴状）卡车的行车路线应呈水滴状 （5）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的 （6）取货、送货应该混合安排，不应该在完成全部送货任务之后再取）取货、送货应该混合安排，不应该在完成全部送货任务之后再取货。货。（7）对过于遥远而无法归入群落的站点，可以采用其它配送方式）对过于遥远而无法归入群落的站点，可以采用其它配送方式 （8）避免时间窗口过短）避免时间窗口过短 这些原则只是提供了合理路线设计的准则，但操作人员还是要处理一这些原则只是提供了合理路线设计的准则，但操作人员还是要处理一些在这些原则中没有考虑到，而车辆运作中可能出现的限制或例外情况些在这些原则中没有考虑到，而车辆运作中可能出现的限制或例外情况(紧紧急订单、绕行等等急订单、绕行等等)。采用这些方法设计的路线和时刻表比采用其它未经仔。采用这些方法设计的路线和时刻表比采用其它未经仔细推敲的方法制定的计划有实质性改进。细推敲的方法制定的计划有实质性改进。6u 6.4.2 行车路线和时期表的制定方法行车路线和时期表的制定方法l 1、扫描法、扫描法l 2、节约法、节约法7l1.扫描法扫描法(The Sweep Method)扫描法可阐述如下：扫描法可阐述如下：(1)在地图或方格图中确定所有站点在地图或方格图中确定所有站点(含仓库含仓库)的位置。的位置。(2)自仓库始沿任一方向向外划一条直线。自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该沿顺时针或逆时针方向旋转该直线直到与某站点相交。考虑，如果在某线路上增加该站点，是否会超过车直线直到与某站点相交。考虑，如果在某线路上增加该站点，是否会超过车辆的载货能力辆的载货能力?如果没有，继续旋转直线，直到与下一个站点相交。再次计如果没有，继续旋转直线，直到与下一个站点相交。再次计算算累计货运量累计货运量是否超过车辆的是否超过车辆的运载能力运载能力(先使用最大的车辆先使用最大的车辆)。如果超过，就。如果超过，就剔除最后的那个站点，并确定路线。随后，从不包含在上一条路线中的站点剔除最后的那个站点，并确定路线。随后，从不包含在上一条路线中的站点开始，继续旋转直线以寻找新路线。继续该过程直到所有的站点都被安排到开始，继续旋转直线以寻找新路线。继续该过程直到所有的站点都被安排到路线中。路线中。(3)排定各路线上每个站点的顺序使行车距离最短。排定各路线上每个站点的顺序使行车距离最短。排序时可以使用排序时可以使用“水水滴滴”法或求解法或求解“流动推销员流动推销员”问题的任何算法。问题的任何算法。8 史密斯卡车运输公司用厢式货车从货主那里取货。货物先运回仓库，集史密斯卡车运输公司用厢式货车从货主那里取货。货物先运回仓库，集中后以更大的批量进行长途运输。图中后以更大的批量进行长途运输。图6-10列出了典型的一天取货量，取货量列出了典型的一天取货量，取货量单位是件。厢式货车的载货量是单位是件。厢式货车的载货量是10000件。完成所有取货任务一般需要整整件。完成所有取货任务一般需要整整一天的时间。公司想知道需要一天的时间。公司想知道需要多少条运输路线多少条运输路线(即多少部车即多少部车)，每条路线上应，每条路线上应该该经过哪些站点经过哪些站点，每条路线上的站点每条路线上的站点应该怎样应该怎样排序排序。首先，首先，向北画一条直线，进行逆时针方向向北画一条直线，进行逆时针方向“扫描扫描”。这些都是随机决定。这些都是随机决定的。逆时针旋转该直线，直到装载的货物能装上一辆载重的。逆时针旋转该直线，直到装载的货物能装上一辆载重10000件货物的卡件货物的卡车，同时又不超重。一旦所有的站点都分派有车辆，就可以利用车，同时又不超重。一旦所有的站点都分派有车辆，就可以利用“水滴水滴”法法安安排经过各站点的顺序。图排经过各站点的顺序。图6-10b所列出的是最终的路线设计。所列出的是最终的路线设计。例例 子子9 a)b)10l2.节约法节约法(The Savings Method)节约法是一种颇为出色的方法，它能够灵活处理许多现实中的约束条件，节约法是一种颇为出色的方法，它能够灵活处理许多现实中的约束条件，对对站点数量不太多站点数量不太多的问题能较快算出结果，且结果与最优解很接近。对仅有的问题能较快算出结果，且结果与最优解很接近。对仅有几个约束条件的小型问题，比较研究显示，利用节约法得到的结果平均只比几个约束条件的小型问题，比较研究显示，利用节约法得到的结果平均只比最优解高最优解高2，该方法能够处理，该方法能够处理有众多约束条件的实际问题有众多约束条件的实际问题，主要因为它可主要因为它可以同时确定路线和经过各站点的顺序。以同时确定路线和经过各站点的顺序。节约法的目标是使所有车辆节约法的目标是使所有车辆行驶的总里程最短行驶的总里程最短，并进而为所有站点提供服，并进而为所有站点提供服务的务的卡车数量卡车数量最少。该方法首先假设每一个站点都有一辆虚拟的卡车提供服最少。该方法首先假设每一个站点都有一辆虚拟的卡车提供服务，随后返回仓库，如图务，随后返回仓库，如图6-11a所示。这时的路线里程是最长的。下一步，将所示。这时的路线里程是最长的。下一步，将两个站点合并到同一条行车路线上，减少一辆运输车，相应地缩短路线里两个站点合并到同一条行车路线上，减少一辆运输车，相应地缩短路线里程。在决定哪些站点要合并到一条路线时，需要计算合并前后节约的运输距程。在决定哪些站点要合并到一条路线时，需要计算合并前后节约的运输距离。不在一条运输路线上的两点离。不在一条运输路线上的两点(A和和B)合并所节约的距离就是图合并所节约的距离就是图6-11a中路线中路线的里程减去图的里程减去图6-11b中路线的里程，节约值为中路线的里程，节约值为Sdaodob-dab11对每对站点都进行这样的计算，并选择对每对站点都进行这样的计算，并选择节约距离最多节约距离最多的一对站点合并在一的一对站点合并在一起，修订后的路线见图起，修订后的路线见图6-11b。12 继续合并过程。除了将单个站点合并在一起外，还可以将某站点并入已继续合并过程。除了将单个站点合并在一起外，还可以将某站点并入已经包含多个站点的路线上。例如，如图经包含多个站点的路线上。例如，如图6-11c，假如将某站点并入位于同一路，假如将某站点并入位于同一路线上两点线上两点A和和B之间，节约的距离为之间，节约的距离为S=doc+dco+dab-dac-dcb。(c)插入插入a、b之间之间13 如果如图如果如图6-11d所示，站点所示，站点C排在线路最后一站排在线路最后一站B之后，则节约的距离为之后，则节约的距离为S=doc+dbo-dbc。(d)插入插入b之后之后14 如果如图如果如图6-11e所示，站点所示，站点C排在站点排在站点A之前，则节约的距离为之前，则节约的距离为S=dco+doa-dca (e)插入插入a之前之前 每次合并时都要计算所节约距离，节约距离最多的站点就应该纳入现有每次合并时都要计算所节约距离，节约距离最多的站点就应该纳入现有路线。假如由于某些约束条件路线。假如由于某些约束条件(如路线太长，无法满足时间窗口的要求，或如路线太长，无法满足时间窗口的要求，或超过车辆的承载能力超过车辆的承载能力)，节约距离最多的站点不能并入该路线，就要，节约距离最多的站点不能并入该路线，就要考虑节考虑节约距离次多约距离次多的站点。重复该过程直到所有站点的路线设计都完成。的站点。重复该过程直到所有站点的路线设计都完成。15节约法的优点节约法的优点 节约法强大的处理能力使得它能够节约法强大的处理能力使得它能够包含实际应用中许多重要的约束条件。包含实际应用中许多重要的约束条件。该方法可以在指定该方法可以在指定各路线途经站点的同时各路线途经站点的同时初步初步确定站点的先后顺序。确定站点的先后顺序。因此，因此，在将站点归入某条路线之前，应该预先考查加入新站点后路线的情况。此在将站点归入某条路线之前，应该预先考查加入新站点后路线的情况。此外，还要考虑一系列有关路线规划的问题，如外，还要考虑一系列有关路线规划的问题，如行车时间行车时间是否超过允许的最长是否超过允许的最长驾驶时间，是否满足驾驶时间，是否满足司机休息司机休息时间的要求，是否有时间的要求，是否有足够载运量足够载运量的车辆装载所的车辆装载所有的货物，各站点有的货物，各站点时间窗口时间窗口的要求是否满足等等。不满足这些条件可能导致的要求是否满足等等。不满足这些条件可能导致该站点不能并入这条路线或者说明该站点在新路线中的排列顺序不当。接着该站点不能并入这条路线或者说明该站点在新路线中的排列顺序不当。接着就要按照就要按照最大节约值最大节约值原则选取下一个站点，重复考虑上述问题。因为原则选取下一个站点，重复考虑上述问题。因为扩展问扩展问题题的难度较大，节约法不能保证将得到的难度较大，节约法不能保证将得到最优解最优解，但能够获得，但能够获得合理解合理解。16案案 例例网路先锋公司的线路规划和送货日程安排网路先锋公司的线路规划和送货日程安排u一、方法：一、方法：节约矩阵分析法节约矩阵分析法u二、步骤：二、步骤：l1、确认距离方阵、确认距离方阵l 2、确认节约方阵、确认节约方阵l 3、将客户划归不同运输线路的运输工具、将客户划归不同运输线路的运输工具l4、为运输线路排定为客户送货的顺序、为运输线路排定为客户送货的顺序17案案 例例 送货线路的规划送货线路的规划和和送货日程的安排送货日程的安排是最重要的运营决策。是最重要的运营决策。网路先锋公司网路先锋公司的网上商店向客户提供送货上门服务，向客户承诺半小时以内送货上门。给的网上商店向客户提供送货上门服务，向客户承诺半小时以内送货上门。给定一组客户定单送货，该公司的目标是对定一组客户定单送货，该公司的目标是对送货工具送货工具和和线路线路进行规划，对进行规划，对送货送货日程日程进行安排，以便在满足承诺送货要求的同时，尽可能地降低成本。进行进行安排，以便在满足承诺送货要求的同时，尽可能地降低成本。进行运输工具的安排时，典型的目标是以下二者的结合：一是缩短运输工具的行运输工具的安排时，典型的目标是以下二者的结合：一是缩短运输工具的行程和运输时间，以减少运费；二是避免出现象送货延误之类的失误。程和运输时间，以减少运费；二是避免出现象送货延误之类的失误。下面以下面以网路先锋公司配送中心经理网路先锋公司配送中心经理为例，来讨论线路规划和设计过程中为例，来讨论线路规划和设计过程中的问题。当客户在网上订货后，配送中心的员工必须将所需货物装到卡车上的问题。当客户在网上订货后，配送中心的员工必须将所需货物装到卡车上以备运输，经理必须决定哪辆卡车为哪些客户送货，并设定每辆卡车送货过以备运输，经理必须决定哪辆卡车为哪些客户送货，并设定每辆卡车送货过程中的行驶线路。经理还必须确保每辆卡车都不超载而且能按时送货。程中的行驶线路。经理还必须确保每辆卡车都不超载而且能按时送货。18案案 例例 一天上午，网路先锋公司配送中心的经理收到了来自一天上午，网路先锋公司配送中心的经理收到了来自13个不同客户的订个不同客户的订单。配送中心的位置、每个客户的坐标以及每位客户所订货物见表单。配送中心的位置、每个客户的坐标以及每位客户所订货物见表1所示。所示。经理一共有经理一共有4辆卡车，每辆卡车的载重量是辆卡车，每辆卡车的载重量是200单位。经理认为，单位。经理认为，送货成本送货成本与与卡车的总行程即两点之间的距离高度相关。因此，经理决定将不同客户的送卡车的总行程即两点之间的距离高度相关。因此，经理决定将不同客户的送货分配到每辆卡车上去，并为货分配到每辆卡车上去，并为每辆卡车设计行驶线路每辆卡车设计行驶线路，以达到，以达到减少总运距减少总运距的的目标。目标。配送中心的经理配送中心的经理首先首先必须决定哪些卡车为哪些客户送货，必须决定哪些卡车为哪些客户送货，然后然后再设计每辆再设计每辆卡车的行驶线路。在最初的任务完成后，送货顺序安排和运输流程改进便于卡车的行驶线路。在最初的任务完成后，送货顺序安排和运输流程改进便于制定每辆卡车的行驶路线决策。配送中心的经理决定使用制定每辆卡车的行驶路线决策。配送中心的经理决定使用节约矩阵分析法节约矩阵分析法进进行决策。行决策。19案案 例例 20案案 例例 节约矩阵分析法节约矩阵分析法易于操作，即使在时间限制或者其他限制存在的情况下，易于操作，即使在时间限制或者其他限制存在的情况下，它仍然可以用来决定哪些卡车为哪些客户送货。主要步骤包括：它仍然可以用来决定哪些卡车为哪些客户送货。主要步骤包括：第一步：第一步：确认距离方阵确认距离方阵 第二步：第二步：确认节约方阵确认节约方阵 第三步：第三步：将客户划归不同运输线路的运输工具将客户划归不同运输线路的运输工具 第四步：第四步：为运输线路排定为客户送货的顺序为运输线路排定为客户送货的顺序 前三步用于将客户分配到运输工具中去，第四步为每辆卡车设定行驶线路前三步用于将客户分配到运输工具中去，第四步为每辆卡车设定行驶线路以缩短行程。以缩短行程。21案案 例例1、确认距离方阵、确认距离方阵 确认距离方阵是要确认任何将要经过的两个地点之间的距离。在这里，确认距离方阵是要确认任何将要经过的两个地点之间的距离。在这里，我们用两点之间我们用两点之间运输成本运输成本代替两点之间的距离。如果任意两点之间的代替两点之间的距离。如果任意两点之间的运输成运输成本本已知，那么就用它来代替两点之间的距离。因此，坐标系中已知，那么就用它来代替两点之间的距离。因此，坐标系中A、B两点之两点之间的距离间的距离Dist(A、B)可以用公式表示为可以用公式表示为(假定假定A、B两点的坐标两点的坐标(xA,yA)，(xB，yB)：每两个客户之间的距离以及它们与配送中心的距离见表每两个客户之间的距离以及它们与配送中心的距离见表2。接下来，我们。接下来，我们用用任意两个地点之间的距离任意两个地点之间的距离，来计算，来计算节约方阵节约方阵。22案案 例例 23案案 例例 2、确认节约方阵、确认节约方阵 节约方阵是指将两个客户的订货放在一辆卡车上联合运送时节约的累积。节约方阵是指将两个客户的订货放在一辆卡车上联合运送时节约的累积。节约可按照距离、时间或者金钱来计算。网路先锋公司的经理按照距离建立节约可按照距离、时间或者金钱来计算。网路先锋公司的经理按照距离建立了节约方阵。运输工具的行程依其所经过地点的顺序不同来确认。配送中了节约方阵。运输工具的行程依其所经过地点的顺序不同来确认。配送中心心客户客户x-配送中心这一行程始于配送中心，送货给客人，然后再回到配送配送中心这一行程始于配送中心，送货给客人，然后再回到配送中心。节约中心。节约S(x，y)表示的含义是将两个行程：表示的含义是将两个行程：配送中心配送中心客户客户x-配送中心配送中心；配送中心配送中心客户客户y-配送中心配送中心，合二为一：，合二为一：配送中心配送中心客户客户x-客户客户y-配送中配送中心心，而，而节约的距离节约的距离。可以用公式计算如下：。可以用公式计算如下：例如，用表例如，用表2经理计算出经理计算出S(1，2)=12+8-9=11。网路先锋公司送货的节约方。网路先锋公司送货的节约方阵见表阵见表3。节约方阵用来将客户划归不同运输线路的运输工具。节约方阵用来将客户划归不同运输线路的运输工具。24案案 例例25案案 例例 3、将客户划归不同运输线路的运输工具、将客户划归不同运输线路的运输工具 经理力图在将客户划归不同运输工具或运输线路中经理力图在将客户划归不同运输工具或运输线路中使节约最大化使节约最大化。这一划。这一划分过程要用到一个重复进行的程序。最初每一客户被划分到各自独立的运输分过程要用到一个重复进行的程序。最初每一客户被划分到各自独立的运输线路中去。如果两条运输线路上的运输总量不超过卡车的最大载重量，那么线路中去。如果两条运输线路上的运输总量不超过卡车的最大载重量，那么二者的合并就是可行的，在任何反复进行的步骤上，网络先锋公司的经理总二者的合并就是可行的，在任何反复进行的步骤上，网络先锋公司的经理总是试图是试图使节约最大使节约最大的两条线合并成一条新的可行的线路。这一过程一直持续的两条线合并成一条新的可行的线路。这一过程一直持续到不能再合并为止。到不能再合并为止。首先，最大的节约首先，最大的节约34来自线路来自线路6和线路和线路11的合并，而且这种合并是可行的合并，而且这种合并是可行的。因为总运量为的。因为总运量为16+91=107，小于，小于200，因此这两个客户被划归一条线路，因此这两个客户被划归一条线路，正如表正如表4所示，从而节约所示，从而节约34在下一步中也就无须再考虑了。在下一步中也就无须再考虑了。26案案 例例 27案案 例例 下一个最大的节约是将客户下一个最大的节约是将客户7和客户和客户6合并为一条线路以后的节约合并为一条线路以后的节约33，由，由于合并后的运量为于合并后的运量为107+56=163，小于，小于200，所以这一合并也是可行的，因，所以这一合并也是可行的，因此，客户此，客户7被添加到线路被添加到线路6中去，正如表中去，正如表5所示。所示。接下来最大的节约是合并客户接下来最大的节约是合并客户5和线路和线路6得到的节约得到的节约29(我们无须考虑合我们无须考虑合并客户并客户7和客户和客户11的节约的节约32，因为二者都已经安排在线路，因为二者都已经安排在线路6中了中了)。但是这一。但是这一合并却不能进行，因为客户合并却不能进行，因为客户5的的57个单位的货物如果添加到线路个单位的货物如果添加到线路6已有的货已有的货物中去，那么总运量将超过卡车的最大载重量物中去，那么总运量将超过卡车的最大载重量200。下面是将客户。下面是将客户10添加到添加到线路线路6中去的节约中去的节约28，但由于最大载重量的限制，这些合并都是不可行的。，但由于最大载重量的限制，这些合并都是不可行的。最后找到将客户最后找到将客户8添加到线路添加到线路6中去的节约中去的节约16，由于合并后的运量为，由于合并后的运量为163+30=193，小于，小于200，所以这一合并是可行的。因此，可将，所以这一合并是可行的。因此，可将6，7，8，11分为一组。分为一组。28案案 例例 29案案 例例 下面的最大节约是合并线路下面的最大节约是合并线路3和和4得到的节约得到的节约28，这是可行的。这两条线路，这是可行的。这两条线路合二为一，如表合二为一，如表6所示。所示。30案案 例例 继续这一反复进行的程序，经理将客户分为四组：继续这一反复进行的程序，经理将客户分为四组：1，3，4，2，9，6，7，8，11，5，10，12，13。然后将每一组分配在一辆卡车上。下一步将排定每一线路内的运输工具然后将每一组分配在一辆卡车上。下一步将排定每一线路内的运输工具的送货顺序。的送货顺序。31u6.4.3 运输路线的排序运输路线的排序 表表6-7为某运输公司的线路时刻表，假设该公司的卡车型号和载重量均相为某运输公司的线路时刻表，假设该公司的卡车型号和载重量均相同，请为该公司制定行车路线计划，使得在满足所有线路服务的条件下，同，请为该公司制定行车路线计划，使得在满足所有线路服务的条件下，所所用车辆最少，车辆空闲时间最短用车辆最少，车辆空闲时间最短。32 解：将所有路线在一天时间内按照时间进行排序，就可满足条件。图解：将所有路线在一天时间内按照时间进行排序，就可满足条件。图6.2为排序结果，即为行车路线计划。为排序结果，即为行车路线计划。33思考题思考题 你将采取什么措施帮助卡车调度员接受和使用本章介绍的行你将采取什么措施帮助卡车调度员接受和使用本章介绍的行车路线和时刻表制定方法车路线和时刻表制定方法?34 本章应掌握的主要内容本章应掌握的主要内容 影响运输方式选择的因素影响运输方式选择的因素 产销不平衡的直达运输线路优化模型产销不平衡的直达运输线路优化模型 解决中转运输问题的思路解决中转运输问题的思路 多起讫点问题的求解方法多起讫点问题的求解方法 合理路线和时刻表的制定原则合理路线和时刻表的制定原则 采用扫描法求解行车路线的方法采用扫描法求解行车路线的方法 采用节约法制定行车路线和时刻表的思路采用节约法制定行车路线和时刻表的思路35此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢