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

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）有以上结果计算累积运输成本以及总库存成本并得出 结论。 年需求/件 批量/件 年运次 提前 期 运费 整车发运5200065008245000 零担(2000) 520002000261122200 零担(1000) 520001000521127400 铁路5200013000449560 表8-2 运输费用 安

3、全库 存成本 周期库 存成本 中转库存 成本 总库存成本 整车发运43301162500100000305801 零担(2000)353555000050000135355 零担(1000)353552500050000110355 铁路55902325000200000580902 表8-3 库存费用 零担(1000)，平均周期库存500，安全库存707.1， 中转库存成本按照提前期的时间计算 总库存成本 运输成 本 总成本 整车发运305801 45000350801 零担(2000)135355 122200257555 零担(1000)110355 127400237755 铁路580

4、902 9560590462 表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个节点

5、的最短距离 问题模型一般需要满足四个假设条件 两点间的弧线距离为整数 任何两点间都有直接相连的弧，如果没有则增 加一个距离为的弧。 所有的距离非负 弧有方向 解决最短路径问题的常用算法 dijkstra算法、逐次逼近算法、floyd算法 dijkstra算法 适用对象 求解任意指定两点之间的最短路径 求解指定点到其余所有节点之间的最短路径 算法思想依据 dijkstra算法算法思想 dijkstra算法 标号（label） 是指在dijkstra算法中用来标记各个节点的属性 的一套符号，根据不同的需要有：试探性的距 离标号，永久标号和临时标号。 两种不同的dijkstra算法 标号设定算法 标

6、号修正算法：适合有负路径的网络问题 标号设定dijkstra算法基本步骤 （1）设置两个顶点集合s和t，s中存放已找 到最短路径的顶点，即带有永久标号的顶 点集合；t中存放当前还未找到最短路径的 顶点，即未带有标号的顶点集合： （2）初始集合s中只包含起始顶点v0，然后不 断从集合t中选取到顶点v0路径长度最短的 顶点vj加入集合s，即对集合s加上一个永久 标号。新加入的顶点有两种可能的途径到 达v0，一是直接与v0相连， vstst， 另一则是与集合s中已知最短路径的顶点相 连，构成一个新的最短路径。 lk(vj)表示第k步求得的最短路,有: vi指的是集合s中的顶点，而vj则是一个试探 性

7、节点，是集合t中的任意元素； （3）重复2，直到目标点vn被加入到集合s中。 11 ()min(),( ) kjkjkiij l vlvlvc ij iji j ci j 从顶点 到顶点 之间的弧线距离；假如、之间存在弧； 0；假如=； ；其他情形 例 2 现有如图8-2所示的连通图，试求解从顶点v1到顶 点v6之间的最短路径和最短路径的长度。 1 2 3 5 4 6 4 11 2 8 4 1 7 3 2 图8-2 例2的连通图 8.2 线路优化模型 8.2.2 多点间运输运输算法 多点间运输问题 是指有起始点或目的点不唯一的运输调配问题 产销平衡运输问题 它是多点间运输问题中最为常见的问题，

8、设计 的总供应能力和总需求是一样的，但是由不同 的路径进行配送时，会导致最终的总运输成本 不一样，此类问题的目标就是寻找最低的总运 输成本。 供应点a=a1, a2, an,需求点 b=b1, b2, bn。cij代表和ai之bj间的距离或者费用等权 重。 xij代表和ai向bj的运送量。 a1 a2 a3 b1 b2 c12 模型 11 1 1 min ,1,2,., ,1,2,., 0, 1,2,., 1,2,., mn ijij ij n iji j m ijj i ij c x xaim xbjn ximjn 满足 8.2.2 多点间运输运输算法 多点间的运输调配问题的求解方法 （1）

9、单纯形法：比较精确，但计算量大，常借 助计算机求解。 （2）表上作业法（也称运输算法）：对比较简 单的问题求解直观方便，可手工完成。 例 3 有一3个起始点和4个目的点的运输问题，3个起始 点的供应量分别是50、50、75，4个目的点的需 求量分别为40，55，60，20.它们之间的距离可 以分别为： 111213142122 232431323334 3,1,4,5,7,3, 8,6,2,3,9,2 cccccc cccccc 。 假设每次装车的额外费用不计，运输成本与所行 驶的距离成正比。用运输算法求解最优的运输方 案。 例 3 求解步骤 这是一个十分典型的多点间运输的问题，应用 运输算法

