物流系统工程课件第十四讲--运输

《物流系统工程课件第十四讲--运输》由会员分享，可在线阅读，更多相关《物流系统工程课件第十四讲--运输（36页珍藏版）》请在金锄头文库上搜索。

1、1,用感知法求解巡回路径问题 对于各点空间相连的问题，且各停车点之间的空间关系代表的是实际的 运行时间或距离，可 以利用人类的模式认 知能力很好地解决。 合理的经停路线中各 条线路之间是不交叉 的，并且只要有可能 路径就会呈凸形，或 水滴状。图6-6举例说 明了合理和不合理的 路径设计。,复 习,2,安休瑟布喜公司利用售货员通过流动卡车销售啤酒和其它饮料,卡车 由当地经销人员所有。公司售货员同当地经销人员都是收取佣金，因而都 不希望每天向各客户提供服务时花费不必要的时间，行走多余的路程。他 们将图钉固定在地图上，以确定某推销员现有客户的位置。下图所举的是 一个20个客户的例子，客户点的信息已经

2、被转换到网络地图上，图中的坐 标与距离相关。我们要找出的是，卡车从仓库出发，经过所有的客户点， 再回到仓库，这个运行过程中距离最短的路径。 可以采用感知法求解最短路径。,例 子,3,X 坐标,饮料客户和仓库所在位置的网络图,Y 坐标,4,X 坐标,a)饮料客户 和仓库所在位 置的网络图 Y 坐标,X 坐标,b) 建议的路径 Y 坐标,5,内容： 合理路线和时期表的制定原则 行车路线和时刻表的制定方法 运输路线的安排 思考题： 你将采取什么措施帮助卡车调度员接受和使用本章介绍的行车路线和时 刻表制定方法?,6.4 行车路线和时刻表的制定,6,6.4.1 合理路线和时期表的制定原则 运用八条原则，

3、经过一番周折，决策者(如车辆调度员)可以制定出合理行 车路线和时刻表。这八条原则简述如下： （1）安排车辆负责相互距离最接近的站点的货物运输。 卡车的行车路线围绕 相互靠近的站点群进行 计划，以使站点之间的 行车时间最短。图6-8a 表示的是安排车辆装运 时应避免的划分方式， 图6-8b表示的则是比较 合理划分方式。,7,（2）安排车辆各日途经的站点时，应注意使站点群更加紧凑 （3）从距仓库最远的站点开始设计路线 （4）卡车的行车路线应呈水滴状 （5）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的 （6）取货、送货应该混合安排，不应该在完成全部送货任务之后再取 货。 （7）对过于遥远

4、而无法归入群落的站点，可以采用其它配送方式 （8）避免时间窗口过短 这些原则只是提供了合理路线设计的准则，但操作人员还是要处理一 些在这些原则中没有考虑到，而车辆运作中可能出现的限制或例外情况(紧 急订单、绕行等等)。采用这些方法设计的路线和时刻表比采用其它未经仔 细推敲的方法制定的计划有实质性改进。,8,6.4.2 行车路线和时期表的制定方法 1、扫描法 2、节约法,9,1. 扫描法(The Sweep Method) 扫描法可阐述如下： (1) 在地图或方格图中确定所有站点(含仓库)的位置。 (2) 自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该 直线直到与某站点相交。考虑，

5、如果在某线路上增加该站点，是否会超过车 辆的载货能力?如果没有，继续旋转直线，直到与下一个站点相交。再次计 算累计货运量是否超过车辆的运载能力(先使用最大的车辆)。如果超过，就 剔除最后的那个站点，并确定路线。随后，从不包含在上一条路线中的站点 开始，继续旋转直线以寻找新路线。继续该过程直到所有的站点都被安排到 路线中。 (3)排定各路线上每个站点的顺序使行车距离最短。排序时可以使用“水 滴”法或求解“流动推销员”问题的任何算法。,10,史密斯卡车运输公司用厢式货车从货主那里取货。货物先运回仓库，集 中后以更大的批量进行长途运输。图6-10列出了典型的一天取货量，取货量 单位是件。厢式货车的载

