中科院物流系统规划建模与实例 第8章配送线路规划.ppt

《中科院物流系统规划建模与实例 第8章配送线路规划.ppt》由会员分享，可在线阅读，更多相关《中科院物流系统规划建模与实例 第8章配送线路规划.ppt（91页珍藏版）》请在三一办公上搜索。

1、第4篇 运输决策和回收物流仿真,第8章 配送线路规划,交通运输的主要内容进行人和货物的载运和输送物流系统关心的两大问题运输方式选择运输线路优化,第8章 配送线路规划,8.1 运输模式的选择,8.1 运输模式的选择,8.1.2 库存与运输决策不同运输模式对库存的影响较慢的运输模式会引起较大的中转或运输库存较大运量单位的运输方式会出现订单批量超过当前需求量的情况，出现不需要的库存。较慢的运输模式会引起安全库存的提高。,例 1,某销售公司的商品需求成正态分布，且互相独立，每周的平均需求为1000件，方差为500件，每件成本为200美元，存储成本率为25%，每件重量为3lb，采用周期检查策略。运输方式

2、初步选择采用铁路或整车、零担，其中零担有2个批量1000或2000，如表8-1所示。请根据上述信息确定优化的运输方式。,表8-1 各运输方式的情况,解题步骤（1）首先计算运输费用（2）根据第6章的库存知识，计算周期检查策略下的各种库 存成本。（3）有以上结果计算累积运输成本以及总库存成本并得出 结论。,表8-2 运输费用,表8-3 库存费用,零担(1000)，平均周期库存500，安全库存707.1，,中转库存成本按照提前期的时间计算,表8-4 运输、库存费用,8.2 线路优化模型,点点间运输最短路径求解方法多点间运输运输算法单回路运输TSP模型及求解多回路运输VRP模型及求解,8.2.1 点点

3、间运输最短路径求解方法,最短路径问题假设有n个节点和m条弧的连通图G(Vn,Em)，并且图中的每条弧(i,j)都有一个长度cij（或者费用cij），则最短路径为：在连通图G(Vn,Em)中找到一条从节点1到节点n距离最短（或费用最低）的路径。,最短路径问题的4种基本原型从指定起始点到指定终点间的最短距离从指定起始点到其它所有点间的最短距离所有任意两点间的最短距离经过k个节点的最短距离,问题模型一般需要满足四个假设条件两点间的弧线距离为整数任何两点间都有直接相连的弧，如果没有则增加一个距离为的弧。所有的距离非负弧有方向解决最短路径问题的常用算法Dijkstra算法、逐次逼近算法、Floyd算法,

4、Dijkstra算法,适用对象求解任意指定两点之间的最短路径求解指定点到其余所有节点之间的最短路径算法思想依据,Dijkstra算法算法思想,Dijkstra算法,标号（Label）是指在Dijkstra算法中用来标记各个节点的属性的一套符号，根据不同的需要有：试探性的距离标号，永久标号和临时标号。两种不同的Dijkstra算法标号设定算法标号修正算法：适合有负路径的网络问题,标号设定Dijkstra算法基本步骤,（1）设置两个顶点集合S和T，S中存放已找到最短路径的顶点，即带有永久标号的顶点集合；T中存放当前还未找到最短路径的顶点，即未带有标号的顶点集合：（2）初始集合S中只包含起始顶点v0

5、，然后不断从集合T中选取到顶点v0路径长度最短的顶点vj加入集合S，即对集合S加上一个永久标号。新加入的顶点有两种可能的途径到达v0，一是直接与v0相连，,另一则是与集合S中已知最短路径的顶点相连，构成一个新的最短路径。lk(vj)表示第k步求得的最短路,有:vi指的是集合S中的顶点，而vj则是一个试探性节点，是集合T中的任意元素；（3）重复2，直到目标点vn被加入到集合S中。,例 2,现有如图8-2所示的连通图，试求解从顶点v1到顶点v6之间的最短路径和最短路径的长度。,图8-2 例2的连通图,8.2 线路优化模型,8.2.2 多点间运输运输算法多点间运输问题是指有起始点或目的点不唯一的运输

6、调配问题产销平衡运输问题它是多点间运输问题中最为常见的问题，设计的总供应能力和总需求是一样的，但是由不同的路径进行配送时，会导致最终的总运输成本不一样，此类问题的目标就是寻找最低的总运输成本。,供应点A=a1,a2,an,需求点 B=b1,b2,bn。cij代表和ai之bj间的距离或者费用等权重。xij代表和ai向bj的运送量。,模型,8.2.2 多点间运输运输算法,多点间的运输调配问题的求解方法（1）单纯形法：比较精确，但计算量大，常借助计算机求解。（2）表上作业法（也称运输算法）：对比较简单的问题求解直观方便，可手工完成。,例 3,有一3个起始点和4个目的点的运输问题，3个起始点的供应量分