10、求解步骤如下： （1）建立运输表 （2）确定初始条件解：西北角法、最小值法 （3）对初始条件解进行优化，得到最优解：闭 回路法 8.2.3 单回路运输tsp模型及求解 8.2.3 单回路运输tsp模型及求解 单回路运输问题 是指在路线优化中，设存在节点集合d，选择一 条合适的路径遍历所有的节点并且要求闭合。 特点 单一性（只有一个回路） 遍历性（不可遗漏） tsp模型 tsp模型是单回路运输问题的最为典型的一 个模型，它的全称是traveling salesman problem (tsp)，中文叫做旅行商问题，它 是一个典型的np-hard问题。 模型描述 在给出的一个n顶点网络（有向或无向

11、），要 求找出一个包含所有n个顶点的具有最小耗费 的环路。 求解方法 枚举法；分支定界法；启发式算法 最近邻点法 简介 由rosenkrantz和stearns等人在1977年提出的 一种用于解决tsp问题的算法，该算法计算快捷， 但精度低，可作为进一步优化的初始解。 算法步骤 （1）从零点开始，作为整个回路的起点。 （2）找到离刚刚加入到回路的上一顶点最近的一个顶点并 将其加入到回路中。 （3）重复步骤（2），直到a中的所有顶点都加入到回路中。 （4）最后，将最后一个加入的顶点和起点连接起来。 例 4 现有一个连通图，|a|=6，它们的距离矩阵如表8-22所示，它们的相 对位置如图8-5所示

12、，假设 i，j 两点之间的距离是对称的。 2 3 15 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)，直到所有的节点都加入子回

13、路中。 8.2.4 多回路运输vrp模型 及求解 8.2.4 多回路运输vrp模型 及求解 最早由dantzig和ramser在1950年首次提出。该问 题的研究目标是：对一系列顾客需求点设计适当 的路线，使车辆有序地通过它们，在满足一定的 约束条件（如货物需求量、发送量、交发货时间、 车辆容量限制、行驶里程限制、时间限制等）下， 达到一定的优化目标（如里程最短、费用最少、 时间尽量少、车队规模尽量小、车辆利用率高 等）。 与前面问题的区别 vrp模型 运用vrp模型需要考虑的问题 （1）仓库 （2）车辆 （3）时窗（4）顾客 （5）道路信息 （6）货物信息 （7）运输规章 vrp模型描述 v

14、rp模型 （3）限制条件： 1）nm 2）每一个定单都要完成。 3）每辆车完成任务之后都要回到v0。 4）车辆的容量限制不能超过。 5）特殊问题还需要考虑时窗的限制。 6）运输规章的限制。 vrp问题的分类 vrp常用的基本问题 旅行商问题（tsp、mtsp ij 第三步，进行回路合并 按照节约度的排序，合并以(i,0)结束以(0,j) 结尾的回路 例子 串行方式 第一步，形成初始解 第二步，计算节约度 第三步，进行回路合并 将 合并为 或 扫描算法 扫描算法（sweep algorithm）是gillett和 miller在1974年首先提出的，它也是用于求 解车辆数目不限制的cvrp问题。

15、 扫描算法算法步骤 （1）以起始点v0作为极坐标系的原点，并以连通图中的 任意一顾客点和原点的连线定义为角度零，建立极坐系。 然后对所有的顾客所在的位置，进行坐标系的变换，全 部都转换为极坐标系。 （2）分组。从最小角度的顾客开始，建立一个组，按逆 时针方向，将顾客逐个加入到组中，直到顾客的需求总 量超出了负载限制。然后建立一个新的组，继续按逆时 针方向，将顾客继续加入到组中。 （3）重复（2）的过程，直到所有顾客都被分类为止。 （4）路径优化。对各个分组内的顾客点，就是一个个单 独的tsp模型的线路优化问题，可以用前面介绍的tsp 模型的方法对结果进行优化，选择一个合理的路线。 例 5 现有

16、一个仓库v0，需要对9个客户提供货物，它们 的需求量及极坐标的角坐标值见表8-24，它们的 位置关系如图8-14所示。每辆车的运力是9 表8-24 需求表和极坐标的角坐标值 顾客/人123456789 需求/单位货物536534216 角坐标/( 。)8030135280255210170350335 例 5 求解过程 解题步骤 （1）建立极坐标系 （2）分组过程 （3）组内的线路优化 3 v0 9 2 8 4 5 6 7 3 1 图8-14 顾客和仓库的位置图 9 2 8 4 5 6 7 1 图8-15 扫描算法求解过程 ts算法 ts算法（tabu search algorithm）是一种