6、货量是10000件。完成所有取货任务一般需要整整 一天的时间。公司想知道需要多少条运输路线(即多少部车)，每条路线上应 该经过哪些站点，每条路线上的站点应该怎样排序。 首先，向北画一条直线，进行逆时针方向“扫描”。这些都是随机决定 的。逆时针旋转该直线，直到装载的货物能装上一辆载重10000件货物的卡 车，同时又不超重。一旦所有的站点都分派有车辆，就可以利用“水滴”法安 排经过各站点的顺序。图6-10b所列出的是最终的路线设计。,例 子,11,a),b),12,2. 节约法(The Savings Method) 节约法是一种颇为出色的方法，它能够灵活处理许多现实中的约束条件， 对站点数量不太

7、多的问题能较快算出结果，且结果与最优解很接近。对仅有 几个约束条件的小型问题，比较研究显示，利用节约法得到的结果平均只比 最优解高2，该方法能够处理有众多约束条件的实际问题，主要因为它可 以同时确定路线和经过各站点的顺序。 节约法的目标是使所有车辆行驶的总里程最短，并进而为所有站点提供服 务的卡车数量最少。该方法首先假设每一个站点都有一辆虚拟的卡车提供服 务，随后返回仓库，如图6-11a所示。这时的路线里程是最长的。下一步，将 两个站点合并到同一条行车路线上，减少一辆运输车，相应地缩短路线里 程。在决定哪些站点要合并到一条路线时，需要计算合并前后节约的运输距 离。不在一条运输路线上的两点(A和

8、B)合并所节约的距离就是图6-11a中路线 的里程减去图6-11b中路线的里程，节约值为Sdaodob-dab,13,对每对站点都进行这样的计算，并选择节约距离最多的一对站点合并在一 起，修订后的路线见图6-11b。,14,继续合并过程。除了将单个站点合并在一起外，还可以将某站点并入已 经包含多个站点的路线上。例如，如图6-11c，假如将某站点并入位于同一路 线上两点A和B之间，节约的距离为S=doc+dco+dab-dac-dcb。 (c) 插入a、b之间,15,如果如图6-11d所示，站点C排在线路最后一站B之后，则节约的距离为 S=doc+dbo-dbc 。 (d) 插入b之后,16,如

9、果如图6-11e所示，站点C排在站点A之前，则节约的距离为 S=dco+doa-dca (e) 插入a之前 每次合并时都要计算所节约距离，节约距离最多的站点就应该纳入现有 路线。假如由于某些约束条件(如路线太长，无法满足时间窗口的要求，或 超过车辆的承载能力)，节约距离最多的站点不能并入该路线，就要考虑节 约距离次多的站点。重复该过程直到所有站点的路线设计都完成。,17,节约法的优点 节约法强大的处理能力使得它能够包含实际应用中许多重要的约束条件。 该方法可以在指定各路线途经站点的同时初步确定站点的先后顺序。因此， 在将站点归入某条路线之前，应该预先考查加入新站点后路线的情况。此 外，还要考虑

10、一系列有关路线规划的问题，如行车时间是否超过允许的最长 驾驶时间，是否满足司机休息时间的要求，是否有足够载运量的车辆装载所 有的货物，各站点时间窗口的要求是否满足等等。不满足这些条件可能导致 该站点不能并入这条路线或者说明该站点在新路线中的排列顺序不当。接着 就要按照最大节约值原则选取下一个站点，重复考虑上述问题。因为扩展问 题的难度较大，节约法不能保证将得到最优解，但能够获得合理解。,18,案 例,网路先锋公司的线路规划和送货日程安排 一、方法： 节约矩阵分析法 二、步骤： 1、确认距离方阵 2、确认节约方阵 3、将客户划归不同运输线路的运输工具 4、为运输线路排定为客户送货的顺序,19,案

11、 例,送货线路的规划和送货日程的安排是最重要的运营决策。网路先锋公司 的网上商店向客户提供送货上门服务，向客户承诺半小时以内送货上门。给 定一组客户定单送货，该公司的目标是对送货工具和线路进行规划，对送货 日程进行安排，以便在满足承诺送货要求的同时，尽可能地降低成本。进行 运输工具的安排时，典型的目标是以下二者的结合：一是缩短运输工具的行 程和运输时间，以减少运费；二是避免出现象送货延误之类的失误。 下面以网路先锋公司配送中心经理为例，来讨论线路规划和设计过程中 的问题。当客户在网上订货后，配送中心的员工必须将所需货物装到卡车上 以备运输，经理必须决定哪辆卡车为哪些客户送货，并设定每辆卡车送货

