集成物流管理系统中定位-运输路线安排问题的研究
- 格式：pdf
- 大小：345.68 KB
- 文档页数：11
该类问题的特点是所运送货物的数量具有随
机特性. 如银行定位 车辆接款路线的安排; 邮局 选址 信件收发的路线安排; 废品集中处理点的 定位与运输车辆的路线安排等. 在解决这一类问 题时, 由于各个节点货物的数量事先未知, 常会造 成车辆在行程中未到达目的地承载量已满的情况
第2期
汪寿阳等 集成物流管理系统中定位 运输路线安排问题的研究
7l
卸下货物9然后继续沿剩余路线行驶. 在这类问题中9除了考虑通常的各项成本外9
还需要考虑由于货物量事先未知所造成的运输成
本9目标是使总的费用最低. 解决该类问题的关键 是得出各个节点货物量的概率分布9并在此基础 上确定设施的位置并安排车辆的运输路线9从而 使得 < lD 在运输路线上产生失误的概率不超过某 一预置值 ; 或< 2D 运输路线上出现多余行程的期 望值不超过原计划长度的 分之一. 和 是根据 实际情况事先给出的参数. 1. . 有害物品运输中的定位 行程安排问题
( 10) 目 标 函 数: 指 解 决 问 题 所 要 达 到 的 目 标. 若求解的目的仅为使成本最低或某一其他目 标9则为单目标函数; 而在实际情形中9往往存在 多于一个的目标函数9例如9最小成本行程路线安 排9最初以客户代码在空间的分散情况为基础9可 能会不满足客户对及时配送服务的需求. 多目标 的特性普遍存在于实际的 LRP 中.
1. 1 一般的 LRP 一般的 LRP 可表述如下[10]: 某公司从一个或多个设施为客户配送货物,
客户的数量~ 位置~ 需求量已知或可估计出, 设施 为工厂~ 仓库~ 分销中心等, 现有若干个设施的位 置可供选择, 但每个客户仅从一个设施得到货物, 即在一定的时间内, 每个客户仅被运输车辆访问 一次. 需要解决的问题是: 在满足一定约束条件 下, < 1> 选择设施的位置和数量; < 3> 确定最佳的运 输行程路线, 使得总费用最低. 总费用指设施的建 设成本~ 运作成本以及车辆的固定成本~ 运输成本 等. 约束条件包括: 设施和运输车辆的容量和数量 的限制; 交货时间窗口限制等. 1. 2 研究领域的扩展
( 8) 计划期间: 指问题所考虑的期间. 若将整 个期间按单一时间段来考虑9则问题被视为是静 态的; 若将整个期间按需求 供应的特性分为不同 的时间段9并在各个时间段内进行决策9则为动态 的 LRP.
( 9) 时间窗口: 指客户对交货时间的要求9分 限定和不限定两种. 而限定时间窗口又可分为较 松期限和严格期限的时间窗口.
( 6) 设施的容量: 指设施可达到的最大库存 量或最大的处理能力9分限定和不限定两种.
( 7) 设施的层次: 指设施在配送过程所处于 的级别9分第一级和第二级两种. 第一级设施指运 输行程的起始点或目的地; 第二级设施指运输过 程的中间点或中转站9如军事仓储点9仓库9分销 中心9废品转运站等. 在分析第二级设施定位时9 一般假定第一级设施定位于已知 固定的地点.
( 11) 模型中数据的来源: 指建模中所使用数 据的来源9分实际的数据和假设的数据两种.
需要指出的是: 由于问题的复杂性9多数关于 LRP 的研究都作出了一定的假设9因此9实际上 往往只考虑了问题的某些方面. 所以建立的模型
与实际情形会有一定的出入9这必然会影响使用 该模型来处理实际问题的效果.
2 解题的算法
< location-routing problems, LRP> 进 行 了 综 合 研 究. 通过建立 LRP 模型, 对于多客户与多设施的 情形, 可同时解决确定设施最优数量~ 容量与寻求 最优运输计划~ 路线安排之间的总体问题, 从而降 低物流成本, 提高产品分销的效率. 图 3 给出了一 个简单 LRP 的示意图.
所涉及到的有关内容及其特点9如表 l 所示.
72
管理科学学报
2000 年 6 月
下面对上述列表逐一进行解释. ( 1) 需求/供应的特性: 指定位和行程路线安
排中参数的特征. 确定型 LRP 模型假定各个参数 如需求/供应量是已知的并在一定期间内固定不 变; 而随机型 LRP 模型认为这些参数具有不确定 和随机的特性.
1 LRP 的特点
图 2 VRP 示意图
图 3 LRP 示意图
关 于 LRP 的 研 究 开 始 于 70 年 代, WatsonGandy 和 Dohrn 将 运 输 车 辆 行 程 安 排 的 多 点 停 留特性与定位-运输网络结合起来开展了研 究[2]. 但 由 于 LRP 问 题 的 解 决 比 通 常 的 运 输/ 定 位模型的难度要大得多, 因此, 对该类问题的研究 进展相当缓慢. 直到 S0 年代后期, 由于实际应用 的迫切需要, LRP 的研究才得到了学术界的广泛 重视. 据不完全统计, 迄今为止, 在英文出版物中, 有关 LRP 的模型~ 算法的研究及综述文章和论著 已有数百篇. 特别需要指出的是: 90 年代以来, 随 着集成物流管理的概念被愈来愈多的企业所接受
除包括物流管理中一般的定位 配送问题
外, LRP 还可应用于以下领域[12~ 17]. 1. 2. 1 旅行修理者的定位 行程安排问题
与设施定位 车辆行程安排问题相类似, 该 问题也是确定设施< 此处为修理者的出发点> 的位 置与修理者对节点< 客户> 的访问路线, 但目标函 数是使各客户的总等待时间最短. 如果同时还要 求旅行修理者的行程路线最短, 则是双目标决策 问题. 1. 2. 2 货物收集的定位 行程安排问题
步骤之一. 分销渠道是指产品在其所有权转移过 程中从生产领域进入消费领域的途径~ 而分销渠 道中的物流管理则是指通过有效地安排产品的仓
储 管理和转移~ 使产品在需要的时间到达需要的 地点的经营活动.
在 物 流 管 理 决 策 中~ 定 位 配 给 问 题 ( location allocation problems~ LAP) 和 车 辆 运 输 行 程 安 排 问 题 ( vehicle routing problems~ VRP) 是得到较多关注的两个方面. 定位 配给问题考 虑设施( 工厂 库存点 分销中心等)的定位与货物 配给之间的相互关系~ 目的是对设施的数量 位置 进行决策~ 使设施的运作成本及车辆的运输成本 最低. 在 LAP 中~ 一般认为设施到客户的运输路 线是放射线状的~ 即运输车辆每次访问一个客户 后~ 就返回到设施点( 见图 1) . 因此~ 在确定设施 的位置时~ 忽视了对车辆巡回的行程路线的考虑~
图 1 LAP 示意图
运输行程安排问题则是指在设施位置已知的
前提下~ 确定车辆在各个客户间的行程路线~ 使得 运输路线最短或运输成本最低( 见图 2) . 在 VRP 问题中~ 考虑了车辆在各个客户点间巡回访问的 特性~ 提高了运输效率~ 并与实际情形相吻合. 但 在此问题中~ 未分析设施的选址问题~ 使得整个物 流成本不能达到最低.
第 3 卷第 2 期 2000 年 6 月
管理科学学报 JOURNAL OF MANAGEMEN SCIENCES IN CHINA
Vol. 3 No. 2 Jun. 2000
集成物流管理系统中定位 运输路线 安排问题的研究D
汪寿阳1~ 赵秋红2~ 夏国平2
( 1. 国家自然科学基金委员会管理科学部~ 北京 1000839 2. 北京航空航天大学管理学院~ 北京 100083)
可用两种不同的方法来解决 LRP 问题9这就 是精确算法和启发式算法. 2. 1 精确算法
类 似 于 Laporte 所 提 出 的 运 输 行 程 问 题 ( VRP) 分 类 计 划9LRP 的 精 确 算 法 可 以 分 为 四 类 : [2] ( 1) 整数规划方法; ( 2) 动态规划方法; ( 3) 混 合整数规划方法; ( 4) 非线性规划方法.
和全球贸易的快速增长, 提高分销效率成为了企 业生存与发展的必由之路, LRP 的研究在各相关 领 域 得 到 了 特 别 的 关 注, 取 得 了 较 大 的 发 展[1, 3, 4, 6, 7, S]. 但 遗 憾 的 是, 到 目 前 为 止, 国 内 尚 未 见到关于这一领域有影响的研究成果的报道. 作 者希望通过本文能引起国内学术界对集成物流管 理系统研究的重视, 使得一批有为的青年学者能 结合中国企业的实际问题开展关于 LRP 的研究.
D 国家自然科学基金资助项目( 79670091) . 作者简介: 汪寿阳( 1958-) ~ 男( 汉族) ~ 江苏人~ 研究员.
70
管理科学学报
2000 年 6 月
的关系, 根据这种关系来相应地进行综合优化与 管理. 应用这种集成物流管理系统的概念, 国外一 批学者对设施定位 车辆运输路线安排问题
由以上两节的分析9可列出目前 LRP 的研究
需求/供应的特性 设施的数量 运输车辆的数量 车辆承载能力 运输持续时间 设施的容量 设施的层次 计划期间 时间窗口
目标函数 模型中数据的来源
确定 单一设施 单一运输工具 不限定 不限定 不限定 第一级 单一期间 未限定
单一目标 假设
随机 多设施 多运输工具 限定 限定 限定 第二级< 中间转换点D 多期间 限定 较松期限 严格期限 多目标 实际
指有害物质< 如化工废料~ 放射性物质~ 各种
有害废物D 集中处理点设施的选址与运输行程安 排问题. 考虑到物品处理点对周围地区的危害性9 运输过程中对沿途地区的危害性以及处理过程发
生事故的概率9该类问题具有多个目标. 目标包 括 定位和运输的费用~ 各种危害性~ 危害程度在 地区间的均衡性等. 通常在研究中假设 < lD 物品 的危害性有一定的范围9如在某一半径 1 内; < 2D 危害程度与人口密度成正比; < 3D 运输过程沿途地 区的人口服从均匀分布. 1. . 4 多级设施的定位 配送问题
随着物质需求的多样性和不规则性以及贸易
呈全球化趋势的发展~ 企业管理者希望能协调物 流系统中的各个环节~ 以最低的价格 最好的服务 来满足顾客的需要. 由此~ 在 LAP VRP 和 其 他 物流决策模型的基础之上~ 产生了集成物流管理 系统的概念[2]. 这种概念认为: 在设施( 制造厂 库 存点或分销中心) 相对于客户的位置 货物的配 给 运输货物的车辆路线安排之间存在相互依赖
机特性. 如银行定位 车辆接款路线的安排; 邮局 选址 信件收发的路线安排; 废品集中处理点的 定位与运输车辆的路线安排等. 在解决这一类问 题时, 由于各个节点货物的数量事先未知, 常会造 成车辆在行程中未到达目的地承载量已满的情况
第2期
汪寿阳等 集成物流管理系统中定位 运输路线安排问题的研究
7l
卸下货物9然后继续沿剩余路线行驶. 在这类问题中9除了考虑通常的各项成本外9
还需要考虑由于货物量事先未知所造成的运输成
本9目标是使总的费用最低. 解决该类问题的关键 是得出各个节点货物量的概率分布9并在此基础 上确定设施的位置并安排车辆的运输路线9从而 使得 < lD 在运输路线上产生失误的概率不超过某 一预置值 ; 或< 2D 运输路线上出现多余行程的期 望值不超过原计划长度的 分之一. 和 是根据 实际情况事先给出的参数. 1. . 有害物品运输中的定位 行程安排问题
( 10) 目 标 函 数: 指 解 决 问 题 所 要 达 到 的 目 标. 若求解的目的仅为使成本最低或某一其他目 标9则为单目标函数; 而在实际情形中9往往存在 多于一个的目标函数9例如9最小成本行程路线安 排9最初以客户代码在空间的分散情况为基础9可 能会不满足客户对及时配送服务的需求. 多目标 的特性普遍存在于实际的 LRP 中.
1. 1 一般的 LRP 一般的 LRP 可表述如下[10]: 某公司从一个或多个设施为客户配送货物,
客户的数量~ 位置~ 需求量已知或可估计出, 设施 为工厂~ 仓库~ 分销中心等, 现有若干个设施的位 置可供选择, 但每个客户仅从一个设施得到货物, 即在一定的时间内, 每个客户仅被运输车辆访问 一次. 需要解决的问题是: 在满足一定约束条件 下, < 1> 选择设施的位置和数量; < 3> 确定最佳的运 输行程路线, 使得总费用最低. 总费用指设施的建 设成本~ 运作成本以及车辆的固定成本~ 运输成本 等. 约束条件包括: 设施和运输车辆的容量和数量 的限制; 交货时间窗口限制等. 1. 2 研究领域的扩展
( 8) 计划期间: 指问题所考虑的期间. 若将整 个期间按单一时间段来考虑9则问题被视为是静 态的; 若将整个期间按需求 供应的特性分为不同 的时间段9并在各个时间段内进行决策9则为动态 的 LRP.
( 9) 时间窗口: 指客户对交货时间的要求9分 限定和不限定两种. 而限定时间窗口又可分为较 松期限和严格期限的时间窗口.
( 6) 设施的容量: 指设施可达到的最大库存 量或最大的处理能力9分限定和不限定两种.
( 7) 设施的层次: 指设施在配送过程所处于 的级别9分第一级和第二级两种. 第一级设施指运 输行程的起始点或目的地; 第二级设施指运输过 程的中间点或中转站9如军事仓储点9仓库9分销 中心9废品转运站等. 在分析第二级设施定位时9 一般假定第一级设施定位于已知 固定的地点.
( 11) 模型中数据的来源: 指建模中所使用数 据的来源9分实际的数据和假设的数据两种.
需要指出的是: 由于问题的复杂性9多数关于 LRP 的研究都作出了一定的假设9因此9实际上 往往只考虑了问题的某些方面. 所以建立的模型
与实际情形会有一定的出入9这必然会影响使用 该模型来处理实际问题的效果.
2 解题的算法
< location-routing problems, LRP> 进 行 了 综 合 研 究. 通过建立 LRP 模型, 对于多客户与多设施的 情形, 可同时解决确定设施最优数量~ 容量与寻求 最优运输计划~ 路线安排之间的总体问题, 从而降 低物流成本, 提高产品分销的效率. 图 3 给出了一 个简单 LRP 的示意图.
所涉及到的有关内容及其特点9如表 l 所示.
72
管理科学学报
2000 年 6 月
下面对上述列表逐一进行解释. ( 1) 需求/供应的特性: 指定位和行程路线安
排中参数的特征. 确定型 LRP 模型假定各个参数 如需求/供应量是已知的并在一定期间内固定不 变; 而随机型 LRP 模型认为这些参数具有不确定 和随机的特性.
1 LRP 的特点
图 2 VRP 示意图
图 3 LRP 示意图
关 于 LRP 的 研 究 开 始 于 70 年 代, WatsonGandy 和 Dohrn 将 运 输 车 辆 行 程 安 排 的 多 点 停 留特性与定位-运输网络结合起来开展了研 究[2]. 但 由 于 LRP 问 题 的 解 决 比 通 常 的 运 输/ 定 位模型的难度要大得多, 因此, 对该类问题的研究 进展相当缓慢. 直到 S0 年代后期, 由于实际应用 的迫切需要, LRP 的研究才得到了学术界的广泛 重视. 据不完全统计, 迄今为止, 在英文出版物中, 有关 LRP 的模型~ 算法的研究及综述文章和论著 已有数百篇. 特别需要指出的是: 90 年代以来, 随 着集成物流管理的概念被愈来愈多的企业所接受
除包括物流管理中一般的定位 配送问题
外, LRP 还可应用于以下领域[12~ 17]. 1. 2. 1 旅行修理者的定位 行程安排问题
与设施定位 车辆行程安排问题相类似, 该 问题也是确定设施< 此处为修理者的出发点> 的位 置与修理者对节点< 客户> 的访问路线, 但目标函 数是使各客户的总等待时间最短. 如果同时还要 求旅行修理者的行程路线最短, 则是双目标决策 问题. 1. 2. 2 货物收集的定位 行程安排问题
步骤之一. 分销渠道是指产品在其所有权转移过 程中从生产领域进入消费领域的途径~ 而分销渠 道中的物流管理则是指通过有效地安排产品的仓
储 管理和转移~ 使产品在需要的时间到达需要的 地点的经营活动.
在 物 流 管 理 决 策 中~ 定 位 配 给 问 题 ( location allocation problems~ LAP) 和 车 辆 运 输 行 程 安 排 问 题 ( vehicle routing problems~ VRP) 是得到较多关注的两个方面. 定位 配给问题考 虑设施( 工厂 库存点 分销中心等)的定位与货物 配给之间的相互关系~ 目的是对设施的数量 位置 进行决策~ 使设施的运作成本及车辆的运输成本 最低. 在 LAP 中~ 一般认为设施到客户的运输路 线是放射线状的~ 即运输车辆每次访问一个客户 后~ 就返回到设施点( 见图 1) . 因此~ 在确定设施 的位置时~ 忽视了对车辆巡回的行程路线的考虑~
图 1 LAP 示意图
运输行程安排问题则是指在设施位置已知的
前提下~ 确定车辆在各个客户间的行程路线~ 使得 运输路线最短或运输成本最低( 见图 2) . 在 VRP 问题中~ 考虑了车辆在各个客户点间巡回访问的 特性~ 提高了运输效率~ 并与实际情形相吻合. 但 在此问题中~ 未分析设施的选址问题~ 使得整个物 流成本不能达到最低.
第 3 卷第 2 期 2000 年 6 月
管理科学学报 JOURNAL OF MANAGEMEN SCIENCES IN CHINA
Vol. 3 No. 2 Jun. 2000
集成物流管理系统中定位 运输路线 安排问题的研究D
汪寿阳1~ 赵秋红2~ 夏国平2
( 1. 国家自然科学基金委员会管理科学部~ 北京 1000839 2. 北京航空航天大学管理学院~ 北京 100083)
可用两种不同的方法来解决 LRP 问题9这就 是精确算法和启发式算法. 2. 1 精确算法
类 似 于 Laporte 所 提 出 的 运 输 行 程 问 题 ( VRP) 分 类 计 划9LRP 的 精 确 算 法 可 以 分 为 四 类 : [2] ( 1) 整数规划方法; ( 2) 动态规划方法; ( 3) 混 合整数规划方法; ( 4) 非线性规划方法.
和全球贸易的快速增长, 提高分销效率成为了企 业生存与发展的必由之路, LRP 的研究在各相关 领 域 得 到 了 特 别 的 关 注, 取 得 了 较 大 的 发 展[1, 3, 4, 6, 7, S]. 但 遗 憾 的 是, 到 目 前 为 止, 国 内 尚 未 见到关于这一领域有影响的研究成果的报道. 作 者希望通过本文能引起国内学术界对集成物流管 理系统研究的重视, 使得一批有为的青年学者能 结合中国企业的实际问题开展关于 LRP 的研究.
D 国家自然科学基金资助项目( 79670091) . 作者简介: 汪寿阳( 1958-) ~ 男( 汉族) ~ 江苏人~ 研究员.
70
管理科学学报
2000 年 6 月
的关系, 根据这种关系来相应地进行综合优化与 管理. 应用这种集成物流管理系统的概念, 国外一 批学者对设施定位 车辆运输路线安排问题
由以上两节的分析9可列出目前 LRP 的研究
需求/供应的特性 设施的数量 运输车辆的数量 车辆承载能力 运输持续时间 设施的容量 设施的层次 计划期间 时间窗口
目标函数 模型中数据的来源
确定 单一设施 单一运输工具 不限定 不限定 不限定 第一级 单一期间 未限定
单一目标 假设
随机 多设施 多运输工具 限定 限定 限定 第二级< 中间转换点D 多期间 限定 较松期限 严格期限 多目标 实际
指有害物质< 如化工废料~ 放射性物质~ 各种
有害废物D 集中处理点设施的选址与运输行程安 排问题. 考虑到物品处理点对周围地区的危害性9 运输过程中对沿途地区的危害性以及处理过程发
生事故的概率9该类问题具有多个目标. 目标包 括 定位和运输的费用~ 各种危害性~ 危害程度在 地区间的均衡性等. 通常在研究中假设 < lD 物品 的危害性有一定的范围9如在某一半径 1 内; < 2D 危害程度与人口密度成正比; < 3D 运输过程沿途地 区的人口服从均匀分布. 1. . 4 多级设施的定位 配送问题
随着物质需求的多样性和不规则性以及贸易
呈全球化趋势的发展~ 企业管理者希望能协调物 流系统中的各个环节~ 以最低的价格 最好的服务 来满足顾客的需要. 由此~ 在 LAP VRP 和 其 他 物流决策模型的基础之上~ 产生了集成物流管理 系统的概念[2]. 这种概念认为: 在设施( 制造厂 库 存点或分销中心) 相对于客户的位置 货物的配 给 运输货物的车辆路线安排之间存在相互依赖
