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

第4篇 运输决策和回收物流仿真,第8章 配送线路规划,交通运输的主要内容 进行人和货物的载运和输送 物流系统关心的两大问题 运输方式选择 运输线路优化,第8章 配送线路规划,8.1 运输模式的选择,8.1 运输模式的选择,8.1.2 库存与运输决策 不同运输模式对库存的影响 较慢的运输模式会引起较大的中转或运输库存 较大运量单位的运输方式会出现订单批量超过当前需求量的情况，出现不需要的库存。 较慢的运输模式会引起安全库存的提高。,例 1,某销售公司的商品需求成正态分布，且互相独立，每周的平均需求为1000件，方差为500件，每件成本为200美元，存储成本率为25%，每件重量为3lb，采用周期检查策略。运输方式初步选择采用铁路或整车、零担，其中零担有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 点点间运输最短路径求解方法,最短路径问题 假设有n个节点和m条弧的连通图g(vn, em)，并且图中的每条弧(i, j)都有一个长度cij（或者费用cij），则最短路径为：在连通图g(vn, em)中找到一条从节点1到节点n距离最短（或费用最低）的路径。,最短路径问题的4种基本原型 从指定起始点到指定终点间的最短距离 从指定起始点到其它所有点间的最短距离 所有任意两点间的最短距离 经过k个节点的最短距离,问题模型一般需要满足四个假设条件 两点间的弧线距离为整数 任何两点间都有直接相连的弧，如果没有则增加一个距离为的弧。 所有的距离非负 弧有方向 解决最短路径问题的常用算法 dijkstra算法、逐次逼近算法、floyd算法,dijkstra算法,适用对象 求解任意指定两点之间的最短路径 求解指定点到其余所有节点之间的最短路径 算法思想依据,dijkstra算法算法思想,dijkstra算法,标号（label） 是指在dijkstra算法中用来标记各个节点的属性的一套符号，根据不同的需要有：试探性的距离标号，永久标号和临时标号。 两种不同的dijkstra算法 标号设定算法 标号修正算法：适合有负路径的网络问题,标号设定dijkstra算法基本步骤,（1）设置两个顶点集合s和t，s中存放已找到最短路径的顶点，即带有永久标号的顶点集合；t中存放当前还未找到最短路径的顶点，即未带有标号的顶点集合： （2）初始集合s中只包含起始顶点v0，然后不断从集合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 多点间运输运输算法 多点间运输问题 是指有起始点或目的点不唯一的运输调配问题 产销平衡运输问题 它是多点间运输问题中最为常见的问题，设计的总供应能力和总需求是一样的，但是由不同的路径进行配送时，会导致最终的总运输成本不一样，此类问题的目标就是寻找最低的总运输成本。,供应点a=a1, a2, an,需求点 b=b1, b2, bn。cij代表和ai之bj间的距离或者费用等权重。 xij代表和ai向bj的运送量。,模型,8.2.2 多点间运输运输算法,多点间的运输调配问题的求解方法 （1）单纯形法：比较精确，但计算量大，常借助计算机求解。 （2）表上作业法（也称运输算法）：对比较简单的问题求解直观方便，可手工完成。,例 3,有一3个起始点和4个目的点的运输问题，3个起始点的供应量分别是50、50、75，4个目的点的需求量分别为40，55，60，20.它们之间的距离可以分别为：,假设每次装车的额外费用不计，运输成本与所行驶的距离成正比。用运输算法求解最优的运输方案。,例 3 求解步骤,这是一个十分典型的多点间运输的问题，应用运输算法求解步骤如下： （1）建立运输表 （2）确定初始条件解：西北角法、最小值法 （3）对初始条件解进行优化，得到最优解：闭回路法,8.2.3 单回路运输tsp模型及求解,8.2.3 单回路运输tsp模型及求解,单回路运输问题 是指在路线优化中，设存在节点集合d，选择一条合适的路径遍历所有的节点并且要求闭合。 特点 单一性（只有一个回路） 遍历性（不可遗漏）,tsp模型,tsp模型是单回路运输问题的最为典型的一个模型，它的全称是traveling salesman problem (tsp)，中文叫做旅行商问题，它是一个典型的np-hard问题。 模型描述 在给出的一个n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。 求解方法 枚举法；分支定界法；启发式算法,最近邻点法,简介 由rosenkrantz和stearns等人在1977年提出的一种用于解决tsp问题的算法，该算法计算快捷，但精度低，可作为进一步优化的初始解。 算法步骤 （1）从零点开始，作为整个回路的起点。 （2）找到离刚刚加入到回路的上一顶点最近的一个顶点并 将其加入到回路中。 （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 , vj之间，用两条新的弧(i, k)、(k, j)代替原来的弧(i, j)，并将节点vk加入到子回路中。 (4) 重复步骤(2)、(3)，直到所有的节点都加入子回路中。,8.2.4 多回路运输vrp模型及求解,8.2.4 多回路运输vrp模型及求解,最早由dantzig和ramser在1950年首次提出。该问题的研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的优化目标（如里程最短、费用最少、时间尽量少、车队规模尽量小、车辆利用率高等）。 与前面问题的区别,vrp模型,运用vrp模型需要考虑的问题 （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）合并成为一个回路（0， ，i，j， ，0）。在上面的合并操作中，整个运输问题的总运输距离将会发生变化，如果变化后总运输距离下降，则称节约了运输距离。相应的变化值，叫做节约距离,节约算法,节约算法的图形描述 两种基本实现途径 （1）并行方式 （2）串行方式,调整前,调整后,并行方式,第一步，形成初始解:k条路线 第二步，计算节约度 对所有节点对计算节约度，并排序 cij=ci0+c0j-cij, i,j=1,2, ,n; ij 第三步，进行回路合并 按照节约度的排序，合并以(i,0)结束以(0,j)结尾的回路 例子,串行方式,第一步，形成初始解 第二步，计算节约度 第三步，进行回路合并 将 合并为 或,扫描算法,扫描算法（sweep algorithm）是gillett和 miller在1974年首先提出的，它也是用于求解车辆数目不限制的cvrp问题。,扫描算法算法步骤,（1）以起始点v0作为极坐标系的原点，并以连通图中的任意一顾客点和原点的连线定义为角度零，建立极坐系。然后对所有的顾客所在的位置，进行坐标系的变换，全部都转换为极坐标系。 （2）分组。从最小角度的顾客开始，建立一个组，按逆时针方向，将顾客逐个加入到组中，直到顾客的需求总量超出了负载限制。然后建立一个新的组，继续按逆时针方向，将顾客继续加入到组中。 （3）重复（2）的过程，直到所有顾客都被分类为止。 （4）路径优化。对各个分组内的顾客点，就是一个个单独的tsp模型的线路优化问题，可以用前面介绍的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 mildest 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 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对应的第四步,解的形式 禁忌对象及长度 候选集 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个，每天一个区域，每周分周一四，二五，三六对所辖的3个服务区域进行服务。每次配送的前一天，通过访销人员获得每个零售户的需求量。 目前的配送方案是，将全市零售户划分成66个车辆配送区域，用22辆配送车辆对其服务。配送车辆的最大容积为1500件单位商品，每天的最长工作时间为8h。公司希望在配送策略不变的情况下，对配送方案进行优化，以降低成本提高效益。,8.3.1 某销售公司的配送线路设计,2、配送业务流程分析物流、信息流分离,3、数学建模,（1）模型数据整理 将全市5000余家客户分成41*29个方格；476个网格内有客户。 按40km/h,2040km/h,小于20km/h对道路分级,3、数学建模,（2）模型约束分析 访销员上午1h例会，下午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元（降25.6%）,8.3.2 家庭电器的月配送计划,背景介绍 在这个案例里，将介绍一个为arcelik设计的大规模月配送计划项目。 arcelik是土耳其最大的一家家用电器生产商，在1992年的销售总量是11亿美元。 arcelik有7个工厂，8个配送中心（仓库）和大约1500个销售代理。产品在仓库进行包装并运送到代理商手中。主要使用卡车进行运输，某些工厂和仓库之间使用铁路进行运输。 atilim集团负责所有arcelik产品在土耳其范围内的配送。它包含5个子公司，全国被划分为5个区域（地理上相连接），每个子公司负责1个区域内所有市场范围的供应。一个市场范围是某地区（通常是一个城市及其周边）内若干个销售代理的集合。,工厂,仓库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个需求点。 用拉格朗日方法来简化模型,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装在卡车下部运到仓库j wij =轻产品i装在卡车上部运到仓库j yj=从仓库j到市场的卡车数量,模型改进,问题： 超过两个仓库给一个市场供货会使系统复杂化 每个仓库只给一个市场供货每月至少需要10车次，否则要么订单延迟，要么空载 对策 手工调整 增加限制条件，限制每个市场最多有2个仓库服务,8.3.2.2 优化结果,出现一些奇怪的分配:深底锅在layjrova生产，但是有些（ layjrova 附近）城市的深底锅从layjrova外的仓库运过来 伊