7、别是50、50、75，4个目的点的需求量分别为40，55，60，20.它们之间的距离可以分别为：,假设每次装车的额外费用不计，运输成本与所行驶的距离成正比。用运输算法求解最优的运输方案。,例 3 求解步骤,这是一个十分典型的多点间运输的问题，应用运输算法求解步骤如下：（1）建立运输表（2）确定初始条件解：西北角法、最小值法（3）对初始条件解进行优化，得到最优解：闭回路法,8.2.3 单回路运输TSP模型及求解,8.2.3 单回路运输TSP模型及求解,单回路运输问题是指在路线优化中，设存在节点集合D，选择一条合适的路径遍历所有的节点并且要求闭合。特点单一性（只有一个回路）遍历性（不可遗漏）,TS

8、P模型,TSP模型是单回路运输问题的最为典型的一个模型，它的全称是Traveling Salesman Problem(TSP)，中文叫做旅行商问题，它是一个典型的NP-Hard问题。模型描述在给出的一个n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。求解方法枚举法；分支定界法；启发式算法,最近邻点法,简介由Rosenkrantz和Stearns等人在1977年提出的一种用于解决TSP问题的算法，该算法计算快捷，但精度低，可作为进一步优化的初始解。算法步骤（1）从零点开始，作为整个回路的起点。（2）找到离刚刚加入到回路的上一顶点最近的一个顶点并 将其加入到回路中。（

9、3）重复步骤（2），直到A中的所有顶点都加入到回路中。（4）最后，将最后一个加入的顶点和起点连接起来。,例 4,现有一个连通图，|A|=6，它们的距离矩阵如表8-22所示，它们的相对位置如图8-5所示，假设 i，j 两点之间的距离是对称的。,2,3,1,5,4,6,图8-5 位置图,最近插入法,由Rosenkrantz和Stearns等人在1977年提出算法步骤(1)找到c1k最小的节点vk，形成一个子回路，T=v1,vk,v1。(2)在剩下的节点中，寻找一个离子回路中某一节点最近的节点vk。(3)在子回路中找到一条弧(i,j)，使得cik+ckj-cij最小，然后将节点vk插入到节点vi,v

10、j之间，用两条新的弧(i,k)、(k,j)代替原来的弧(i,j)，并将节点vk加入到子回路中。(4)重复步骤(2)、(3)，直到所有的节点都加入子回路中。,8.2.4 多回路运输VRP模型及求解,8.2.4 多回路运输VRP模型及求解,最早由Dantzig和Ramser在1950年首次提出。该问题的研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的优化目标（如里程最短、费用最少、时间尽量少、车队规模尽量小、车辆利用率高等）。与前面问题的区别,VRP模型,运用VRP模型

11、需要考虑的问题（1）仓库（2）车辆（3）时窗（4）顾客（5）道路信息（6）货物信息（7）运输规章VRP模型描述,VRP模型,（3）限制条件：1）Nm 2）每一个定单都要完成。3）每辆车完成任务之后都要回到v0。4）车辆的容量限制不能超过。5）特殊问题还需要考虑时窗的限制。6）运输规章的限制。,VRP问题的分类,VRP常用的基本问题旅行商问题（TSP、MTSP&VRP）分配问题运输问题背包问题最短路径问题最小费用流问题中国邮递员问题,节约算法,Clarke和Wright在1964年提出，是目前用来解决VRP模型最有名的启发式算法。算法思想将运输问题中存在的两个回路（0，i，0）和（0，j，0）合

12、并成为一个回路（0，i，j，0）。在上面的合并操作中，整个运输问题的总运输距离将会发生变化，如果变化后总运输距离下降，则称节约了运输距离。相应的变化值，叫做节约距离,节约算法,节约算法的图形描述两种基本实现途径（1）并行方式（2）串行方式,调整前,调整后,并行方式,第一步，形成初始解:k条路线第二步，计算节约度对所有节点对计算节约度，并排序Cij=ci0+c0j-cij,i,j=1,2,n;ij第三步，进行回路合并 按照节约度的排序，合并以(i,0)结束以(0,j)结尾的回路例子,串行方式,第一步，形成初始解第二步，计算节约度第三步，进行回路合并 将合并为 或,扫描算法,扫描算法（Sweep