12、过 程中的行驶线路。经理还必须确保每辆卡车都不超载而且能按时送货。,20,案 例,一天上午，网路先锋公司配送中心的经理收到了来自13个不同客户的订 单。配送中心的位置、每个客户的坐标以及每位客户所订货物见表1所示。 经理一共有4辆卡车，每辆卡车的载重量是200单位。经理认为，送货成本与 卡车的总行程即两点之间的距离高度相关。因此，经理决定将不同客户的送 货分配到每辆卡车上去，并为每辆卡车设计行驶线路，以达到减少总运距的 目标。 配送中心的经理首先必须决定哪些卡车为哪些客户送货，然后再设计每辆 卡车的行驶线路。在最初的任务完成后，送货顺序安排和运输流程改进便于 制定每辆卡车的行驶路线决策。配送中

13、心的经理决定使用节约矩阵分析法进 行决策。,21,案 例,22,案 例,节约矩阵分析法易于操作，即使在时间限制或者其他限制存在的情况下， 它仍然可以用来决定哪些卡车为哪些客户送货。主要步骤包括： 第一步：确认距离方阵 第二步：确认节约方阵 第三步：将客户划归不同运输线路的运输工具 第四步：为运输线路排定为客户送货的顺序 前三步用于将客户分配到运输工具中去，第四步为每辆卡车设定行驶线路 以缩短行程。,23,案 例,1、确认距离方阵 确认距离方阵是要确认任何将要经过的两个地点之间的距离。在这里， 我们用两点之间运输成本代替两点之间的距离。如果任意两点之间的运输成 本已知，那么就用它来代替两点之间的

14、距离。因此，坐标系中A、B两点之 间的距离Dist(A、B)可以用公式表示为(假定A、B两点的坐标(xA,yA)，(xB， yB)： 每两个客户之间的距离以及它们与配送中心的距离见表2。接下来，我们 用任意两个地点之间的距离，来计算节约方阵。,24,案 例,25,案 例,2、确认节约方阵 节约方阵是指将两个客户的订货放在一辆卡车上联合运送时节约的累积。 节约可按照距离、时间或者金钱来计算。网路先锋公司的经理按照距离建立 了节约方阵。运输工具的行程依其所经过地点的顺序不同来确认。配送中 心客户x-配送中心这一行程始于配送中心，送货给客人，然后再回到配送 中心。节约S(x，y)表示的含义是将两个行

15、程：配送中心客户x-配送中心； 配送中心客户y-配送中心，合二为一：配送中心客户x-客户y -配送中 心，而节约的距离。可以用公式计算如下： 例如，用表2经理计算出S(1，2)=12+8-9=11。网路先锋公司送货的节约方 阵见表3。节约方阵用来将客户划归不同运输线路的运输工具。,26,案 例,27,案 例,3、将客户划归不同运输线路的运输工具 经理力图在将客户划归不同运输工具或运输线路中使节约最大化。这一划 分过程要用到一个重复进行的程序。最初每一客户被划分到各自独立的运输 线路中去。如果两条运输线路上的运输总量不超过卡车的最大载重量，那么 二者的合并就是可行的，在任何反复进行的步骤上，网络

16、先锋公司的经理总 是试图使节约最大的两条线合并成一条新的可行的线路。这一过程一直持续 到不能再合并为止。 首先，最大的节约34来自线路6和线路11的合并，而且这种合并是可行 的。因为总运量为16+91=107，小于200，因此这两个客户被划归一条线路， 正如表4所示，从而节约34在下一步中也就无须再考虑了。,28,案 例,29,案 例,下一个最大的节约是将客户7和客户6合并为一条线路以后的节约33，由 于合并后的运量为107+56=163，小于200，所以这一合并也是可行的，因 此，客户7被添加到线路6中去，正如表5所示。 接下来最大的节约是合并客户5和线路6得到的节约29(我们无须考虑合 并客户7和客户11的节约32，因为二者都已经安排在线路6中了)。但是这一 合并却不能进行，因为客户5的57个单位的货物如果添加到线路6已有的货 物中去，那么总运量将超过卡车的最大载重量200。下面是将客户10添加到 线路6中去的节约28，但由于最大载重量