第八章 运输及配送路线的优化

第八章运输及配送路线的优化第一节运输方式的选择一、运输方式选择的原则（一）安全性原则（二）及时性原则（三）准确性原则（四）经济性原则二、运输方式选择的定量分析法•基于运输成本与库存成本的总成本分析方法•例8-1某公司欲将产品从位置A的工厂运往位置B的公司自有仓库，年运量D=700000件，产品单价C=30元，年存货成本I=产品价格的30％。公司希望选择使总成本最小的运输方式。据估计，运输时间每减少一天，平均库存成本可以减少1％。各种运输服务方式的有关参数见表8-1：二、运输方式选择的定量分析法表8-1运输方式费率R(元/件)时间T(天)年运送批次平均存货量Q/2铁路0.12110100000驮背0.15142046500公路0.252042000航空1.424020250二、运输方式选择的定量分析法•解：•以年总成本最低为原则来选择合适的运输方式。这里，总成本=运输费用+库存成本；•其中，运输费用=运输量费率•库存成本=在途运输库存成本+工厂存货成本+仓库存货成本•在途运输库存费用=ICDT/365•工厂存货成本=ICQ/2•仓库存货成本=I（C+R）Q/2•代入各种运输方式的基本数据信息，将相应的成本计算结果列入表8-2。二、运输方式选择的定量分析法表8-2各种运输方式成本计算结果由表中结果可知，总成本最低的是公路运输方式，总成本为984821元，其次是驮背运输，成本最高的是铁路运输。按照总成本最低的原则，适合选择公路运输方式。成本类型计算公式铁路运输驮背运输公路运输航空运输运输成本RD70000105000140000980000在途库存ICDT/3653452052416448630134521工厂存货ICQ/2900000416500378000182250仓库存货I(C+R)Q/2903000420593380520190755总成本221820511857379848211387526第三节物资运输调配决策•一、多起迄点间的直达运输设某物资有m个产地A1，A2，…，Am；供应n个销售地B1，B2，…，Bn；已知Ai的产量为ai（i=1，2，…，m），Bj的需求量为bj（j=1，2，…，n）。由Ai到Bj的单位运价为Cij。用Xij表示由产地Ai运输到销地Bj的物资量（i＝1，2，…，m；j=1，2，…，n），如图8-1所示。图8-1多点之间的物资运输调拨问题示意图a1a2amb1b2bnCijXij供应地需求地第三节物资运输调配决策（一）产销平衡的运输问题1．产销平衡运输问题数学模型（8-1）约束条件为：（8-2）（8-3）i＝1，2，…，m；j=1，2，…，n且minjijijXCZ11minmijijbX1nj,,2,1mjiijaX1mj,,2,10ijXnjjmiiba11第三节物资运输调配决策（二）产销不平衡的运输问题1．总产量大于总销量即：，则增加一个假想的销地Bn+1，其销量为：（8-4）从产地Ai运往假想销地Bn+1的物资数量实际上是停留在原产地没有运出的物资，因此，相应的运价为0，这样就将不平衡运输问题转化为平衡运输问题。njjmiiba11njjmiinbab111第三节物资运输调配决策2．总销量大于总产量即：，可增加一个假想的产地Am+1，其产量为：（8-5）由于假想的产地并不存在，其产量也不可能存在，由假想产地运往某个销地的物资数量实际上就是该销地不能满足的需求量，因此相应的运价为0，这样就将不平衡运输问题转化为平衡运输问题。miinjjab11miinjjmaba111第三节物资运输调配决策二、存在中间转运的物资调配（一）问题描述如图8-2所示，某物流系统中有f个工厂（供应地），m个流通中心（中转站），n个零售商店（需求地）。已知工厂Ak的生产能力为ak（k=1，2，…，f），流通中心Ti的配送能力为ti（i=1，2，…，m），零售店Bj的需求量为bj（j=1，2，…，n）。由Ak经Ti运到Bj的单位运价为Ckij。求：在工厂生产能力一定，流通中心配送能力限制的条件下，满足零售店需求量的最优运输方案。图8-2有中间转运的物资运输调拨问题t1t2tmb1b2bnCkijXkij供应地需求地a1af中转站第三节物资运输调配决策（二）数学模型用Xkij表示由产地Ak经流通中心Ti运输到零售店Bj的物资量（k=1，2，…，f；i＝1，2，…，m；j=1，2，…，n），这就是问题的决策变量。其目标函数为：（8-6）约束条件为：（1）配送量生产能力的限制：k=1，2，…，f；（8-7）（2）流通中心发送能力的限制：i＝1，2，…，m；（8-8）minjkijkijfkXCZ111minnjkkijmiaX11njikijfkitX1第三节物资运输调配决策（3）满足零售店需求量：j=1，2，…，n；（8-9）（4）变量非负：（8-10）（三）求解方法求解上述问题有两种方法。一种是运用一般的线性规划方法求解，但由于该问题的变量数多、约束方程多，求解过程十分复杂、计算量特别大。另一种方法就是运用运输问题表上作业法，其基本思路是：补充一些虚拟的产地或需求地，将有中转的运输问题转化为无中转的直达运输问题；再进一步转化为供需平衡的运输问题；然后，再运用表上作业法求解。下面通过例题说明第二种方法的应用。fkjkijmibX110kijX第四节单一车辆配送路线的优化一、起迄点不同的单一路线优化（一）动态规划法首先，根据网络结构特征将整个线路网络划分成多个阶段；其次，对每个阶段的决策问题求解；最后对于每一阶段，以初始状态为基础确定下一阶段的可选状态，并计算各状态的代价，然后从中选择代价最小的状态。（二）Dijkstra方法此方法主要用来解决图论中的最短路径问题。广义上，“最短路径”不单指“纯距离”意义上的最短路径，它可以是“经济距离”意义上的最短路径，“时间”意义上的最短路径，“网络”意义上的最短路径等。第四节单一车辆配送路线的优化二、起迄点重合的单一路线优化（一）旅行商问题TSP模型（TravelingSalesmanProblem）TSP模型可描述如下：在一个由n个顶点构成的网络中，要求找出一个包括所有顶点的具有最小耗费（例如最短距离、或最小时间代价）的环路。一个环路也就是一个回路，既然回路是包含了所有顶点的一个循环，所以，可以将任何一个点作为起点和终点。（二）中国邮递员问题邮递员从邮局出发，走遍他所负责的街道，完成投递后返回邮局，怎样走才使总路程最短？城市配送中心为分布在各街道的便民连锁店配送完货物后再返回配送中心；流动推销员从销售中心出发，沿着街道推销商品，最后再返回销售中心，也属于这类问题。由于该类问题是我国学者管梅谷在1962年首先提出的，国际上通称这类问题为中国邮递员问题。第五节多车辆配送路线的优化一、问题概述（一）多车辆路径问题VRP（VehicleRoutingProblem）多车辆路径问题在现实中普遍存在。例如，一家大型物流中心要为成百上千的客户提供送货或取货的服务，就需要对运输车辆的数量及其行驶路线进行规划。（二）多车辆路径问题数学模型模型假设：•（1）单一物流中心，多部车辆配送。•（2）每个需求点由一辆车服务，每个客户点货物需求量不超过车辆的载重容量。•（3）车辆为单一车种，即视为相同的载重量，且有容量限制。•（4）无时窗限制的配送问题。•（5）客户的位置和需求量均为已知。•（6）配送的货物视为同一种商品，便于装载。（三）多车辆路径问题求解方法概述求解上述VRP模型，可以应用精确优化算法、智能优化算法、模拟方法、启发式方法等。第五节多车辆配送路线的优化二、扫描法•描述：扫描法在VRP求解方法中是一种先分群再寻找最佳路线的算法。求解过程分为两步：第一步是分派车辆服务的站点或客户点；第二步是决定每辆车的行车路线。•扫描法的原理是：先以物流中心为原点，将所有需求点的极坐标算出，然后依角度大小以逆时钟或顺时钟方向扫描，若满足车辆装载容量即划分为一群，将所有点扫描完毕后在每个群内部用最短路径算法求出车辆行驶路径。第五节多车辆配送路线的优化•扫描法步骤：1．以物流中心为原点，将所有客户需求点的极坐标计算出来。2．以零角度为极坐标轴，按顺时针或逆时针方向，依角度大小开始扫描。3．将扫描经过的客户点需求量进行累加，当客户需求总量达到一辆车的载重量限制且不超过载重量极限时，就将这些客户划分为一群，即由同一辆车完成送货服务。接着，按照同样的方法对其余客户划分新的客户群，指派新的车辆。4．重复步骤3，直到所有的客户都被划分到一个群中。5．在每个群内部用TSP算法求出车辆行驶最短路径。第五节多车辆配送路线的优化三、节约法节约法描述：节约法的目标是使所有车辆行驶的总里程最短，使提供服务的车辆总数最少。算法的基本思想是：如果将运输问题中的两个回路合并成一个回路，就可缩短线路总里程（即节约了距离），并减少了一辆卡车。举例：如图8-15所示，将两个回路合并成一个回路后，节约的距离为AB=CAO+CBO-CAB。COACBOABO仓库ABO仓库（a）初始路线总里程=COA+CAO+COB+CBOCAOCOB（b）将两个站点合并成同一线路总里程=COA+CAB+CBOCABCOACBO