13、Algorithm）是Gillett和 Miller在1974年首先提出的，它也是用于求解车辆数目不限制的CVRP问题。,扫描算法算法步骤,（1）以起始点v0作为极坐标系的原点，并以连通图中的任意一顾客点和原点的连线定义为角度零，建立极坐系。然后对所有的顾客所在的位置，进行坐标系的变换，全部都转换为极坐标系。（2）分组。从最小角度的顾客开始，建立一个组，按逆时针方向，将顾客逐个加入到组中，直到顾客的需求总量超出了负载限制。然后建立一个新的组，继续按逆时针方向，将顾客继续加入到组中。（3）重复（2）的过程，直到所有顾客都被分类为止。（4）路径优化。对各个分组内的顾客点，就是一个个单独的TSP模型

14、的线路优化问题，可以用前面介绍的TSP模型的方法对结果进行优化，选择一个合理的路线。,例 5,现有一个仓库v0，需要对9个客户提供货物，它们的需求量及极坐标的角坐标值见表8-24，它们的位置关系如图8-14所示。每辆车的运力是9,表8-24 需求表和极坐标的角坐标值,例 5 求解过程,解题步骤（1）建立极坐标系（2）分组过程（3）组内的线路优化,3,TS算法,TS算法（Tabu Search Algorithm）是一种用来求解组合优化问题的迭代启发式算法，最早由Fred Glover详细介绍的。该算法的初始想法是在Hansen的最速上升缓和下降启发式算法（Steepest Ascent Mil

15、dest Descent Algorithm）中出现的。特点（1）TS算法是一种广义的局部搜索。（2）TS算法是一种亚启发式算法。,TS算法每次循环从当前解转移到它的邻域中的最好点，即使这个点所对应的值不优于当前解的。避免循环的出现（tabu）,TS算法,需要注意的概念（1）尝试解（Trial Solution）（2）Tabu限制（Tabu Restriction）（3）激活准则（Aspiration Criterion)（4）候选列表（Candidate List）（5）可行邻域解（Admissible Neighborhood Solution）（6）移动属性（Attribute of A

16、 Move）（7）新旧存储器（Recency Based Memory）（8）Tabu期限（Tabu Tenure）（9）移动评价（Move Evaluator）（10）移动收益（Move Value）,Tabu搜索算法的流程图,禁忌搜索的一个例子,四城市非对称TSP问题，A为起始和终止城市,第一步,解的形式 禁忌对象及长度 候选集f(x0)=4,第二步,解的形式 禁忌对象及长度 候选集f(x1)=4.5,第三步,解的形式 禁忌对象及长度 候选集f(x2)=3.5,第四步,解的形式 禁忌对象及长度 候选集f(x3)=7.5,怎么往下走?,禁忌长度改为2对应的第四步,解的形式 禁忌对象及长度 候

17、选集f(x3)=7.5,禁忌长度改为2对应的第五步,解的形式 禁忌对象及长度 候选集f(x4)=4.5,禁忌长度改为2对应的第六步,解的形式 禁忌对象及长度 候选集f(x5)=8,何时结束?,TS算法注意的问题,禁忌的长度终止的规则,8.3 实例分析,8.3.1 某销售公司的配送线路设计8.3.2 家庭电器的月配送计划,8.3.1 某销售公司的配送线路设计,1、公司背景 某销售公司的配送中心负责对全市85km2范围内的5716个零售户进行配送服务。根据零售户的销售能力、库存和资金运转情况，公司的配送策略是每周对每个零售户配送两次，每辆车的固定配送区域为3个，每天一个区域，每周分周一四，二五，三

18、六对所辖的3个服务区域进行服务。每次配送的前一天，通过访销人员获得每个零售户的需求量。目前的配送方案是，将全市零售户划分成66个车辆配送区域，用22辆配送车辆对其服务。配送车辆的最大容积为1500件单位商品，每天的最长工作时间为8h。公司希望在配送策略不变的情况下，对配送方案进行优化，以降低成本提高效益。,8.3.1 某销售公司的配送线路设计,2、配送业务流程分析物流、信息流分离,3、数学建模,（1）模型数据整理将全市5000余家客户分成41*29个方格；476个网格内有客户。按40km/h,2040km/h,小于20km/h对道路分级,3、数学建模,（2）模型约束分析访销员上午1h例会，下午

19、1h汇总报表，最多工作360min，每个客户至少5min每辆车在每个客户停留23min，车容量有限制。每天最多工作300min。,3、数学建模,（3）方案建模目标：最小化访销路线里程和配送里程条件假设配送的货物类似各个客户的需求和位置已知配送方有足够的运力约束条件车辆的容量限制访销员和配送员工作时间限制,4、优化分析与讨论,（1）访销路线得到新访销路线74条，每人3条，共需25人平均每天工作时间288.52min节约成本58500元（降54.5%）（2）配送方案得到配送路线27条，共需9辆车，每车容量1500单位平均配送时间308.33min,平均容量2525.58节约成本36938.047元

