基于马尔科夫决策过程的货物流的配给策略.doc

基于马尔科夫决策过程的货物流的配给策略徐东升1 , 周伟华2(11 中山大学管理学院 , 广州 510275 ; 21 浙江大学管理学院 , 杭州 310028)摘要 : 随着全球化趋势和不断增长的运输量 , 许多大型货站已经开始使用综合自动化装运处理系统 。在这些货站中 , 不同起点 (如仓库入口点) 和讫点 (如仓储货架) 之间的路径选择是一个至关重要的决策 , 本文中 , 我 们研究此类路径最优问题 , 并提出了有效的货物流配给策略 。该策略中不同的货物有不同的路径集合与之对应 , 且只有在权重较高的路径的饱和度较低时 , 才允许权重较小的货物在权重较高的路径上运输 , 不允许权重高的货 物在权重低的路径上运输 。我们引入马尔可夫决策过程模型进行决策 , 并通过数值试验证明我们提出的路径策略 的有效性 。关键词 : 货物流配给 ; 物料装运系统 ; 马尔科夫决策过程 ; 货站运作中图分类号 : N945文献标识码 : A文章编号 : 100426062 (2009) 04201422060引言当今社会 ,先进的自动化仓库及配送中心在全球供应链 中起着越来越重要的作用 ,例如 ,现代仓库和配送中心为了 节省劳动力 ,大量使用自动仓储系统 (ASRSs) 来利用高处空 间及加快货物的转移 。综合自动化装运处理系统 ( IASHSs) 由多个 ASRSs 及各种各样的处理站组成 ,并与物料处理设备 组成的复杂网络连接 。本论文中 ,我们讨论从一个大型空运货站 香港空运 货站 ( HACTL) 的工程项目里得到的一个设施物流网络问题 , 该问题讨论具有不同权重的多个货物流如何在起讫点之间 运输 。已 有 很 多 文 献 对 货 运 站 及 设 施 物 流 进 行 研 究 。 Stahlbock1 , Gunther 和 Kim2 及 Hartmann3 已经对这一领域进 行了很好的研究 ,韩晓龙 4 建立龙门吊的数量配置网络流模 型 。对 ASRS 路径问题的早期研究主要关注某个特殊设备的 作业规则 , Graves 等人 5 表明一个较好的路径会使得取货时 间降低达 30 %之多 ,Van de Berg 和 Gademanna6 研究了如何 在使 SR 机器完成所有存取要求的条件下选择路径 ,使总时 间最短 。还有许多文献研究了弹性制造系统 ( FMSs) 的路径策略 。 Yao 和 Pei 7 根据熵标准研究 FMSs 路径的动态部分 ,他们给 出了两种作业规则 ,并将其与“处理时间最短”( SPT) 规则进 行比较 。包括 Seidmann 和 Tenenbaum8 在内的很多学者研究 动态部分的配给策略 ,并给出使处理能力最大的最优策略 。研究表明 ,在移动电话系统中动态路径策略很有效 (Boucher多 ,典型的 IASHS 包含几百个关键设备 、大量的连接设备及成千上万个储存位置 。用状态空间的方式建立此问题的模 型就不太现实 ,主要有以下两个方面的问题 : 首先是上述提 到的网络规模庞大及计划时期较长 ; 另外 ,此问题的关键设 备按先到先服务 ( FCFS) 的原则作业 ,因此很难建立简单的时 空网络模型 。对交通运输路径的路径策略的研究也很多 。在过去十 年间 ,Merchant 和 Nemhauser11 、Carey12 使用了已公式化的动 态路径模型 ,另外 , Friesz 等 13 与 Astarita14 利用路径运输延 迟建立模型 ,杜进有等15 改进了在一定运输需求条件下对路 网上双向 、空重车流路径同时进行优化的多目标满意优化模 型 ,并通过建立独立满意度和综合满意度来衡量优化解的品 质 。侯立文等 16 同时考虑客户需求可分以及客户方和配送中心时间窗限制的前提下 ,重新构造了路径问题模型 。朱晨波等 17运用基于马尔可夫决策过程的分解方法 ,研究一种有车辆限制 、长期的直接配送的三层随机库存路径问题 。郭耀煌和钟小鹏 18 以顾客等待时间最小化作为系统目标 ,利用排 队理论研究了一类动态车辆路径的实时优化策略 。我们所研究的问题与交通路径问题的有以下不同点 :首 先 ,交通路径问题研究的对象是交通流 ,而我们的问题研究 的是单个货物 ,因此 ,前者的目的是一般是推导网络流平衡 点 ,设计交通网络 ; 而我们的目的则是寻找运输所有货物的 最优方案 。第 二 , 交 通 路 径 问 题 在 进 行 路 径 决 策 时 是 分 权 的 ,因为每个车主的决策是独立的 ; 而我们研究的空运货站 路径问题 ,可以由系统进行集中决策 。总体来说 ,前者的目 的是推导出一种网络平衡或者达到最大2最小公平 ; 而本文的目的是寻找整个系统的最优路径策略 。等 9) 。由于设备数量很少 ,上述文献都是以状态空间方式研究系统作业情况 。Kliewer 等10 建立了基于时空网络的动态模型 。但 是 , IASHS 的 网 络 规 模 比 FMS 的 网 络 规 模 大 的收稿日期 : 2009203215 修回日期 : 2009208223基金项目 : 国家自然科学基金项目 (70801053)作者简介 : 徐东升 ,男 ,1979 ,汉 ,浙江人 ,中山大学管理学院 ,讲师 。研究方向 ,供应链和物流管理 。1问题描述在介绍 我 们 的 模 型 与 方 法 之 前 , 有 必 要 先 解 释 一 下 IASHS 的组成部分及其运行过程 。一个 IASHS 系统通常由几 个 ASRS 系统及大量工作站组成 ,并且他们通过物料搬运设 备组成的网络连接起来 。单个 ASRS 用自动存储取出设备 在 ASRS 系统的进库出库台 ( SEPs) 与存储货架之间运输货 物 ,其中 ,物料搬运设备根据其功能可分为两类 。第一类是 关键设备 ,这些设备通常很昂贵 ,并且有多个输入通道获得 货物 ,多个出口通道运出货物 , 如台架运货机 ( 与自动存储 取出设备相似) 即能水平运动又能垂直运动 ,其中 ,自动运货 车水平运动 ,升降台垂直运动 ,转车台能水平的改变运送货 物的方向 。另一类是连接设备 ,他们起到连接关键设备与系 统 SEPs 的作用 ,如运输设备 、动力滚轴 、货物缓冲设备 ( 等待 关键设备处理) 。由于 IASHS 的 结 构 网 络 复 杂 , 其 中 的 动 作 也 比 单 个 ASRS 复杂 的 多 。IASHS 包 含 三 种 形 式 的 动 作 : 从 SEPs 到 ASRS 货架的存储货物动作 、从 ASRS 到 SEPs 的取出货物动 作 、不同 ASRS 之间的转运货物及从处理站到 ASRS 的转运货 物动作 。整个流程为 : 当一个航空集装箱 ULD ( 空运货站业 务的集装箱 ,接下来我们将此作为货运需求单位) 到达一个 大规模航空站时 ,首先储存在 ASRS 货架 ,接着可能被取出到 处理站进行某些特殊操作 。如被拆散成多个散包装 。接着 , 这些 ULDs (以批量箱的形式) 被转移到顾客清关中心 ,然后 运送到另一个 ASRS 进行批量储存 。最后 ,从 SEPs 取出 。HACTL 拥有超级一号货站 ,就货量而言 ,它是全球最大 的空运货站 ,图 1 是它的简图 。从图 1 可以看出 , 网络结构 很复杂 。这个货站拥有 350 多个工作站及 3500 多个存储机 架 。在 SEPs 与存储机架之间有成千上万个连接设备来进行 物料的自动搬运 。自动物料搬运设备分布在一个大楼里 ,这 个大楼分为货运大楼及分布在货运大楼东西两端的两个货 箱贮存系统 ,这两个货箱贮存系统通过 72 个高架桥与货运 大楼相连 。第一层是由动力滚轴组成的主要线路类型轨道 (下文就称此为主线路) ,这些线路不仅将普通货物储藏区与 冷藏货物储藏区分开 ,还在两个储藏区之间架起了可通行的 桥梁 。因此 ,建立这个系统的路径策略非常具有挑战性 ,设备 尤其是关键设备的选择非常困难 。为了说明这一点 ,一对起 讫点 (OD ,起点或者讫点可以是 SEP 或者存储机架) 之间至少 要包含 4 个升降机 、2 个自动运货车 、两个台架运货机及大量 的连接设备 。在 5 层高的大楼里 ,一个 OD 对有 1540 个实 际可行路径 。例如 ,最简单的路径可能是由升降台到 2 楼 , 通过主路径 ,再通过台架运货机到 4 楼的存储货架 。同样 , 还可以从 一 楼 的 工 作 站 出 发 。由 升 降 机 到 3 楼 , 通 过 高 架 桥 ,接着采用自动运货车 ,然后通过台架运货机到 4 楼的存 储货架 。目前 HACTL 的做法很简单 。HACTL 的路径策略基于路 径列表 ,列表中 ,每个 OD 对之间都由很多被赋予不同分值的路径 。根据 OD 的位置以及网络布局 ,路径列表中可以有 540 个路径 。当一单位货物要在一个 OD 对之间运输时 ,采用路径列表中分值最低的路径 ,当选择的路径中有设备在进 行维护时就选择备用路径 ,这样 ,大概 90 %的货物采用分值 最低的路径 (也可看作最短路径) 。在忙时 ,由于很多路径都要用到关键设备 ,系统采用上述路径策略时 ,经常出现严重阻塞 。数据表明 ,实际上货物 的存储与取出要花费 3 个多小时 ,显然远远达不到理想的绩 效要求 。并且 ,当前采用的路径策略不能根据需求优先要求 处理具有不同优先权的货物 。例如 ,在一个空运货站中 ,必 须赋予需要速递的货物较高的优先权 ,由于出口货物什么时 候运出取决于飞机起飞时间 ,因此出口 ULDs 比进口 ULDs 更 紧急 。由于当前路径策略的这些局限性 ,为了优化系统性能 , 在第 2 节中我们将给出货物流配给原则 ,然后建立相应的数 学模型进行分析 。第 3 节我们进行了大量的模拟实验并提 供数值结果 ,实验结果表明货物流配给策略比当前的策略优越很多 。第 4 节给出我们的结论 。2货物流配给原则及数学模型本节我们将给出货物配给原则的概念 。货物配给原则 将路径分为 若 干 不 同 的 集 合 , 每 个 集 合 对 应 一 种 货 物 流 类 型 。为了避免路径空闲或者利用率较低 ,某些特殊的路径集 合允许权重较低的需求通过 。我们考虑普通需求和紧急需 求这两种货物流类型的情况 。假设每个 OD 对之间都有两种 路径集合 :分别为普通需求和紧急需求类型设定的普通路径 和速递路径 。所有的紧急需求必须在速递路径上运输 ,但是 普通需求即可以在速递路径也可以在普通路径运输 ,这取决 于速递路径的利用情况 。通常情况下 ,普通路径的数量都多 于速递路径 ,本文中我们先研究单一速递路径问题 ,即每对 OD 之间仅存在一条速递路径的配给问题 。是否允许普通 ULD 在速递路径上运输取决于当前路径 的利用 情 况 及 接 下 来 可 能 到 达 的 潜 在 紧 急 ULDs 。本 文 用 “饱和度”表示路径的利用情况 。饱和度指路径能同时运输 的 ULDs 数量 。要特别强调的是 : 饱和度的一个重要性质就 是可恢复性 ,即当一条路径上的货物运输完成时这条路径的 饱和度可以恢复 。因此 ,系统运行的不同时刻路径的饱和度 是不断变化的 。通过权衡 (1) 为潜在紧急 ULDs 预留饱和度还是 (2) 为避 免紧急 ULDs 比预测过少而带来的饱和度浪费 ,决定是否允 许普通 ULD 使用速递路径 。本文中我们用马尔可夫决策决 策过程 (MDP) 模型来处理这一过程 。在给出模型之前 ,先定 义以下符号 。符号S :路径饱和度 。t :时期指标 , t = 1 ,2 , , T 。A t: t 时期的可用饱和度 。Rt : t 时期通过速递路径配送普通需求货物的收益 。Wt : t 时期的到达的普通货物总量 。图 1 超级一号货站的简图 ( t , A ) :状态变量 。V ( t , A ) : t 时期的最优价值函数 。N ( x) :在前一期的使用的饱和度为 x 时 ,本期可以恢复 的饱和度 。不失一般性 ,在下面的讨论中 ,为了表达方便 ,符号的下标 t 都省略 。在这个模型中 ,恢复函数 N ( x ) 表示系统中运 出 x 的 ULD 以后可以恢复的饱和度 , A + N ( S - A) 表示若前一期的可用饱和度为 A 时 ,本期的可用饱和度为 A + N ( S - Source : http :203118911661163hactlenaboutST1 brochure . pdfA) 。根据航空站的网络特征 ,我们假设 A + N ( S - A ) 满足 :1) 是关于 A 的非减函数 ; 2) 是关于 A 的凸函数 ; 3) 且 A + N ( S - A) S 。下面简单解释一下这三个性质 ,性质 1 表明网 络中 ULDs 越多从网络中运出的 ULDs 也就越多 ;性质 2 反映 了可用饱和度越大 ,网络中的阻塞就越少 ,这反过来增加了 饱和度的恢复速度 ;性质 3 表明了任一时期的可用饱和的都 不能超过总饱和度 。实际经验表明 ,饱和度恢复函数可以使前速递路径的饱和度等 ,用定理 1 决定是否用速递路径来运输 。MDP 模型及 货 物 流 配 给 原 则 的 运 用 很 复 杂 。在 运 用 MDP 模型及货物流配给原则时 ,应该考虑大量问题 ,包括 :1) 如何确定饱和度 ;2) 如何划分时期 ;3) 如何选择恢复函数 ; 4) 如何将 ULD 需求转化成离散的随机变量 。以上问题我们将在下面数值试验具体实施过程中介绍 。用线性函数 , 例 如 N ( x ) = x3 , 从 而 A + N ( S -2 A ) 3 。根据以上约定的符号 ,最优方程可表示为 :A ) = ( S +3 数值实验为了评价我们定义的路径策略的有效性 ,我们设计了 一个仿真体统 ,该仿真系统具有实际空运货站的主要特征 。 该仿真实验是在一台 CPU 双核 210 GHz ,内存 1024M 的个人 电脑上进行的 。货物流分为两类 :普通类和紧急类 。311 数据生成与参数设定我们选两个不同的最短路径策略作为基准 ,一个是分类 独立的最短路径 ( SPI) 策略 , 另一个是分类依赖的最短路径 ( SPD) 策略 。其中 SPI 这样决策 ,给定一个 ULD ,不论其类型 , 根据其 OD 确定一条最短路径运输这个 ULD 。SPD 则是对每 个 OD ,确定 一 组 路 径 , 每 条 路 径 对 应 一 个 权 重 类 型 。给 定 ULD 并确定其权重类型后 ,就找到相应路径来进行运输 。现在我们来构造货物流配给 ( FR) 路径策略 ,首先用 SPI 策略的最短路径作为速递路径 ,另外有三个路径作为普通路 径 。假 设 用 SPI 可 以 完 成 90 % 的 ULDs , 并 记 录 模 拟 时 间 (32400 秒) 内每个 OD 对能完成的 ULDs 的运输量 。连续进行100 次 ,记录 其 平 均 值 , 并 将 其 作 为 速 递 路 径 的 饱 和 度 。另 外 ,我们选定每个时期的时间长度为 1 小时 ,因此 ,整个模拟 时间就可以分为 9 个时期 ,即 T = 9 ,恢复函数设为 N ( x ) = x ,其中参数 根据一个时期内对 应 路 径 能 完 成 的 ULDs 的运输量的平均值来确定 。另外 ,我们注意到 ULD 的到达规律服从泊松过程 ,下一时期的 ULD 量服从泊松分布 。鉴于阻V ( t , A) = EW , R max V ( t + 1 , A -V ( t + 1 , A + N ( S - A ) ) 且边界条件为 :W + N ( S -A) ) + R ,V ( T + 1 , A)= 0.下面的 引 理 和 定 理 指 出 了 MDP 模 型 的 最 优 函 数 的 性质 。引理 1给定 t 时 , V ( t , A) 是 A 的非减函数 。证明 :用数学归纳法来证明 。显然 V ( T + 1 , A ) 是 A 的 非减函数 ,假设 V ( t + 1 , A ) 是 A 的非减函数 ,其中 t = T , T -1 , ,1 ,我们需要证明 V ( t , A ) 是非减的 。由于 A + N ( S -A ) 是非减的 ,所以对任意给定 R 和 W , V ( t + 1 , A - W + N ( S- A) ) + R 与 V ( t + 1 , A + N ( S - A ) ) 都 是 非 减 函 数 , 因 此 max V ( t + 1 , A - W + N ( S - A ) ) + R , V ( t + 1 , A + N ( S - A) ) 是非减函数 ,从而 V ( t , A ) 是非减函数 ,命题得证 。引理 2 给定 t 时 , V ( t , A) 是 A 的凸函数 。证明 :同样 , 还 是 用 数 学 归 纳 法 。首 先 , 显 然 t = T + 1 时 ,命题成立 。假设给定 t , V ( t + 1 , A ) 是 A 上的凸函数 ,其 中 t = T , T - 1 , ,1 , 我们需要证明 V ( t , A ) 也是 A 的凸函 数 。由于 A + N ( S - A ) 是凸函数且 V ( t , A ) 是非减的 ,所以 V ( t + 1 , A - W + N ( S - A) ) + R 与 V ( t + 1 , A + N ( S - A ) ) 都是凸函数 ,从而 ,对任意给定的 R , W ,max V ( t + 1 , A - W+ N ( S - A) ) + R , V ( t + 1 , A + N ( S - A ) ) 是凸函数 ,这就 意味着 V ( t , A) 是凸函数 ,命题得证 。定理 1 最优策略为 :接受 ,如果 R RW ( t + 1 , A )拒绝 ,如果 R RW ( t + 1 , A )如果 W > A其中 ,u塞以指数形式增长 ,我们设定 R ( t ) = ( Wt ) p Wt ,其中 ,u( Wt ) = 3 Wt 是 Wt 的增函数 , p 是紧急货物的成本系数 , 设 为 3 。最后 ,普通 ULDs 以随机形式分配到普通路径 ,即将普 通 ULDs 均匀分布到可能的普通路径上 。312 实验结果与分析我们构建了一个仿真的系统 , 由 166 个重要设备和 304 个连接设备组成 。这个系统共有 3 层 ,上述设备在这个系统 中均匀地分布 。此外 ,为了 测 试 我 们 的 策 略 在 不 同 货 物 流 环 境 下 的 表 现 ,我 们 考 虑 了 两 种 情 形 , 稳 定 货 物 流 ( UR) 和 变 动 货 物 流 (VR) 。这两种 情 形 下 , 货 物 流 都 是 依 照 Poisson 过 程 来 到 。 但是第一 种 货 物 流 情 形 下 , Poisson 过 程 的 速 率 是 常 数 不 变 的 ;但是在第二种情形下 , Poisson 过程的速率是变化的 。速 率的取值 ,见表格 n 列 。由于篇幅限制 ,这个仿真系统的细节和实验数据的取得 详见 19 。我们给出以下试验结果 : 其中表 1 给出给出 UR 情形下的绩效结果 ,表 2 给出 VR 情形下的绩效结果 。在这两个表中 ,第一列是参数n 的值 ,从第 2 至第 13 列RW ( t , A) = V ( t , A + N ( S - A) ) - V ( t , A -并且 ,对给定 t , RW ( t , A) 是非减的 。W + N ( S - A ) ) 。证明 :根据 RW ( t , A ) 及 V ( t , A ) 的定义 , 该策略是一个 当前最优策略 ( myopic strategy) ,由于该模型的收益函数是独 立的变量 R ,根据马尔科夫决策过程的性质 ,该局部最优策 略也是全局最优策略 。并且 ,由于 V ( t , A ) 关于是 A 的凸函 数及 A + N ( S - A ) 是 A 的非减函数 ,因此对给定 t , RW ( t , A) 是非减的 。我们的货物运输策略如下 : (1) 对于紧急货物 ,我们直接用速递路径来运输 ; (2) 对于普通货物 ,依据其数量 、收益 、当分成 SPI、SPD 、FR 三个模块 ,每块中从左到右各列依次是运输的普通 ULDs 的 数 量 、运 输 的 紧 急 ULDs 的 数 量 、每 单 位ULD 的延迟 h0 、单位 ULD 的总运输成本 h1 。参 考 文 献1Stahlbock Robert , Vob Stefan. Operations research at container terminals : A literature update . OR Spectrum , 2008 , 30 : 152 . Gunther Hans2Otto , Kim Kap2Hwan. Container terminals and terminal operations. OR Spectrum , 2006 ,28 :437445 .Hartmann Sonke . A general framework for scheduling equipment and manpower at container terminals. OR Spectrum , 2004 ,26 , 5174 . 韩晓龙. 集装箱港口装卸中的龙门吊数量配置J . 系统工程 ,2005 ,10 .Graves RJ , Hausman WH , Schwarz LB. Storage2retrieval interleaving in automatic warehousing systems J . Management Science , 1977 ,23 (9) : 935945 .Van den Berg J P , Gademanna AJ RM. Optimal routing in an automated storageretrieval system with dedicated storage J . IIE Transactions , 1999 ,31 (5) :407415 .Yao D , F Pei F. Flexible parts routing in manufacturing systemsJ . IIE Transactions , 1990 ,22 (1) :4855 .Seidmann A , Tenenbaum A. Throughput maximization in flexible manufacturing systems J . IIE Transactions , 1994 , 26 ( 1 ) : 90 100 .Boucher TO , Yalcin A , Tai T. Dynamic routing and the performance of automated manufacturing cellsJ . IIE Transactions , 2000 ,32 (8) :975988 .Kliewer N , Melloulia T , Suhla LA time2space network based exact optimization model for multi2depot bus scheduling J . European Journal of Operational Re2search , 2005 ,173 (3) :16161627 . Merchant D , Nemhauser G. A model and an algorithm for dynamic traffic assignment problems J . Transportation Science , 1978 , 12 :183199 .Carey M. Nonconvexity of the dynamic traffic assignment problemJ . Transportation Research B , 1992 ,26 (2) :127133 .Friesz TL , Bernstein D , Smith TE , et al . A variational inequality formulation of the dynamic network user equilibrium problem J . Operations Research , 1993 ,41 :179191 .Astarita V. A continuous time link model for dynamic network loading based on travel time function. in Proceeding 13th International Symposium on Transportation and Traffic Theory , Pergamon2Elsevier ,1996 :79102 .杜进有 ,姚新胜 ,黄洪钟. 路网车流径路的满意优化 J . 系统 工程 ,2005 (9) .侯立文 ,谭家美 ,赵元. 求解带时间窗的客户需求可分条件下 的车辆路径问题. 中国管理科学 ,2007 (6) .朱晨波 , 叶耀华 , 戴锡. 直接配送的三层随机库 存 路 径 问 题J . 系统工程理论与实践 ,2007 (12) .郭耀煌 ,钟小鹏. 动态车辆路径问题排队模型分析 J . 管理科 学学报 ,2006 (1) .Xu DS. Resource Allocation among Multiple Stochastic DemandClasses in Express Delivery Chains D . HKUST , 2007 . PhD Dissertation.表 1UR 情况的结果23456表 2VR 情况的结果78910从以上表格看 ,结果令人满意 。平均而言 ,在表 1 UR 的情况下 ,FR 运输的总 ULDs 量比 SPI 提高 911 % 、比 SPD 提高417 % 。这表明 FR 的系统能力显著增加 ,平均比 SPI ( SPD) 高9 % (4 %) 。因此 ,从运输能力来看 , 这种运输策略有助于改 善系统绩效 、降低成本 。另一方面 ,在表 1 UR 的情况下 ,与 SPI 情况相比 , FR 的 每单位 ULD 的延迟 h0 降低了 3113 % 、单位 ULD 的总运输成 本 h1 降低了 913 % ;与 SPD 情况相比 ,FR 的 h0 和 h1 分别降 低了 2113 %与 510 % 。这表明 ,通过更好的分配货物流的路 径 ,FR 将货物延迟降低了约 14 ,而 SS 的延迟又是衡量一个 IASHS 服务质量的一个重要绩效指标 。在 VR 情况下结果类似 。11121314154结论我们给出了一个货物流路径配给策略 ,该策略中每种类 型的 ULDs 各有不同的路径集合与之对应 ,且只有饱和度较 低时才允许权重较低的 ULDs 在权重比它高的路径上运输 。 我们还用 MDP 模型来决定是否接受订单 , 并给出其结构形 式 。后续研究还需研究以下方面 。首先 ,应该研究每种类型 的 ULDs 在对应路径集合上如何分配 ,如普通 ULDs 在普通路 径上的分配 。第二 ,还需注意每种类型 ULDs 应该有多少路 径与之对应 。最后 ,利用实时信息不断更新恢复函数 ,有助于改善模型 ,我们后续将进行此研究 。16171819nSPISPDFRNUh0h1NUh0h1NUh0h111261135114411531162Avg376 12813 2417 1741836712 12719 1311 1541539511 13218 2815 1811838117 12415 1915 1671241917 14017 3314 1901038719 13018 2318 1731737117 12713 1515 1561537019 12819 1215 15819404 13615 2611 1671341217 13412 1916 1621842912 14312 2910 1811839717 13410 2016 1651537517 12815 1218 1521837714 13115 1212 1481841212 13816 1710 1601343212 14118 1518 1561144516 15018 1917 1671540816 13812 1515 15711nSPISPDFRNUh0h1NUh0h1NUh0h111261135114411531162Avg38912 12619 1910 1641639416 13314 2218 1731240317 13413 2716 1811040915 13914 1918 1661742215 13416 5410 2211740319 13317 2816 1811439417 13013 1419 1561340217 13516 2416 1731843415 14611 2016 1681541710 14018 1515 1561945214 14612 2316 1721242013 13918 1918 1651539518 129 1319 1541841313 14016 1219 1531644913 150 1810 1541845314 15214 1419 1471049319 15719 1817 1661944111 14610 1517 15514Markov Decision Processes Model f or Flo w Rationing Routing StrategyXU Dong2sheng1 , ZHOU Wei2hua2(11School of Management , Sun Yat2sen University , Guangzhou 510275 , China ;21School of Management , Zhejiang University , Hangzhou 310028 , China)Abstract : With the trend of globalization and increasing transportation volume , integrated automated shipment handling systems have appearedin major cargo terminals. In such terminals , a critical decision is the route selection linking various origins ( such as system gate points) and destinations ( such as storage racks) . We study such a routing optimization problem and propose a flow rationing routing strategy , which reserves various sets of paths for corresponding cargos and only admits the cargos with less importance on more important paths only when their saturability is low. A Markov Decision Processes model is developed to make the decision on the admission policy. Extensive numerical experiment is conducted to prove the effectiveness of the routing strategy we proposed.Key words : flow rationing ; material handling system ; markov decision processes ; terminal operations责任编辑 : 杜 健(上接第 141 页)contract projects J . Journal of construction engineering and management , 2005 ,131 (2) : 211220 .Shen L Y , Bao HJ , Wu YZ. Using bargaining2game theory fornegotiating concession period for BOT2type contract J . Journal of construction engineering and managem