物流配送管理相关算法及应用教材

1、第五章第五章 物流配送管理相关算法及应用物流配送管理相关算法及应用本章学习内容本章学习内容 第一节第一节 配送中心选址问题配送中心选址问题 第二节第二节 运输计划编制问题运输计划编制问题 第三节第三节 配送路线优化问题配送路线优化问题 第四节第四节 物流配送优化相关问题物流配送优化相关问题 配送中心选址问题配送中心选址问题第一节第一节 一、配送中心选址概述一、配送中心选址概述 配送中心选址是以提高物流系统的配送中心选址是以提高物流系统的经济效益和社会效益为目标，根据供货经济效益和社会效益为目标，根据供货状况、需求分布、运输条件、自然环境状况、需求分布、运输条件、自然环境等因素，用系统工程的方法

2、，对配送中等因素，用系统工程的方法，对配送中心的地理位置进行决策的过程。心的地理位置进行决策的过程。 当一个物流系统中需要设置多个配送当一个物流系统中需要设置多个配送中心，这时不仅要确定配送中心的位中心，这时不仅要确定配送中心的位置，而且还要对配送中心的数量、规置，而且还要对配送中心的数量、规模、服务范围等进行决策，建立一个模、服务范围等进行决策，建立一个服务好、效率高、费用低的物流网络服务好、效率高、费用低的物流网络系统。对此常称为网点布局。系统。对此常称为网点布局。 本课程将配送中心选址与布局统称为选址。一个物流系统只设置一个配送中心，称单中心选址问题，如果设置多个配送中心，则称多中心选址

3、问题。 供应商1供应商2客户1客户2客户3 图图3-1 3-1 单中心配送网络示意图单中心配送网络示意图配送中心配送中心2供应商1供应商2供应商3客户1客户2客户3客户4客户5客户6配送中心1图图3-2 3-2 多中心配送网络示意图多中心配送网络示意图（一）配送中心选址的重要意义（一）配送中心选址的重要意义 配送中心选址合理与否会直接影响到配送系统的服务水平、作业效率和经济效益。所以配送中心选址的目标是：1 1、成本最小化、成本最小化 2 2、服务最优化、服务最优化 3 3、辐射范围最大化、辐射范围最大化 4 4、社会效益最高化、社会效益最高化 配送中心选址属企业战略层的决策问题，对物流系统的

4、合理化具有决定性的意义。 经济性原则经济性原则适应性原则适应性原则（二）（二）配送中心选址的原则配送中心选址的原则 战略性原则战略性原则 协调性原则协调性原则（三）配送中心选址的决策（三）配送中心选址的决策选址包括两个层次的问题：选址包括两个层次的问题：第一：选位，即选择什么地区（区域）设置设施，第一：选位，即选择什么地区（区域）设置设施，沿海还是内地，南方还是北方，等等。在当前沿海还是内地，南方还是北方，等等。在当前全球经济一体化的大趋势之下，或许还要考虑全球经济一体化的大趋势之下，或许还要考虑是国内还是国外；是国内还是国外；第二：定址。地区选定以后，具体选择在该地区第二：定址。地区选定以后

5、，具体选择在该地区的什么位置设置设施，也就是说，在已选定的的什么位置设置设施，也就是说，在已选定的地区内选定一片土地作为设施的具体位置地区内选定一片土地作为设施的具体位置。（四）配送中心选址的影响因素（四）配送中心选址的影响因素自自然然环环境境经经营营环环境境基基础础设设施施其其他他因因素素1 1、自然环境、自然环境 （1）地质条件）地质条件 （2）气象条件）气象条件 （3）地形条件）地形条件 （4）水文条件）水文条件2、经营环境因素、经营环境因素（1）经营环境）经营环境（2）商品特性）商品特性（3）服务水平）服务水平（4）物流费用）物流费用3、基础设施状况、基础设施状况（1）道路、交通条件）

6、道路、交通条件（2）公共设施状况）公共设施状况1、环境保护要求、环境保护要求2、供应商的分布、供应商的分布3、人力资源条件、人力资源条件4、国土资源利用、国土资源利用 5、周边状况、周边状况4、其他因素、其他因素二、配送中心选址的基本条件和数据（一）选址的基本条件 1、需求条件 2、运输条件 3、配送服务的条件 4、流通职能条件 5、用地条件 6、法制条件 7、其他条件 配送中心的选址有单一和多个配送中心的选址，相对而言，单一配送中心的选址需要考虑的因素少一些，多个配送中心的选址除了考虑区位因素以外，还要考虑配送中心之间的网点布局关系。一般而言，一个精确的论证必备如下资料： 1. 业务量资料