20、（降25.6%）,8.3.2 家庭电器的月配送计划,背景介绍在这个案例里，将介绍一个为Arcelik设计的大规模月配送计划项目。Arcelik是土耳其最大的一家家用电器生产商，在1992年的销售总量是11亿美元。Arcelik有7个工厂，8个配送中心（仓库）和大约1500个销售代理。产品在仓库进行包装并运送到代理商手中。主要使用卡车进行运输，某些工厂和仓库之间使用铁路进行运输。ATILIM集团负责所有Arcelik产品在土耳其范围内的配送。它包含5个子公司，全国被划分为5个区域（地理上相连接），每个子公司负责1个区域内所有市场范围的供应。一个市场范围是某地区（通常是一个城市及其周边）内若干个销

21、售代理的集合。,工厂,仓库2,仓库3,仓库1,仓库5,仓库4,顾客,顾客,顾客,顾客,顾客,8.3.2.1.1 问题建模,用到的数据（1）每个工厂每月的生产计划（2）每个市场每月的需求分配（3）每个仓库的容量（4）从工厂到仓库和从仓库到市场的单位产品单位运输成本。,定义参数Cij=产品i从其工厂到仓库j的单位运输成本Dijk=产品i从仓库j到市场k的单位运输成本Bi=每月产品i的产量Uj=仓库j的容量Aik=产品i对市场k的需求分配Ri=产品i的体积系数Xij=产品i运到仓库j的数量Yijk=产品i从仓库j到市场k的数量,建立数学模型,讨论,模型规模：假设30个产品，10个仓库，100个需求点

22、。用拉格朗日方法来简化模型,8.3.2.1.2 更精确的模型,重的货物只能放在卡车底部，轻的货物可放在卡车底部或上部放在卡车底部的货物要考虑体积系数，放在卡车上部的货物要考虑面积系数。每车的体积系数不能超过48，面积系数不能超过24，这两个系数独立考虑。,定义参数cij=产品i从其工厂到仓库j的单位运费dj=仓库j到市场的整车运费ei=产品i的体积因子fi=产品i的面积因子ai=市场对产品i的需求H=重的产品集和L=轻的产品集和,变量xij=重产品i运到仓库j的数量zij=轻产品i装在卡车下部运到仓库jwij=轻产品i装在卡车上部运到仓库jyj=从仓库j到市场的卡车数量,模型改进,问题：超过两

23、个仓库给一个市场供货会使系统复杂化每个仓库只给一个市场供货每月至少需要10车次，否则要么订单延迟，要么空载对策手工调整增加限制条件，限制每个市场最多有2个仓库服务,8.3.2.2 优化结果,出现一些奇怪的分配:深底锅在Layjrova生产，但是有些（Layjrova 附近）城市的深底锅从Layjrova外的仓库运过来伊斯坦布尔附近的新仓库使用率比较低,8.3.2.2 优化结果,调整后的方案是合理的调整后的方案和调整前的费用相差不到1所有在Layjrova生产的产品直接运到该市场区域，不经过间接的仓库Eskisehir仓库只存储31种产品中的10种。卡车的装载将有富余（如顶部空间）运往大部分市场

24、的轻便货物在车顶部分配到Layjrova和Eskisehir仓库的轻便货物是成比例的没有零散货物有4个市场的产品来自一个仓库其它11个市场由2个仓库提供，31种产品中有30种只存储在一个仓库中。,所有运往布尔沙和antalya的货物如果只存在cayirova的仓库，成本增加14%15%;如果只存在Eskisehir的仓库，成本增加23%26%。有4个区域没有精确数据，采用距离代表运输成本，人口数代替需求。可能求解出的最佳方案是每个区域有3、4个仓库服务，但是改为不多于两个后，成本平均增加2.6%,有两个仓库（8号、10号）在最佳方案中不起作用。增加这两个仓库到系统中成本增加1020，成本提高管

25、理者解释为为了增加放影速度、市场覆盖率。使用开发的系统后ATILM公司的成本降了，但把因增加仓库还是改善分配计划引起的比较困难。,8.3.2.3 讨论及评价,ATILM公司使用项目中建立的线性规划模型代替电子表格线性规划模型的优点对装载能力的约束最优化能力柔性（可加入新的约束）可扩展性（可加入新的产品和仓库）数据错误检测（不正确的数量和成本数据会导致不合理的方案）,线性规划模型的缺点精确性模型假设环境是静态的（所有的需求合约供给在每月的第一天都能得到），实际上需求和供给数据是一个月连续不断的进入系统。需求是批量化的（如订单），这些订单不能被分离基于此，预计成本数据只能看作一个目标，在实际运作中会有些偏差,作 业,t4,