17、用 来求解组合优化问题的迭代启发式算法， 最早由fred glover详细介绍的。该算法的初 始想法是在hansen的最速上升缓和下降启 发式算法（steepest ascent mildest descent algorithm）中出现的。 特点 （1）ts算法是一种广义的局部搜索。 （2）ts算法是一种亚启发式算法。 ts算法 每次循环从当前解转移到它的邻域中的最好点， 即使这个点所对应的值不优于当前解的。 避免循环的出现（tabu） ts算法 需要注意的概念 （1）尝试解（trial solution） （2）tabu限制（tabu restriction） （3）激活准则（aspira

18、tion 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搜索算法的流程图 最优解 当前解 尝试解 1 尝试解 2 “最优” 移动1 移动2 tabu？ 当前解 n y 激活准则 y 重新移动 当前解 n 禁忌搜索的一个例子 四

19、城市非对称tsp问题，a为起始和终止城市 0 1 0.5 1 1 0 1 1 () 1.5 5 0 1 1 1 1 0 ij dd 第一步 解的形式 禁忌对象及长度 候选集 f(x0)=4 a b c d bcd a b c 对换评价值 c,d4.5 b,c7.5 b,d8 第二步 解的形式 禁忌对象及长度 候选集 f(x1)=4.5 a b d c bcd a b c3 对换评价值 b,c3.5 b,d4.5 c,d4.5t 第三步 解的形式 禁忌对象及长度 候选集 f(x2)=3.5 a c d b bcd a b3 c2 对换评价值 b,c4.5t b,d7.5 c,d8t 第四步 解的

20、形式 禁忌对象及长度 候选集 f(x3)=7.5 a c b d bcd a b23 c1 对换评价值 b,d3.5t b,c4.5t c,d4.5t 怎么往下走? 禁忌长度改为2对应的第四步 解的形式 禁忌对象及长度 候选集 f(x3)=7.5 a c b d bcd a b12 c0 对换评价值 b,d3.5t b,c4.5t c,d4.5 禁忌长度改为2对应的第五步 解的形式 禁忌对象及长度 候选集 f(x4)=4.5 a d b c bcd a b01 c2 对换评价值 b,d4.5t c,d7.5t b,c8 禁忌长度改为2对应的第六步 解的形式 禁忌对象及长度 候选集 f(x5)=

21、8 a d c b bcd a b20 c1 对换评价值 b,d4 c,d3.5t b,c4.5t 何时结束? ts算法注意的问题 禁忌的长度 终止的规则 8.3 实例分析 8.3.1 某销售公司的配送线路设计 8.3.2 家庭电器的月配送计划 8.3.1 某销售公司的配送线路设计 1、公司背景 某销售公司的配送中心负责对全市85km2范围内的5716 个零售户进行配送服务。根据零售户的销售能力、库存和 资金运转情况，公司的配送策略是每周对每个零售户配送 两次，每辆车的固定配送区域为3个，每天一个区域，每 周分周一四，二五，三六对所辖的3个服务区域进行服务。 每次配送的前一天，通过访销人员获得

22、每个零售户的需求 量。 目前的配送方案是，将全市零售户划分成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，每个客户

23、至少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

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

25、周边）内若 干个销售代理的集合。 工厂 仓库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的数量 建立数学模型

26、min (8-1) (8-2) , (8-3) ijijijkijk ijijk iji j ijkik j c xd y xbi yai k , (8-4) (8-5) ,0 , , (8-6) ijijk k iijj i ijijk xyi j r xuj xyi j k 讨论 模型规模：假设30个产品，10个仓库，100 个需求点。 用拉格朗日方法来简化模型 8.3.2.1.2 更精确的模型 重的货物只能放在卡车底部，轻的货物可 放在卡车底部或上部 放在卡车底部的货物要考虑体积系数，放 在卡车上部的货物要考虑面积系数。每车 的体积系数不能超过48，面积系数不能超 过24，这两个系数独立

27、考虑。 定义参数 cij =产品i从其工厂到仓库j的单位运费 dj =仓库j到市场的整车运费 ei =产品i的体积因子 fi =产品i的面积因子 ai =市场对产品i的需求 h=重的产品集和 l=轻的产品集和 l变量 xij =重产品i运到仓库j的数量 zij =轻产品i装在卡车下部运到仓库j wij =轻产品i装在卡车上部运到仓库j yj=从仓库j到市场的卡车数量 min() (8-7) + 481,2,.,8 (8-8) 241,2,.,8 (8-9) ijijijijijjj i hji ljj iijiijj i hi l iijj i l c xczwd y e xe zyj f wyj 满足 (8-10) () (8-11) ,0 , , iji j ijiji j ijijijj xaih zwail xzwyi j k (8-12) 模型改进 问题： 超过两个仓库给一个市场供货会使系统复杂化 每个仓库只给一个市场供货每月至少需要10车 次，否则要么订单延迟，