7、2. 费用资料 3. 其他资料（二） 配送中心选址应具备的资料配送网点布局配送网点布局是指以企业的物流系统是指以企业的物流系统建设和经济效益为目标，用系统学的建设和经济效益为目标，用系统学的理论和系统工程的方法，综合考虑商理论和系统工程的方法，综合考虑商品的供需状况、运输条件、自然环境品的供需状况、运输条件、自然环境等因素，对配送网点的设置位置、规等因素，对配送网点的设置位置、规模、供货范围等进行研究和设计。模、供货范围等进行研究和设计。151. 业务量资料业务量资料 1) 供货企业至配送中心间的运输量； 2) 向用户配送的货物数量； 3) 配送中心储存货物的数量； 4) 配送中心作业过程中需

8、要进行分装、集装等业务工作量； 5) 配送中心作业过程中需要进行流通加工的作业量； 6) 配送中心作业过程中拣选、配货等工作量2. 费用资料费用资料 1) 供货企业至配送中心间的运输费用。 2) 配送中心至用户的配送费用。 3) 与设施、土地有关的费用，人工费、管理费等。3. 其他资料其他资料 1) 各候选地址的配送路线和距离； 2) 必备的车辆数、作业人员数等； 3) 装卸方式、装卸机械费用等。三、配送中心选址程序 （一）配送中心选址程序（一）配送中心选址程序 （二）配送中心选址方案的经济论证（二）配送中心选址方案的经济论证 （三）配送中心选址的难度（三）配送中心选址的难度（一）配送中心选址

9、程序（一）配送中心选址程序(一一)、配送中心选址程序、配送中心选址程序( (二二) )、配送中心选址方案的经济论证、配送中心选址方案的经济论证 1 1、投资额的确定、投资额的确定 预备性投资、直接投资、相关投资、运营费用预备性投资、直接投资、相关投资、运营费用 2 2、投资效果分析和确定、投资效果分析和确定（三）配送中心选址的难度（三）配送中心选址的难度 1 1、选址因素相互矛盾、选址因素相互矛盾 2 2、不同因素的相对重要性很难确定和度量、不同因素的相对重要性很难确定和度量 3 3、判断的标准会随时间变化而变化、判断的标准会随时间变化而变化22四、物流节点选址布局的方法 定性分析法 定量法1

10、、解析法2、最优化规划法3、启发式方法4、仿真方法5、综合因素评价法（1 1）优缺点比较法）优缺点比较法n具体做法：罗列出各选址方案的优缺点进具体做法：罗列出各选址方案的优缺点进行比较，并对各个方案进行评分，得分最行比较，并对各个方案进行评分，得分最高的方案为最优方案。高的方案为最优方案。（2 2）德尔菲法）德尔菲法定性分析方法定性分析方法一一定量选址方法定量选址方法二二1、解析法2、综合因素评价法3、启发式方法4、仿真方法5、最优化规划法25解析法选址 解析方法就是指解析方法就是指用函数公式计算的方法用函数公式计算的方法，来确定物流，来确定物流中心的选址，通常是指重心方法选址。这种方法把运中

11、心的选址，通常是指重心方法选址。这种方法把运输成本表达为运输需求量、距离以及时间的函数，根输成本表达为运输需求量、距离以及时间的函数，根据距离、需求量、时间或三者的结合，用代数方法来据距离、需求量、时间或三者的结合，用代数方法来求解物流中心的坐标。求解物流中心的坐标。 重心法是重心法是连续模型连续模型，即其选址点是一定区域内的连续，即其选址点是一定区域内的连续坐标。坐标。 解析方法考虑影响因素较少，模型简单，主要适用于解析方法考虑影响因素较少，模型简单，主要适用于单个配送中心选址问题。对于复杂的选址问题，解析单个配送中心选址问题。对于复杂的选址问题，解析方法往往难以求解，通常需要借助其他更为综

12、合的分方法往往难以求解，通常需要借助其他更为综合的分析技术。析技术。26综合因素评价法 综合因素评价法是一种全面考虑各种影响综合因素评价法是一种全面考虑各种影响因素，并根据各影响因素重要性的不同因素，并根据各影响因素重要性的不同赋赋予权重予权重，对方案进行评价、打分，以找出，对方案进行评价、打分，以找出最优的选址方案。最优的选址方案。 综合因素评价法可以综合因素评价法可以综合考虑各方面因素综合考虑各方面因素，包括量化和非量化因素，包括量化和非量化因素，（非量化因素（非量化因素也可通过打分来量化），适用范围广。不也可通过打分来量化），适用范围广。不足之处在于打分和赋权过程中存在人为因足之处在于打

