物流优化技术ppt课件-第6章-物流网络规划

第六章第六章 物流网络规划物流网络规划第六章 物流网络规划一、物流中心规划v1 1、物流中心的数目、物流中心的数目v在确定物流中心数目时，除了在确定物流中心数目时，除了服务水平服务水平和和成本成本两个主要因素两个主要因素以外，还要考虑以下因素：以外，还要考虑以下因素：v（1 1）客户的购买方式）客户的购买方式：如客户频繁地少批量需求，则需要：如客户频繁地少批量需求，则需要较多的接近客户的中心；较多的接近客户的中心；v（2 2）竞争环境）竞争环境：一般竞争环境恶劣时需要更多的物流中心，：一般竞争环境恶劣时需要更多的物流中心，以提高顾客的满意度；以提高顾客的满意度；v（3 3）信息网络的完善程度：）信息网络的完善程度：拥有完善的信息网络可使企业拥有完善的信息网络可使企业的仓库数目减少，以信息替代库存。若没有信息网络，企业的仓库数目减少，以信息替代库存。若没有信息网络，企业只能靠增加中心数目达到顾客满意。只能靠增加中心数目达到顾客满意。一、物流中心规划1、物流中心的数目物流优化技术ppt课件-第6章-物流网络规划物流优化技术ppt课件-第6章-物流网络规划2 2 物流中心的选址物流中心的选址v选址问题的类型：选址问题的类型：v按设施数量划分为按设施数量划分为单一设施单一设施的选址和的选址和多个设多个设施施的选址。的选址。v按选择的离散程度分为按选择的离散程度分为连续选址连续选址和和离散选址离散选址。v连续选址连续选址是考察一个连续空间内所有可能的点，并是考察一个连续空间内所有可能的点，并选择其中最优的一个；选择其中最优的一个；v离散选址离散选址是在一系列可能方案中做出选择，这些方是在一系列可能方案中做出选择，这些方案事先已经通过了合理性分析，多用于多设施选址。案事先已经通过了合理性分析，多用于多设施选址。2 物流中心的选址选址问题的类型：物流中心选址应考虑的因素物流中心选址应考虑的因素v(1)(1)与目标顾客的距离与目标顾客的距离v一天能往返的路程为佳一天能往返的路程为佳v(2)(2)自然资源和劳动力的可获得性自然资源和劳动力的可获得性v(3)(3)当地经济环境因素当地经济环境因素v物流量的大小物流量的大小v物流中心设立的目的是降低社会物流成本，若无足够的物流物流中心设立的目的是降低社会物流成本，若无足够的物流量，物流中心的规模效益无法发挥；量，物流中心的规模效益无法发挥；v货物的流向货物的流向v货物的流向决定着物流中心的工作内容和设施设备的配置。货物的流向决定着物流中心的工作内容和设施设备的配置。v如对于供应物流来说，物流中心主要为生产企业提供原材料、如对于供应物流来说，物流中心主要为生产企业提供原材料、零部件，应当选择靠近生产企业的地点，便于降低生产企业零部件，应当选择靠近生产企业的地点，便于降低生产企业的库存，随时为生产企业提供服务。对于销售物流来说，物的库存，随时为生产企业提供服务。对于销售物流来说，物流中心的主要职能是将产品集结、分拣、配送到门店或用户流中心的主要职能是将产品集结、分拣、配送到门店或用户手中，故应选择靠近客户的地点。手中，故应选择靠近客户的地点。物流中心选址应考虑的因素(1)与目标顾客的距离v（3 3）城市的扩张与发展）城市的扩张与发展v城市物流中心的选址，既要考虑城市扩张的速度和方向，城市物流中心的选址，既要考虑城市扩张的速度和方向，又要考虑节省短驳费用和减少装卸次数。又要考虑节省短驳费用和减少装卸次数。v（4 4）交通便利条件）交通便利条件v对于综合型物流中心，一定要选择在两种以上运输方式的对于综合型物流中心，一定要选择在两种以上运输方式的交汇地。交汇地。v4 4、自然环境因素、自然环境因素v1 1）地理因素）地理因素v如地形对仓库基建投资的影响也很大，地形坡度应在如地形对仓库基建投资的影响也很大，地形坡度应在1 14%4%之间；应远离闹市或居民区；与易发生火灾的单位保持一之间；应远离闹市或居民区；与易发生火灾的单位保持一定安全距离，如油库、加油站、化工厂等；定安全距离，如油库、加油站、化工厂等；v2 2）气候因素）气候因素v如自然环境中的湿度、盐分、降雨量、风向、风力等。如自然环境中的湿度、盐分、降雨量、风向、风力等。v5 5、当地产业政策、税收的法规、当地产业政策、税收的法规v政策环境条件包括企业优惠措施（如土地提供、减税等）、政策环境条件包括企业优惠措施（如土地提供、减税等）、城市规划（土地开发、道路建设计划）、地区产业政策等城市规划（土地开发、道路建设计划）、地区产业政策等（3）城市的扩张与发展6.2 6.2 中心选址的技术方法中心选址的技术方法v主要方法：主要方法：v经验寻优法经验寻优法：不追求理论最佳，而追求较优：不追求理论最佳，而追求较优和快速；和快速；v数学规划法数学规划法：问题描述：问题描述数学模型数学模型用规划用规划软件求解；软件求解；v仿真模拟法仿真模拟法：拟定多种可行方案：拟定多种可行方案仿真软件仿真软件模拟模拟仿真结果仿真结果结果评价结果评价选优选优6.2 中心选址的技术方法主要方法：6.2.1 6.2.1 经验寻优法的例子经验寻优法的例子#1#1一个产品，两个工厂（一个产品，两个工厂（P P），两个中心（），两个中心（W W），三个零售店（），三个零售店（C C）生产能力生产能力市场需求市场需求物流成本物流成本6.2.1 经验寻优法的例子#1一个产品，两个工厂（P），两6.2.1 6.2.1 经验寻优法的例子经验寻优法的例子#1#1v基本规则基本规则选择配送成本最低的中心来满足每个市场选择配送成本最低的中心来满足每个市场物流成本物流成本解决方案解决方案总成本总成本=250000+1100000+250000+260000+5140000=11200006.2.1 经验寻优法的例子#1基本规则物流成本解决方案总成6.2.1 6.2.1 经验寻优法例子经验寻优法例子#2#2v基本规则基本规则v对每个市场，选择到客户的总运输成本最低的仓库来提供服务对每个市场，选择到客户的总运输成本最低的仓库来提供服务解决方案解决方案总成本总成本=3*50000+3*60000+5*50000+4*40000=7400006.2.1 经验寻优法例子#2基本规则解决方案总成本=3经验寻优法的特点经验寻优法的特点v简单可操作性强简单可操作性强v解决速度快解决速度快v不保证最优，但求较好方案不保证最优，但求较好方案v适合适合作估计值作估计值数据量大的情况数据量大的情况经验寻优法的特点简单可操作性强6.2.2 6.2.2 数学规划方法数学规划方法v（1 1）连续点选址模型）连续点选址模型-重心法重心法XYO6.2.2 数学规划方法（1）连续点选址模型-重心法X重心法重心法v重点法是通过考虑重点法是通过考虑产品市场的位置、产品市场的位置、各市场对产品的需各市场对产品的需求量和相应的运输求量和相应的运输费用来确定最佳配费用来确定最佳配送中心位置。送中心位置。v某公司有两个工厂某公司有两个工厂向仓库供货，再由向仓库供货，再由仓库供应三个分销仓库供应三个分销中心。工厂和分销中心。工厂和分销中心的空间分布如中心的空间分布如图所示，要求寻找图所示，要求寻找使运输成本最小的使运输成本最小的仓库位置。仓库位置。M1M2M3P1P2重心法重点法是通过考虑产品市场的位置、各市场对产品的需求量和选址步骤选址步骤v（1 1）确定各产地和需求地的坐标值）确定各产地和需求地的坐标值X X、Y Y，同，同时确定各点货物运输量和运输费率；时确定各点货物运输量和运输费率；选址步骤（1）确定各产地和需求地的坐标值X、Y，同时确定各点（2 2）估算初始选址位置）估算初始选址位置目标：是使所选位置与供货地和需求地之间的运输费用最小。所选位置到i点的距离到i点的运输费率运输总成本运输量（2）估算初始选址位置目标：是使所选位置与供货地和需求地之间 的表示方法的表示方法起点i终点jyxyiyjxixj直线距离折线距离 的表示方法起点i终点jyxyiyjxixj直线直线距离的计算直线距离的计算v直线距离一般用于城市间的配送问题选址，直线距离一般用于城市间的配送问题选址，在这些问题中，直线距离是可以接受一近似在这些问题中，直线距离是可以接受一近似值。城市间配送问题中的实际路线距离可以值。城市间配送问题中的实际路线距离可以通过将直线距离乘以一个适当的系数来进行通过将直线距离乘以一个适当的系数来进行计算（美国大陆是计算（美国大陆是1.21.2，在东南美洲是，在东南美洲是1.261.26）。）。直线距离的计算直线距离一般用于城市间的配送问题选址，在这些折线距离的计算折线距离的计算v折线距离一般用在道路较规则的城市内的配折线距离一般用在道路较规则的城市内的配送问题及具有直线通道的工厂及仓库内的布送问题及具有直线通道的工厂及仓库内的布置、物料搬运设备的顺序移动等问题中。置、物料搬运设备的顺序移动等问题中。折线距离的计算折线距离一般用在道路较规则的城市内的配送问题及v设待定地址坐标为（设待定地址坐标为（X0X0，Y0Y0），将直线），将直线距离代入总运输费用距离代入总运输费用TCTC函数公式，并求函数公式，并求TCTC对对X0X0和和Y0Y0的偏导，令其等于的偏导，令其等于0 0，即求得：，即求得：设初始坐标为：设待定地址坐标为（X0，Y0），将直线距离代入总运输费用TC初选地点位置计算初选地点位置计算初选地点位置计算初选地点位置计算结果初选地点位置计算结果初选地点位置计算结果（3 3）计算各供需点到初选地点）计算各供需点到初选地点的距离的距离d di i（3）计算各供需点到初选地点的距离di(4)(4)对初始选址位置进行修正对初始选址位置进行修正 将计算出的将计算出的di代入上式，得到修正的选址坐标；根据修正的选址坐标代入上式，得到修正的选址坐标；根据修正的选址坐标再计算再计算di,再将再将di值代入上式计算，直到计算出的选址坐标不再变化，或变化值代入上式计算，直到计算出的选址坐标不再变化，或变化很小，则停止计算，所得结果就是最优位置。很小，则停止计算，所得结果就是最优位置。终止准则终止准则：1）根据经验和以前的试验结果直接设一个迭代次数）根据经验和以前的试验结果直接设一个迭代次数N；2）将每次得到的迭代结果与前一次结果比较，当结果变化小于某一规）将每次得到的迭代结果与前一次结果比较，当结果变化小于某一规定的值时，就停止计算，即所得最优值。定的值时，就停止计算，即所得最优值。(4)对初始选址位置进行修正 将计算出的di代入上式，得到修（5 5）计算最优地址的总成本）计算最优地址的总成本（5）计算最优地址的总成本实例分析：v某物流园区，每年需要从P1地运来铸铁，从P3地运来煤炭，从P4地运来日用百货，各地与某城市中心的距离和每年的材料运量如表所示。实例分析：某物流园区，每年需要从P1地运来铸铁，从P3地运来练习题练习题v已知某铸造厂需要从已知某铸造厂需要从P1P1地运来铸铁，从地运来铸铁，从P2P2地运地运来礁碳，其铸件产品将运往来礁碳，其铸件产品将运往P3P3和和P4P4两个需求地，两个需求地，以上各地的位置、年运量及运输费率如下表，以上各地的位置、年运量及运输费率如下表，试用重心法确定该厂的合理位置。试用重心法确定该厂的合理位置。初始位置(38,42),费用：191670迭代最佳位置（42，34），费用：188708练习题已知某铸造厂需要从P1地运来铸铁，从P2地运来礁碳，其(2)(2)离散点选址模型离散点选址模型v覆盖模型覆盖模型-对于需求已知的需求点，对于需求已知的需求点，如何确定一组服务设施来满足这些需求如何确定一组服务设施来满足这些需求点的需求点的需求。v具体有集合覆盖模型和最大覆盖模型。具体有集合覆盖模型和最大覆盖模型。集合覆盖模型最大覆盖模型(2)离散点选址模型覆盖模型-对于需求已知的需求点，如集合覆盖法集合覆盖法多设施选址多设施选址123456789200200300100350400300150150250300300200300300集合覆盖法多设施选址1234567892002003001集合覆盖法集合覆盖法多设施选址多设施选址v某区域对某产品有某区域对某产品有9 9个需求地，分布情况如图，各需个需求地，分布情况如图，各需求点之间的相对距离如图中数字，为保证各需求点求点之间的相对距离如图中数字，为保证各需求点的产品需求能及时满足，要求配送中心到各需求点的产品需求能及时满足，要求配送中心到各需求点的距离不超过的距离不超过300km300km，在现有需求点的基础上确定配，在现有需求点的基础上确定配送中心的合理数量和位置。送中心的合理数量和位置。v步骤：步骤：v1 1）以每个需求点作为侯选位置，找出它们能够服务）以每个需求点作为侯选位置，找出它们能够服务的需求点的集合的需求点的集合A A（j);j);v2)2)从从A A（j)j)中找出属于其它侯选点的子集，并删去，中找出属于其它侯选点的子集，并删去，以简化问题；以简化问题；v3 3）确定配送中心的合理数量和位置）确定配送中心的合理数量和位置集合覆盖法多设施选址某区域对某产品有9个需求地，分布情况如解：解：3，4，6，7为可选方案为可选方案再进一步考虑再进一步考虑最少设施最少设施的原则，（的原则，（3，7）为最）为最佳的设施位置，即要满佳的设施位置，即要满足所有需求，最少需要足所有需求，最少需要设置设置2个配送中心，个配送中心，位置应选择（位置应选择（3，7）123456789200200300100350400300150150250300300200300300解：3，4，6，7为可选方案1234567892002003二、物流线路优化v节余里程问题v最小费用最大流问题二、物流线路优化节余里程问题1、节余里程法v节约里程法的基本思想 v 送货最直接的想法是利用两辆车分别为A、B两个客户配送，如图B所示，车辆的实际运行距离是2a+2b；然而，如改用由一辆车巡回配送，如图C所示，实际运行距离为a+b+c；当道路状况没有特殊规定时，可节约车辆运行距离为(2a+2b)-(a+b+c)=a+b-c；根据三角形两边之和大于第三边之定理，a+b-c0，则这个节约量称为“节约里程”。1、节余里程法节约里程法的基本思想 第一步，计算网络结点之间的最短距离，可采用最短路求解法。第一步，计算网络结点之间的最短距离，可采用最短路求解法。第二步，根据最短路结果，计算出各客户之间的节约里程，并按节约行程按大小顺序排列 v计算举例，A-B的节约行程：vP-A距离：a=8 P-B距离：b=5 A-B距离：c=8v则A-B的节约行程为a+b-c=5 第二步，根据最短路结果，计算出各客户之间的节约里程，并按节约结 果v1、其配送路线为023467510，v2、最短里程为：57311587854 结 果1、其配送路线为02346751节约法的注意事项v1、适用于有稳定客户群的配送中心，v2、各配送线路的负荷要尽量均衡v3、实际选择线路时还要考虑道路状况；v4、要考虑驾驶员的作息时间及客户要求的交货时间；v5、可利用计算机软件进行运算，直接生成结果 节约法的注意事项1、适用于有稳定客户群的配送中心，2、最小费用最大流问题v对一费用容量网络，具有相同流量对一费用容量网络，具有相同流量 f 的可行的可行流中，总费用最小的可行流称为该费用容量流中，总费用最小的可行流称为该费用容量网络关于流量网络关于流量 f 的最小费用流，简称流量为的最小费用流，简称流量为 f 的最小费用流。的最小费用流。2、最小费用最大流问题对一费用容量网络，具有相同流量 f 的二、求解最小费用最大流问题的对偶法二、求解最小费用最大流问题的对偶法1、求解途径：、求解途径：（1 1）始终保持网络中的可行流是最小费用流，始终保持网络中的可行流是最小费用流，然后不断调整，使然后不断调整，使流量逐步增大流量逐步增大流量逐步增大流量逐步增大，最终成为最，最终成为最小费用的最大流；小费用的最大流；（2 2）始终保持可行流是最大流，通过不断调整始终保持可行流是最大流，通过不断调整使使费用逐步减小费用逐步减小费用逐步减小费用逐步减小，最终成为最大流量的最小费，最终成为最大流量的最小费用流。用流。二、求解最小费用最大流问题的对偶法1、求解途径：2、算法原理、算法原理（1）定理）定理 若若X 是流量为是流量为f(X)的最的最小费用流，小费用流，是关于是关于X 的所有增广的所有增广链中费用最小的增广链，那麽沿着链中费用最小的增广链，那麽沿着去调整去调整X得到的新的可行流得到的新的可行流 就就是流量为是流量为 f()的最小费用流。的最小费用流。2、算法原理（2）实现思路）实现思路 基于第一种求解途径，根据上述基于第一种求解途径，根据上述定理，只要找到最小费用增广链，在定理，只要找到最小费用增广链，在该链上调整流量，得到增加流量后的该链上调整流量，得到增加流量后的最小费用流。循环往复直至求出最小最小费用流。循环往复直至求出最小费用最大流。费用最大流。（2）实现思路 实施中的关键实施中的关键 构造增广费用网络图（即扩展费用网络图），构造增广费用网络图（即扩展费用网络图），借助最短路算法寻找最小费用增广链。借助最短路算法寻找最小费用增广链。增广费用网络图的构造方法增广费用网络图的构造方法将网络中的每一条弧（将网络中的每一条弧（vi,vj）都变成一对）都变成一对方向相反的弧，以形成四通八达的方向相反的弧，以形成四通八达的“路路”，权数定义如下：，权数定义如下：实施中的关键 增广费用网络图的构造方法零流弧上零流弧上 Wij=cij 原有弧（流量可以增加）原有弧（流量可以增加）后加弧（流量不能再减少）后加弧（流量不能再减少）饱和弧上饱和弧上wij=原有弧（流量不能再增加）原有弧（流量不能再增加）-cij 后加弧（流量可以减少）后加弧（流量可以减少）非饱和且非零流非饱和且非零流 (0 xijbij)弧上弧上 cij 原有弧（流量可以增加）原有弧（流量可以增加）-cij 后加弧（流量可以减少）后加弧（流量可以减少）Wij=零流弧上 Wij=cij 原有弧（流量可以增加）将上述思想加以简化，出现将上述思想加以简化，出现处相应的弧处相应的弧不画，按下面的方法具体构造增广费用网不画，按下面的方法具体构造增广费用网络图络图：零流弧上零流弧上，保持原弧不变，将单位费用，保持原弧不变，将单位费用作为权数，即作为权数，即wij=cij:Vi Vj(bij,cij)将上述思想加以简化，出现处相应的弧不画，按下面的方法具体构非饱和弧上非饱和弧上，原有弧以单位费用作权数，原有弧以单位费用作权数，后加弧（虚线弧）以单位费用的负数作后加弧（虚线弧）以单位费用的负数作权数：权数：ViVj（bij,cij）(bij,-cij)非饱和弧上，原有弧以单位费用作权数，后加弧（虚线弧）以单位费 Vi Vj(bij,-cij)饱和弧上饱和弧上,去掉原有弧去掉原有弧,添上后加弧添上后加弧(虚虚线弧线弧),权数为单位费用的负数：权数为单位费用的负数：Vi Vj(bij,-cij)饱和弧上,去掉原有弧,添上后 于是，在容量网络中寻找最小费于是，在容量网络中寻找最小费用增广链就相当于在增广费用网络图用增广链就相当于在增广费用网络图（扩展费用网络图）中寻找从发点到（扩展费用网络图）中寻找从发点到收点的最短路。收点的最短路。注意注意 将找到的最短路还原到原网络将找到的最短路还原到原网络图中（虚线弧改成原图中的反向弧）。图中（虚线弧改成原图中的反向弧）。于是，在容量网络中寻找最小费用增广链就相当于在增3、步骤：、步骤：第一步第一步-用用Ford-Fukerson算法求出算法求出该容量网络的最大流量该容量网络的最大流量fmax；（本步骤的作用是什麽？）（本步骤的作用是什麽？）第二步第二步-取初始可行流为零流，其必取初始可行流为零流，其必为流量为为流量为0的最小费用流的最小费用流3、步骤：第二步-取初始可行流为零流，其必为流量为0的 第三步第三步-一般为第一般为第k-1次迭代，得次迭代，得一最小费用流一最小费用流X(k-1)，对当前可行流构，对当前可行流构造增广费用网络图造增广费用网络图W(X(k-1)，用最短，用最短路算法求出从发点到收点的最短路。路算法求出从发点到收点的最短路。（若不存在最短路，则（若不存在最短路，则X(k-1)即最小费即最小费用最大流，停止迭代。否则，转下一用最大流，停止迭代。否则，转下一步。）步。）第三步-一般为第k-1次迭代，得一最小费 第四步第四步-将最短路还原成原网将最短路还原成原网络图中的最小费用增广链络图中的最小费用增广链，在，在上上对可行流对可行流X(k-1)进行调整，得到新的进行调整，得到新的可行流图，若其流量等于可行流图，若其流量等于fmax,迭代结迭代结束。否则转入第一步，进入下一次束。否则转入第一步，进入下一次迭代过程。迭代过程。第四步-将最短路还原成原网络图中