运输决策.ppt

运输决策运输决策运输服务方式的选择路线的选择行车路线制定运输服务方式的选择运输服务方式的选择 公路、铁路、水路、航空公路、铁路、水路、航空运输服务的成本（运费）、平均运输时运输服务的成本（运费）、平均运输时间（速度）和运输时间的波动性（可靠间（速度）和运输时间的波动性（可靠性）是选择运输方式时考虑的因素。性）是选择运输方式时考虑的因素。基本的成本权衡基本的成本权衡 如果不将运输方式作为竞争手段，则最如果不将运输方式作为竞争手段，则最佳运输方式就是能够使该运输服务的成佳运输方式就是能够使该运输服务的成本与运输服务水平（速度、可靠性）导本与运输服务水平（速度、可靠性）导致的相关库存成本之间达到平衡的运输致的相关库存成本之间达到平衡的运输服务方式。服务方式。考虑竞争因素考虑竞争因素 对于买方而言，速度越快越好、可靠性对于买方而言，速度越快越好、可靠性越高越好。因此供应商可能为了创造有越高越好。因此供应商可能为了创造有竞争力的服务优势，追求令买方满意的竞争力的服务优势，追求令买方满意的优质运输服务水平，而提高了运输服务优质运输服务水平，而提高了运输服务成本。成本。运输服务方式的选择运输服务方式的选择 公路、铁路、水路、航空公路、铁路、水路、航空路线选择路线选择 找到运输工具在公路网、铁路线等的最佳路线以找到运输工具在公路网、铁路线等的最佳路线以尽可能的缩短运输时间或运输距离，从而达到降尽可能的缩短运输时间或运输距离，从而达到降低运输成本、改善运输服务的目标。低运输成本、改善运输服务的目标。路线选择问题有三种基本类型：路线选择问题有三种基本类型：一是起点和终点不同的单一路径规划；一是起点和终点不同的单一路径规划；二是多个起点和终点的路径规划；二是多个起点和终点的路径规划；三是起点和终点相同的路径规划。三是起点和终点相同的路径规划。1 1、起点和终点不同的单一问题、起点和终点不同的单一问题（网络规划中一个发点和一个收点的的最短路问题）（网络规划中一个发点和一个收点的的最短路问题）手手工工算算法法,DijstraDijstra算算法法/利利用用计计算算机机求求解解：把把网网络络中中边边和和节节点点的的资资料料都都存存入入数数据据库库中中，选选好好某某个个起起点点和和终终点后，计算机可以很快就能算出最短路径。点后，计算机可以很快就能算出最短路径。绝绝对对的的最最短短距距离离路路径径并并不不能能说说明明穿穿越越网网络络的的最最短短时时间间各各条条路路线线的的运运行行质质量量问问题题。因因此此，可可以以对对运运行行时时间和距离都设定权数，甚至是动态权数。间和距离都设定权数，甚至是动态权数。俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃思堡沃思堡90分钟分钟138348153489012013248150126132608484126JIHGFEDCBA 从上图中找出得克萨斯州的阿马里洛与沃思堡之间行从上图中找出得克萨斯州的阿马里洛与沃思堡之间行车时间最短的路线。节点之间的每条链上都标有相应的时车时间最短的路线。节点之间的每条链上都标有相应的时间，节点代表公路的连接处。间，节点代表公路的连接处。66俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃恩堡沃恩堡90分钟分钟138348153489012013248150126132608484126JIHGFEDCBA0,0A,A,A,A,A,A,348A,138A,90A,66俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃恩堡沃恩堡90分钟分钟138348153489012013248150126132 608484126JIHGFEDCBA0,0A,A,B,174A,A,C,291A,138A,90A,66俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃恩堡沃恩堡90分钟分钟138348153489012013248150126132 608484126JIHGFEDCBA0,0A,A,B,174C,228A,C,291A,138A,90A,66俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃恩堡沃恩堡90分钟分钟138348153489012013248150126132 608484126JIHGFEDCBA0,0A,E,258B,174C,228AC,291A,138A,90A,66俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃恩堡沃恩堡90分钟分钟138348153489012013248150126132 608484126JIHGFEDCBA0,0F,283E,258B,174C,228F,360C,291A,138A,90A,66俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃恩堡沃恩堡90分钟分钟138348153489012013248150126132 608484126JIHGFEDCBA0,0F,283E,258B,174C,228F,360C,291A,138A,90I,38466俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃恩堡沃恩堡90分钟分钟138348153489012013248150126132 608484126JIHGFEDCBA0,0F,283E,258B,174C,228H,351C,291A,138A,90I,38466俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃恩堡沃恩堡90分钟分钟138348153489012013248150126132 608484126JIHGFEDCBA0,0F,283E,258B,174C,228D,339C,291A,138A,90I,38466俄克拉俄克拉荷马城荷马城起点起点阿马里洛阿马里洛终点终点沃恩堡沃恩堡90分钟分钟138348153489012013248150126132 608484126JIHGFEDCBA0,0F,283E,258B,174C,228D,339C,291A,138A,90I,384662 2、多个起点和终点的问题、多个起点和终点的问题多多个个货货源源地地服服务务多多个个目目的的地地，要要指指定定各各目目的的地地的的供供货货地地，同同时时要要找找到到供供货货地地、目目的的地地之之间间的的最最佳佳路径。路径。适适用用于于多多个个供供应应商商、工工厂厂或或仓仓库库服服务务于于多多个个客客户户。如如果果各各供供货货地地能能够够满满足足的的需需求求有有限限，则则问问题题会会更更复复杂杂。解决这类问题可以运用线性规划的运输规划方法。解决这类问题可以运用线性规划的运输规划方法。某玻璃制造商与三个位于不同地点的纯碱供应商鉴定合同，某玻璃制造商与三个位于不同地点的纯碱供应商鉴定合同，由他们供货给三个工厂，条件是不超过合同所定的数量，但必由他们供货给三个工厂，条件是不超过合同所定的数量，但必须满足生产需求。图中运输费率是每个供应商到每个工厂之间须满足生产需求。图中运输费率是每个供应商到每个工厂之间最短路径的运输费率。最短路径的运输费率。供应商供应商A供应商供应商B供应商供应商C工厂工厂工厂工厂工厂工厂 400=600 700 500=300=500123供量供量A476 400B555 700C958 500需量需量600500300供大于求的运输问题供大于求的运输问题供求平衡供求平衡表上作业法表上作业法123 虚需求地虚需求地供量供量A4760400B5550700C9580500需量需量600500300200表上作业法：表上作业法：最小元素法求初始方案；最小元素法求初始方案；闭回路法检验；闭回路法检验；闭回路法调整。闭回路法调整。123 虚需求虚需求地地供量供量A4760400B5550700C9580500需量需量600500300200最小元素法求初始方案最小元素法求初始方案4002005000300200运量调整量运量调整量LOGWARE 中的中的TRANLP软件求解。软件求解。至：至：自自4000020020030003000从供应商从供应商A运输运输400吨到工厂吨到工厂1。从供应商从供应商B运输运输200吨到工厂吨到工厂1。从供应商从供应商B运输运输200吨到工厂吨到工厂2。从供应商从供应商B运输运输300吨到工厂吨到工厂3。从供应商从供应商C运输运输300吨到工厂吨到工厂2。运送总量运送总量1400吨，最低总成本吨，最低总成本6600单位。单位。3 3、起迄点重合的问题、起迄点重合的问题-企业拥有运输工具企业拥有运输工具 从某仓库送货到零售店然后返回的路线（从中央配送中心送从某仓库送货到零售店然后返回的路线（从中央配送中心送货到食品店或药店）；货到食品店或药店）；从零售店到客户本地配送的路线设计（商店送货上门）；从零售店到客户本地配送的路线设计（商店送货上门）；小车、送报车、垃圾收集车和送餐车等的路线设计。小车、送报车、垃圾收集车和送餐车等的路线设计。由于要求车辆必须返回起点行程才结束，找出途径点的顺由于要求车辆必须返回起点行程才结束，找出途径点的顺序，使其满足必须经过所有点且总出行时间或总距离最短的要序，使其满足必须经过所有点且总出行时间或总距离最短的要求求 “旅行推销员旅行推销员”或或“中国邮递员中国邮递员”问题。问题。如果某个问题中包含很多个点，要找到最优路径是不切实如果某个问题中包含很多个点，要找到最优路径是不切实际的，因为许多现实问题的规模太大，即使用最快的计算机进际的，因为许多现实问题的规模太大，即使用最快的计算机进行计算，求最优解的时间也非常长。感知法和启发式求解法是行计算，求最优解的时间也非常长。感知法和启发式求解法是求解这类问题的好方法。求解这类问题的好方法。DD各点空间相连各点空间相连合理的经停路线中各条线路之间是不交叉的，并且只要有可合理的经停路线中各条线路之间是不交叉的，并且只要有可能路径就会呈凸形，或水滴状。能路径就会呈凸形，或水滴状。感知法感知法图中有关卡、单行线、交通拥堵时图中有关卡、单行线、交通拥堵时计算机求解。计算机求解。8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 81819151614131211109876543212017W安休瑟安休瑟布喜公司（布喜公司（Anheuser-Busch Company)：售货员售货员通过流动卡车销售啤酒和其它饮料，卡车由当地销人员所有。公通过流动卡车销售啤酒和其它饮料，卡车由当地销人员所有。公司销售员和当地经销人员一样都是收取佣金，因此都不希望每天司销售员和当地经销人员一样都是收取佣金，因此都不希望每天向向客户提供服务时花费客户提供服务时花费不必要的时间，行走不必要的时间，行走多余的路程。多余的路程。卡车从仓库出发，卡车从仓库出发，经过所有的客户点，经过所有的客户点，再回到仓库，运行过再回到仓库，运行过程中距离最短的路径程中距离最短的路径。网格地图（坐标、距离）网格地图（坐标、距离）图钉（客户、编号）图钉（客户、编号）这是ROUTESEQ的运行结果空间上不相连的点空间上不相连的点各点之间的空间关系是扭曲的，需要说明各点之间的确切各点之间的空间关系是扭曲的，需要说明各点之间的确切距离或时间。距离或时间。这时，感知法不适用，可以利用这时，感知法不适用，可以利用STORM中的流动推销员中的流动推销员模块求解。模块求解。ABDCW312334341726474867仓库仓库配送配送中心中心运行时间运行时间行车路线和时刻表的制定行车路线和时刻表的制定1.每个站点既要取一定量的货，又要送一定量的货每个站点既要取一定量的货，又要送一定量的货2.使用多部车辆，每部车的载货重量和容积不同使用多部车辆，每部车的载货重量和容积不同3.司机的总驾驶时间达到一定上限时，须休息至少司机的总驾驶时间达到一定上限时，须休息至少小时小时4.每个站点每天只允许在特定的时间内取货送货每个站点每天只允许在特定的时间内取货送货（称为时间窗）（称为时间窗）5.途中只有在送货后才能取货途中只有在送货后才能取货6.允许驾驶员每天在特定的时间休息和用餐允许驾驶员每天在特定的时间休息和用餐.合理路线和时刻表的制定原则合理路线和时刻表的制定原则 原则：安排车辆负责相互距离最近的站点的货物运输。原则：安排车辆负责相互距离最近的站点的货物运输。仓库仓库仓库仓库如果考虑作业的均衡性？如果考虑作业的均衡性？原则：安排车辆各日途经的站点时，应注意使站原则：安排车辆各日途经的站点时，应注意使站点群更加紧凑。点群更加紧凑。DD 原则原则3：从距仓库最远的站点开始设计路线。找出：从距仓库最远的站点开始设计路线。找出其相应的站点群分派载货能力能满足该站点群需要的卡其相应的站点群分派载货能力能满足该站点群需要的卡车。由远及近考虑。车。由远及近考虑。原则原则4：卡车的行车路线应呈水滴状。各条线路之：卡车的行车路线应呈水滴状。各条线路之间尽量没有交叉。（时间窗、送货之后才能取货的除外）间尽量没有交叉。（时间窗、送货之后才能取货的除外原则原则5：尽可能使用最大的车辆进行运送（总距离：尽可能使用最大的车辆进行运送（总距离最，使用车辆数量最少）。最，使用车辆数量最少）。原则原则6：取货、送货应混合安排。边送边取。：取货、送货应混合安排。边送边取。原则原则7：过于遥远而无法归入群落的站点，采用其：过于遥远而无法归入群落的站点，采用其他配送方式（邮政等）。他配送方式（邮政等）。原则原则8：避免时间窗过短。：避免时间窗过短。2.行车路线和时刻表的制定方法行车路线和时刻表的制定方法扫描法扫描法:手工计算。箱式载货车的载货量是手工计算。箱式载货车的载货量是10000件。需要件。需要多少条线路？每条线路上的站点如何排列？多少条线路？每条线路上的站点如何排列？D300030001000300020002000200020002000100020004000D300030001000300020002000200020002000100020004000起点不同，最终方案不同。起点不同，最终方案不同。节约法节约法(ROUTER)目标是使所有车辆行驶的总里程最短，进而为所目标是使所有车辆行驶的总里程最短，进而为所有站点提供服务的卡车数量最少。有站点提供服务的卡车数量最少。初始路线初始路线线路里程线路里程AB将两个站点合并到同一路线上的将两个站点合并到同一路线上的里程里程节约的距离为节约的距离为S=dAO+dOB-dABAB原理：原理：节约法能够处理包含实际应用中的许多重要的约节约法能够处理包含实际应用中的许多重要的约束条件。束条件。指定各路线途径站点的同时，确定站点的先指定各路线途径站点的同时，确定站点的先后顺序。后顺序。行车时间是否超过允许的最长驾驶时间。行车时间是否超过允许的最长驾驶时间。各站点时间窗的要求是否满足。各站点时间窗的要求是否满足。节约法不能保证得到最优解，一般得到满意解。节约法不能保证得到最优解，一般得到满意解。例：瑞格尔金属公司（例：瑞格尔金属公司（Regal Metals）生产生产商用楼卫生间用的钢质隔板。位于俄亥俄州托商用楼卫生间用的钢质隔板。位于俄亥俄州托莱多的工厂（莱多的工厂（X=420,Y720)将订单将订单货物累积起来每周向个建筑工地送货一次。工货物累积起来每周向个建筑工地送货一次。工厂拥有辆载重厂拥有辆载重40000磅的卡车。该公司某一周磅的卡车。该公司某一周的送货情况如下：的送货情况如下：站点站点 建筑工地建筑工地 订货量订货量米尔沃基米尔沃基 2208003000芝加哥芝加哥24072031500底特律底特律47079016500布法罗布法罗6708606000克里夫兰克里夫兰5407304500匹兹堡匹兹堡6306806750辛辛那提辛辛那提4205703750路易斯威尔路易斯威尔3704906000圣路易斯圣路易斯1305007500孟孟菲斯菲斯1802709000诺克斯威尔诺克斯威尔4803605250亚特兰大亚特兰大48021018000哥伦比亚哥伦比亚6602503000罗利罗利7603906750巴尔的摩巴尔的摩81064011250总计总计138750车辆调度原则：车辆调度原则：本周所有的货物要一次性发出；本周所有的货物要一次性发出；托莱多的发车时间不能早于早晨托莱多的发车时间不能早于早晨7：00；不能超过卡车的载货能力；不能超过卡车的载货能力；所有的卡车都必须返回托莱多的工厂；所有的卡车都必须返回托莱多的工厂；送货时间为早晨送货时间为早晨 7：00和下午：和下午：00之间；之间；驾驶员在中午驾驶员在中午12：00以后又一小时的午餐时间；以后又一小时的午餐时间；晚上晚上7：00以后有一整晚（以后有一整晚（12小时）的休息时间；小时）的休息时间；在大湖区行车受特别限制，平均车速为英里小时；在大湖区行车受特别限制，平均车速为英里小时；各站点的卸货时间为各站点的卸货时间为30分钟。公路里程要比用坐标计算的分钟。公路里程要比用坐标计算的直线距离长直线距离长21%。司机和卡车的成本为。司机和卡车的成本为1.3美元英里。不外出美元英里。不外出送货，司机在场内工作。送货，司机在场内工作。配送路线、配送到达时间。配送路线、配送到达时间。