13、分和赋权过程中存在人为因素，同素，同时时的人往往得出不同的结果。的人往往得出不同的结果。27启发式规划选址 启发式方法是一种启发式方法是一种逐次逼近最优解逐次逼近最优解的方法，大部分的方法，大部分在在2020世纪世纪5050年代末期以年代末期以6060年代期间被开发出来。当年代期间被开发出来。当复杂的线性规划或者非线性规划难以用运筹学中的复杂的线性规划或者非线性规划难以用运筹学中的方法原理进行求解时，启发式方法发挥了巨大的作方法原理进行求解时，启发式方法发挥了巨大的作用。用。 启发式方法与最优规划方法的最大不同是启发式方法与最优规划方法的最大不同是它不是精它不是精确式算法，不能保证给出的解决方

14、案是最优的，确式算法，不能保证给出的解决方案是最优的，但但只要方法得当，能够使获得的可行解与最优解是非只要方法得当，能够使获得的可行解与最优解是非常接近的，而且启发式算法相对最优规划方法计算常接近的，而且启发式算法相对最优规划方法计算简单，求解速度快。因此启发式方法是规划技术中简单，求解速度快。因此启发式方法是规划技术中非常实用的方法。非常实用的方法。 28仿真法选址 仿真方法是试图通过模型重现某一系统的行为或活动，而不仿真方法是试图通过模型重现某一系统的行为或活动，而不必实地去建造并运转一个系统。必实地去建造并运转一个系统。 在选址问题中在选址问题中, ,仿真技术可以使分析者通过反复改变和组

15、合仿真技术可以使分析者通过反复改变和组合各种参数，多次试行来评价不同的选址方案；还可进行动态各种参数，多次试行来评价不同的选址方案；还可进行动态模拟，例如假定各个地区的需求是随机变动的，通过一定时模拟，例如假定各个地区的需求是随机变动的，通过一定时间长度的模拟运行间长度的模拟运行, ,可以估计各个地区的平均需求，从而在可以估计各个地区的平均需求，从而在此基础上确定配送中心的分布。此基础上确定配送中心的分布。 仿真方法可描述多方面的影响因素，因此具有较强的实用价仿真方法可描述多方面的影响因素，因此具有较强的实用价值，值，常用来求解较大型问题常用来求解较大型问题。仿真方法的不足主要在于。仿真方法的

16、不足主要在于仿真仿真方法不能提出初始方案方法不能提出初始方案, , 只能通过对各已存在的备选方案进只能通过对各已存在的备选方案进行评价，从中找出最优方案。所以在运用这项技术时必须首行评价，从中找出最优方案。所以在运用这项技术时必须首先借助其他技术找出各初始方案，而且预定初始方案的好坏先借助其他技术找出各初始方案，而且预定初始方案的好坏会对最终决策结果产生很大影响。会对最终决策结果产生很大影响。29最优化规划选址 最优化规划方法就是最优化规划方法就是用运筹学的理论方法用运筹学的理论方法，在许多可用的，在许多可用的选择中挑选出一个最优方案。最优化规划问题的关键是构选择中挑选出一个最优方案。最优化规

17、划问题的关键是构造目标函数和选择约束条件，即把选址影响因素（自变量造目标函数和选择约束条件，即把选址影响因素（自变量因子）的相关关系找出来。因子）的相关关系找出来。 最优化方法是最优化方法是一种离散模型一种离散模型，即对有限的备选点进行优化，即对有限的备选点进行优化组合。组合。 最优化规划方法中的线性规划及整数规划是目前应用最为最优化规划方法中的线性规划及整数规划是目前应用最为广泛的选址方法。最优化规划方法的优点是它属于精确式广泛的选址方法。最优化规划方法的优点是它属于精确式算法，能获得精确最优解。不足之处主要在于对一些复杂算法，能获得精确最优解。不足之处主要在于对一些复杂情况很难建立合适的规

