《第11章-线路规划》由会员分享，可在线阅读，更多相关《第11章-线路规划（112页珍藏版）》请在金锄头文库上搜索。
1、第十一章第十一章 运输与配送的线路规划运输与配送的线路规划n n合理的运行路线和时间安排原则合理的运行路线和时间安排原则n n点点间运输点点间运输最短路径求解方法最短路径求解方法n n多点间运输多点间运输运输算法运输算法n n节约法制定车辆运行路线节约法制定车辆运行路线n n中国邮路法制定车辆运行路线中国邮路法制定车辆运行路线n n扫描法制定车辆运行路线扫描法制定车辆运行路线n n车辆运行时间的安排车辆运行时间的安排案例案例1 1n n伊万斯维尔地方学区为小学生提供校车服务。如图所示，伊万斯维尔地方学区为小学生提供校车服务。如图所示， 现有一辆校车被分派到该地区。已知每年学生的新名册，现有一辆
2、校车被分派到该地区。已知每年学生的新名册， 接送学生的停车点位置在地图上标出。对各站点进行排序接送学生的停车点位置在地图上标出。对各站点进行排序 以确定校车每次行驶所需的时间和距离。利用你最佳的感以确定校车每次行驶所需的时间和距离。利用你最佳的感 知技巧设计满足下列条件的最短路径：知技巧设计满足下列条件的最短路径：l l经过所有停车点。经过所有停车点。l l孩子们可以在街道的任何一边上下车。孩子们可以在街道的任何一边上下车。l l住在临近街区的孩子可以在拐弯处上下车。住在临近街区的孩子可以在拐弯处上下车。l l不允许转不允许转U U形弯。形弯。l l校车有足够空间，可以接送路上所有的学生。校车
3、有足够空间，可以接送路上所有的学生。借助尺子计算校车行驶的总距离。借助尺子计算校车行驶的总距离。校车路线制定练习校车路线制定练习123456789101112141315161718192021习题习题4 4答案答案n n1.1.将相互接近的停留点的货物装在一辆车上运送将相互接近的停留点的货物装在一辆车上运送n n2. 2.将集聚在一起的停留点安排同一天送货将集聚在一起的停留点安排同一天送货n n3. 3.运行路线从离仓库最远的停留点开始。运行路线从离仓库最远的停留点开始。n n4. 4.一辆运货车顺次途经各停留点的路线要成泪滴状。一辆运货车顺次途经各停留点的路线要成泪滴状。n n5. 5.
4、尽可能使用最大的车辆进行运送。尽可能使用最大的车辆进行运送。n n6. 6. 取货、送货应该混合安排，不应该在完成全部送货任务之取货、送货应该混合安排，不应该在完成全部送货任务之 后再取货。后再取货。n n7. 7.对偏离集聚停留点路线远的单独的停留点可应用另一个送对偏离集聚停留点路线远的单独的停留点可应用另一个送 货方案。货方案。n n8. 8.应当避免停留点工作时间太短的约束。应当避免停留点工作时间太短的约束。一一. . 合理的运行路线和时间安排原则合理的运行路线和时间安排原则1. 1.将相互接近的停留点的货物装在一辆车上运送将相互接近的停留点的货物装在一辆车上运送仓库差的串联仓库差的串联
5、 仓库更好的串联仓库更好的串联车辆将停留点串起来的示意图车辆将停留点串起来的示意图 DD 仓库停留点仓库2. 2.将集聚在一起的停留点安排同一天送货将集聚在一起的停留点安排同一天送货不合理的不合理的路线交叉划分方式路线交叉划分方式 较合理的较合理的线路划分方式线路划分方式一周各天停留点群的划分一周各天停留点群的划分FFFFFFFTTTTTTTD 仓库FFFFFTTTFTFTTTD 仓库(a) (b) 停留点3. 3.运行路线从离仓库最远的停留点开始。运行路线从离仓库最远的停留点开始。n n首先应划分出离仓库最远的停留点集聚区。首先应划分出离仓库最远的停留点集聚区。n n选定距该核心停留点最近的
6、一些停留点形成停留点集聚区选定距该核心停留点最近的一些停留点形成停留点集聚区 ，分派载货能力能满足该停留点集聚区需要的卡车。，分派载货能力能满足该停留点集聚区需要的卡车。n n从还没有分派车辆的其他停留点中找出距仓库最远的站点从还没有分派车辆的其他停留点中找出距仓库最远的站点 ，分派另一车辆。，分派另一车辆。4. 4.一辆运货车顺次途经各停留点的路线要成泪滴状。一辆运货车顺次途经各停留点的路线要成泪滴状。n n根据经验，当运行路线不发生交叉时，经过各停留点根据经验，当运行路线不发生交叉时，经过各停留点 的次序是合理的，同时，应尽量使运行路线形成泪滴的次序是合理的，同时，应尽量使运行路线形成泪滴
7、 状。状。运输路线示意图运输路线示意图不好的线路规划不好的线路规划线路交叉线路交叉 好的线路规划好的线路规划线路不交叉线路不交叉仓库仓库 仓库仓库 例安休瑟例安休瑟布喜公司布喜公司 (Anheuser(AnheuserBusch Company)Busch Company)利用利用 售货员通过流动卡车销售啤酒和售货员通过流动卡车销售啤酒和 其它饮料，卡车由当地经销人员其它饮料，卡车由当地经销人员 所有。公司售货员同当地经销人所有。公司售货员同当地经销人 员一样都是收取佣金，因而都不员一样都是收取佣金，因而都不 希望每天向各客户提供服务时花希望每天向各客户提供服务时花 费不必要的时间，行走多余的
8、路费不必要的时间，行走多余的路 程。他们将图钉固定在地图上，程。他们将图钉固定在地图上， 以确定某推销员现有客户的位置以确定某推销员现有客户的位置 。图。图中中所举的是一个所举的是一个2020个客户的个客户的 例子，客户点的信息已经被转换例子，客户点的信息已经被转换 到网格地图上，图中的坐标与距到网格地图上，图中的坐标与距 离相关。我们要找出的是，卡车离相关。我们要找出的是，卡车 从仓库出发，经过所有的客户点从仓库出发，经过所有的客户点 ，再回到仓库，这个运行过程中，再回到仓库，这个运行过程中 距离最短的路径。距离最短的路径。建议的路径建议的路径 用软件用软件ROUTEROUTE的计算结的计算
9、结 果。整个行程的总成本果。整个行程的总成本 为为37.5937.59距离单位。距离单位。 比例尺：比例尺：1 15 5英里英里 珠宝推销员问题中客户珠宝推销员问题中客户(X)(X)和汽车旅馆和汽车旅馆(Y)(Y)的位置的位置习题习题n n丹丹帕普帕普(Dan (Dan PuppPupp) )是个珠宝推销是个珠宝推销 员，他需要走访中西部的店铺。图员，他需要走访中西部的店铺。图 中列出了他负责的某个销售区域。中列出了他负责的某个销售区域。 他的工作方式是在走访的前一天晚他的工作方式是在走访的前一天晚 上来到这个地区，住在当地的汽车上来到这个地区，住在当地的汽车 旅馆里，花两天时间走访这个地区旅
10、馆里，花两天时间走访这个地区 ，随后在第三天早上离开。由于是，随后在第三天早上离开。由于是 自己付费，他希望总成本能够最小自己付费，他希望总成本能够最小 。第一天要走访第。第一天要走访第1 1至第至第9 9位客户，位客户， 第二天走访其余的客户。他有两个第二天走访其余的客户。他有两个 方案可供比较。方案可供比较。n n方案方案1 1：三晚都住在汽车旅馆：三晚都住在汽车旅馆M2M2中中 ，住宿费是每晚，住宿费是每晚49.0049.00美元。美元。n n方案方案2 2：前两晚都住在汽车旅馆：前两晚都住在汽车旅馆M1M1 中，走访客户中，走访客户l l至至9 9，住宿费为每晚，住宿费为每晚 40.0
11、040.00美元。随后，搬到汽车旅馆美元。随后，搬到汽车旅馆 M3M3住一晚，走访客户住一晚，走访客户1010至至1818，住宿，住宿 费是每晚费是每晚45.0045.00美元。在走访客户美元。在走访客户l l 至至9 9后，推销员回到后，推销员回到M1M1，在此过夜，在此过夜 。随后，搬到。随后，搬到M3M3，过夜并于次日早，过夜并于次日早 晨离开。晨离开。M1M1和和M3M3相距相距3636英里。不管英里。不管 丹在这个地区的什么地方，旅行成丹在这个地区的什么地方，旅行成 本都是本都是0.300.30美元英里。美元英里。n n哪个方案对丹最好哪个方案对丹最好? ?答案答案 方案方案1 1路
12、线停留点顺序路线停留点顺序 距离距离8 6 4 1 2 3 5 7 9 95.408 6 4 1 2 3 5 7 9 95.4010 13 14 17 18 16 12 15 11 86.4610 13 14 17 18 16 12 15 11 86.46线路总长度（英里）线路总长度（英里） 181.86181.86方案方案1 1的总成本为：的总成本为：住宿费：住宿费： 493 493 147 147 美元美元旅行费用：旅行费用：181.860.30 181.860.30 54.5654.56美元美元总成本：总成本： 201.56201.56美元美元答案答案 方案方案2 2路线停留点顺序路线停
13、留点顺序 距离距离2 3 5 7 9 8 6 4 1 95.402 3 5 7 9 8 6 4 1 95.4018 17 13 14 10 11 15 12 16 80.3018 17 13 14 10 11 15 12 16 80.30M M1 1与与M M3 3距离距离 3636线路总长度（英里）线路总长度（英里） 211.70211.70方案方案1 1的总成本为：的总成本为：住宿费：住宿费： 40 + 40 + 45 40 + 40 + 45 125 125 美元美元旅行费用：旅行费用：211.700.30 211.700.30 63.5163.51美元美元总成本：总成本： 188.51
14、188.51美元美元采用第二种方案最好采用第二种方案最好实例实例n n凯斯寿材公司凯斯寿材公司(The (The Case Case Casket Casket Company)Company)生产一系列殡生产一系列殡 葬产品，并向各殡仪馆送货。殡仪馆订货量常常很小，葬产品，并向各殡仪馆送货。殡仪馆订货量常常很小， 经常一次不超过一个。为服务市场，凯斯公司在全美建经常一次不超过一个。为服务市场，凯斯公司在全美建 立了立了5050多家配送仓库。多家配送仓库。n n图中列出了其中一家仓库的位置及其服务区域，同时还图中列出了其中一家仓库的位置及其服务区域，同时还 列出了有代表性的一周订货量和订货点的位置。仓库使列出了有代表性的一周订货量和订货点的位置。仓库使 用两辆特制的卡车送货，该种卡车最多可运送用两辆特制的卡车送货，该种卡车最多可运送1818副棺木副棺木 ，每周送货五天。要求制定出该地区的车辆路线和时刻，每周送货五天。要求制定出该地区的车辆路线和时刻 表。表。殡仪馆的位置及其一周的订货量殡仪馆的位置及其一周的订货量凯斯寿材公司密歇根中部地区凯斯寿材公司密歇根中部地区 首先要将该区域划分为五个每日的客户群；首先要将该区域划分为五个每日的客户群；