18、划模型，或者模型太复杂，难以得情况很难建立合适的规划模型，或者模型太复杂，难以得到最优解。到最优解。 因素评分法的具体步骤如下：因素评分法的具体步骤如下： 1 1）决定一组相关的选址决策因素。）决定一组相关的选址决策因素。 2 2）对每一因素赋予一个权重以反映这个因素在）对每一因素赋予一个权重以反映这个因素在所有权重中的重要性。每一因素的分值根据权重所有权重中的重要性。每一因素的分值根据权重来确定，而权重则要根据成本的标准差来确定，来确定，而权重则要根据成本的标准差来确定，而不是根据成本值来确定。而不是根据成本值来确定。 3 3）对所有因素的打分设定一个共同的取值范围。）对所有因素的打分设定一

19、个共同的取值范围。 一、因素分析法一、因素分析法 4 4）对每一个备择地址，对所有因素按设定范围打分；）对每一个备择地址，对所有因素按设定范围打分； 5 5）用各个因素的得分与相应的权重相乘，并把所有）用各个因素的得分与相应的权重相乘，并把所有因素的加权值相加，得到每一个备择地址的最终得因素的加权值相加，得到每一个备择地址的最终得分；分； 6 6）选择具有最高总得分的地址作为最佳的选址。）选择具有最高总得分的地址作为最佳的选址。 n重心法是一种模拟方法重心法是一种模拟方法，它将物流，它将物流配送网络中的需求点和资源点看成配送网络中的需求点和资源点看成是分布在某一平面范围内，各处的是分布在某一平

20、面范围内，各处的需求量和资源量分别看成是聚积在需求量和资源量分别看成是聚积在一点的物体的重量。一点的物体的重量。 二、重心法二、重心法 二、重心法二、重心法 重心法的基本思想重心法的基本思想是所选配送中心地是所选配送中心地址到各个配送网点（或客户）的运输址到各个配送网点（或客户）的运输费用最小，并假设到各网点的配送费费用最小，并假设到各网点的配送费率是相同的。率是相同的。 重心法的假设条件为：重心法的假设条件为： （1 1）需求量集中于某一点上。）需求量集中于某一点上。 （2 2）不同地点物流节点的建设费用、运营费用）不同地点物流节点的建设费用、运营费用相同。相同。 （3 3）运输费用随运输距

21、离成正比增加。）运输费用随运输距离成正比增加。 （4 4）运输线路为空间直线。）运输线路为空间直线。 （5 5）运输费只与配送中心和客户的直线距离有）运输费只与配送中心和客户的直线距离有关，不考虑城市交通状况；关，不考虑城市交通状况； （6 6）不考虑配送中心所处地理位置的地产价格。）不考虑配送中心所处地理位置的地产价格。图图1 1 重心法示意图重心法示意图y(x1,y1)(x2,y2)(x0,y0)(xn,yn)xo假设有n个配送网点，需要建立一个配送中心。各配送网点（或客户）在平面坐标中的坐标是已知的，为(xi、yi)(i=1,2,3, n)，如下图所示。则该配送中心坐标位置（xo、yo)

22、可以用重心法公式求得：niiniiiniiniiiQQyyQQxx110110 x1Q1+ x2Q2 + + xnQn Q1+ Q2 + + Qn Y1Q1+ Y2Q2 + + YnQn Q1+ Q2 + + Qn 公式中，公式中，QiQi表示配送中心向第表示配送中心向第i i个配送网个配送网点的年配送物流量。点的年配送物流量。 例：例： 华联万家福超市要在某地建立一所地区级华联万家福超市要在某地建立一所地区级中央配送中心，要求该配送中心能够覆盖该地中央配送中心，要求该配送中心能够覆盖该地区五个连锁分店，分店的坐标及每月的销售量区五个连锁分店，分店的坐标及每月的销售量数据如表所示，要求求出一个

23、理论上的配送中数据如表所示，要求求出一个理论上的配送中心的位置。心的位置。算例一算例一 某公司拟在某城市建设一个配送中心，该配送中心某公司拟在某城市建设一个配送中心，该配送中心每年要从每年要从P P、Q Q、R R、S S 四个供应地运来不同商品。已知各地四个供应地运来不同商品。已知各地距城市中心的距离和年运量如表，假定各种材料运输费率相距城市中心的距离和年运量如表，假定各种材料运输费率相同，试用重心法确定该厂的合理位置。同，试用重心法确定该厂的合理位置。 厂址坐标及年运输量表厂址坐标及年运输量表供应地供应地PQRS供应地坐标供应地坐标 （50，60） （60，70） （19，25） （59，

24、45）年运输量年运输量/t2 2001 9001 700900km2 .46km900170019002200900591700191900602200500 xkm9 .51km900170019002200900451700251900702200600y 微分法微分法 在某计划区内，共有在某计划区内，共有n n个资源点和需求个资源点和需求点，各点的资源量或需求量为点，各点的资源量或需求量为Vi(i=1,2,Vi(i=1,2,n),n)，它们各自的坐标是（它们各自的坐标是（xi ,yixi ,yi) )（i=1, 2, i=1, 2, , , n n），需设置一个结点，设结点的坐标为（），

25、需设置一个结点，设结点的坐标为（X, X, Y Y），结点至资源点或需求点的运费率为），结点至资源点或需求点的运费率为RiRi。求在总运费最低情况下的结点位置。求在总运费最低情况下的结点位置。物流中心选址建模物流中心选址建模221)()(iiniiiyyxxRVTC总运费：niiiiiiniiiiiiyyxxyyRVyFyyxxxxRVxF1221220)()(/ )(0)()(/ )(一阶偏导数iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiidRVdRVyyxxRVyyxxyRVydRVdRVyyxxRVyyxxxxyx/)()(/)()(/)()(/)()(/RV22222

26、222求解：使总运输费用使总运输费用TC最小的网点位置，其坐标必须满足最小的网点位置，其坐标必须满足不考虑距离因素不考虑距离因素d，用重心公式估算初始选址，用重心公式估算初始选址点：点：iiiiiiiiiiRVRVyRVRVxyx00iiiiiiiiiiiiiidRVdRVydRVdRVxyx/迭代重心法求解步骤：目标值（迭代重心法求解步骤：目标值（x0，y0）（1）利用重心公式，求得初始解）利用重心公式，求得初始解（x00，y00）；）；（2）将初始解代入距离公式求得）将初始解代入距离公式求得di；代入总运费公式，计算总；代入总运费公式，计算总运费运费C0；（3）将）将di代入目标公式，求得

27、第一次迭代的解代入目标公式，求得第一次迭代的解（x01，y01）；（4）重复步骤（）重复步骤（2），求得），求得di新值；计算总运费新值；计算总运费C1 ，比较，比较C1与与C0的大小。若的大小。若C1C0 ，则继续迭代；若，则继续迭代；若C1C0 ，则结，则结束运算，束运算，（x01，y01）即为所求最优解；即为所求最优解；（5）重复步骤（）重复步骤（3）（）（2），直到），直到CnCn-1（n表示迭代次数）。表示迭代次数）。例题例题iX坐标XY坐标 Y资源量或需求量V至网点的运费率 RA13820000.05A28230000.05B32525000.075B46410000.075B58

28、815000.075# # 表示资源点表示资源点9 98 8 表示需求点表示需求点7 76 6 表示物流网点表示物流网点5 54 43 32 21 11 12 23 34 45 56 67 78 89 91010d1(3,8)d2(8,2)d3(2,5)d4(6,4)d5(8,8)# # 表示资源点表示资源点9 98 8 表示需求点表示需求点7 76 6 表示物流网点表示物流网点5 54 43 32 21 11 12 23 34 45 56 67 78 89 91010d1(3,8):100d2(8,2):150d3(2,5):187d4(6,4):75.5d5(8,8):112.5iX坐标X

29、Y坐标 Y资源量或需求量V至网点的运费率 RA13820000.05A28230000.05B32525000.075B46410000.075B58815000.075物流费率系数 V.RX轴重心V.R.XY轴重心V.R.Y100.0300.0800.0150.0 1200.0300.0187.5375.0937.575.0450.0300.0112.5900.0900.0625.0 3225.03237.5合计合计先用近似法求解初始坐标先用近似法求解初始坐标9 . 415 . 2329185 . 233228 . 715 . 23241105 . 211322,1414104141000i

30、iiiiiiiiiiiiiRVYRVyRVXRVxyx）求初始坐标（16. 5625322551510iiiiiiiRVXRVX18. 56255 .323751510iiiiiiiRVYRVY2147.1002. 45448. 1165. 3263. 4) 218. 5() 816. 5()()(552. 3) 818. 5() 316. 5()()(251043222202202222102101iiiidRVTCdddyyxxdyyxxd）求总费用（05659. 55.03769002. 45 .112448. 10 .75165. 3187263. 4150552. 3100002. 485 .112448. 160 .75165. 32187263. 48150552. 33100,35151105151110100iiiiiiiiiiiiiiiiiidRVdRVydRVdRVxyxyx）求改善地点坐标（标所以继续求改善地点坐因为）求改善后