大型货站货物流配给策略研究

大型货站货物流配给策略研究

0动态路径策略随着当今社会，先进的自动仓库和配送中心在全球供应链中发挥着越来越重要的作用。例如，为了节省劳动力，现代物流中心（rss）使用自动仓库系统（rss）来使用较高的空间，加快货物的转移。综合自动化装运处理系统(IASHSs)由多个ASRSs及各种各样的处理站组成,并与物料处理设备组成的复杂网络连接。本论文中,我们讨论从一个大型空运货站——香港空运货站(HACTL)的工程项目里得到的一个设施物流网络问题,该问题讨论具有不同权重的多个货物流如何在起讫点之间运输。已有很多文献对货运站及设施物流进行研究。Stahlbock,Gunther和Kim及Hartmann已经对这一领域进行了很好的研究,韩晓龙建立龙门吊的数量配置网络流模型。对ASRS路径问题的早期研究主要关注某个特殊设备的作业规则,Graves等人表明一个较好的路径会使得取货时间降低达30%之多,VandeBerg和Gademanna研究了如何在使SR机器完成所有存取要求的条件下选择路径,使总时间最短。还有许多文献研究了弹性制造系统(FMSs)的路径策略。Yao和Pei根据熵标准研究FMSs路径的动态部分,他们给出了两种作业规则,并将其与“处理时间最短”(SPT)规则进行比较。包括Seidmann和Tenenbaum在内的很多学者研究动态部分的配给策略,并给出使处理能力最大的最优策略。研究表明,在移动电话系统中动态路径策略很有效(Boucher等)。由于设备数量很少,上述文献都是以状态空间方式研究系统作业情况。Kliewer等建立了基于时空网络的动态模型。但是,IASHS的网络规模比FMS的网络规模大的多,典型的IASHS包含几百个关键设备、大量的连接设备及成千上万个储存位置。用状态空间的方式建立此问题的模型就不太现实,主要有以下两个方面的问题:首先是上述提到的网络规模庞大及计划时期较长;另外,此问题的关键设备按先到先服务(FCFS)的原则作业,因此很难建立简单的时空网络模型。对交通运输路径的路径策略的研究也很多。在过去十年间,Merchant和Nemhauser、Carey使用了已公式化的动态路径模型,另外,Friesz等与Astarita利用路径运输延迟建立模型,杜进有等改进了在一定运输需求条件下对路网上双向、空重车流路径同时进行优化的多目标满意优化模型,并通过建立独立满意度和综合满意度来衡量优化解的品质。侯立文等同时考虑客户需求可分以及客户方和配送中心时间窗限制的前提下,重新构造了路径问题模型。朱晨波等运用基于马尔可夫决策过程的分解方法,研究一种有车辆限制、长期的直接配送的三层随机库存路径问题。郭耀煌和钟小鹏以顾客等待时间最小化作为系统目标,利用排队理论研究了一类动态车辆路径的实时优化策略。我们所研究的问题与交通路径问题的有以下不同点:首先,交通路径问题研究的对象是交通流,而我们的问题研究的是单个货物,因此,前者的目的是一般是推导网络流平衡点,设计交通网络;而我们的目的则是寻找运输所有货物的最优方案。第二,交通路径问题在进行路径决策时是分权的,因为每个车主的决策是独立的;而我们研究的空运货站路径问题,可以由系统进行集中决策。总体来说,前者的目的是推导出一种网络平衡或者达到最大-最小公平;而本文的目的是寻找整个系统的最优路径策略。1hactl的路径策略在介绍我们的模型与方法之前,有必要先解释一下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对有15～40个实际可行路径。例如,最简单的路径可能是由升降台到2楼,通过主路径,再通过台架运货机到4楼的存储货架。同样,还可以从一楼的工作站出发。由升降机到3楼,通过高架桥,接着采用自动运货车,然后通过台架运货机到4楼的存储货架。目前HACTL的做法很简单。HACTL的路径策略基于路径列表,列表中,每个OD对之间都由很多被赋予不同分值的路径。根据OD的位置以及网络布局,路径列表中可以有5～40个路径。当一单位货物要在一个OD对之间运输时,采用路径列表中分值最低的路径,当选择的路径中有设备在进行维护时就选择备用路径,这样,大概90%的货物采用分值最低的路径(也可看作最短路径)。在忙时,由于很多路径都要用到关键设备,系统采用上述路径策略时,经常出现严重阻塞。数据表明,实际上货物的存储与取出要花费3个多小时,显然远远达不到理想的绩效要求。并且,当前采用的路径策略不能根据需求优先要求处理具有不同优先权的货物。例如,在一个空运货站中,必须赋予需要速递的货物较高的优先权,由于出口货物什么时候运出取决于飞机起飞时间,因此出口ULDs比进口ULDs更紧急。由于当前路径策略的这些局限性,为了优化系统性能,在第2节中我们将给出货物流配给原则,然后建立相应的数学模型进行分析。第3节我们进行了大量的模拟实验并提供数值结果,实验结果表明货物流配给策略比当前的策略优越很多。第4节给出我们的结论。2mdp模型求解本节我们将给出货物配给原则的概念。货物配给原则将路径分为若干不同的集合,每个集合对应一种货物流类型。为了避免路径空闲或者利用率较低,某些特殊的路径集合允许权重较低的需求通过。我们考虑普通需求和紧急需求这两种货物流类型的情况。假设每个OD对之间都有两种路径集合:分别为普通需求和紧急需求类型设定的普通路径和速递路径。所有的紧急需求必须在速递路径上运输,但是普通需求即可以在速递路径也可以在普通路径运输,这取决于速递路径的利用情况。通常情况下,普通路径的数量都多于速递路径,本文中我们先研究单一速递路径问题,即每对OD之间仅存在一条速递路径的配给问题。是否允许普通ULD在速递路径上运输取决于当前路径的利用情况及接下来可能到达的潜在紧急ULDs。本文用“饱和度”表示路径的利用情况。饱和度指路径能同时运输的ULDs数量。要特别强调的是:饱和度的一个重要性质就是可恢复性,即当一条路径上的货物运输完成时这条路径的饱和度可以恢复。因此,系统运行的不同时刻路径的饱和度是不断变化的。通过权衡(1)为潜在紧急ULDs预留饱和度还是(2)为避免紧急ULDs比预测过少而带来的饱和度浪费,决定是否允许普通ULD使用速递路径。本文中我们用马尔可夫决策决策过程(MDP)模型来处理这一过程。在给出模型之前,先定义以下符号。符号S:路径饱和度。t:时期指标,t=1,2,…,T。At:t时期的可用饱和度。Rt:t时期通过速递路径配送普通需求货物的收益。Wt:t时期的到达的普通货物总量。(t,A):状态变量。V(t,A):t时期的最优价值函数。N(x):在前一期的使用的饱和度为x时,本期可以恢复的饱和度。不失一般性,在下面的讨论中,为了表达方便,符号的下标t都省略。在这个模型中,恢复函数N(x)表示系统中运出x的ULD以后可以恢复的饱和度,A+N(S-A)表示若前一期的可用饱和度为A时,本期的可用饱和度为A+N(S-A)。根据航空站的网络特征,我们假设A+N(S-A)满足:1)是关于A的非减函数;2)是关于A的凸函数;3)且A+N(S-A)≤S。下面简单解释一下这三个性质,性质1表明网络中ULDs越多从网络中运出的ULDs也就越多;性质2反映了可用饱和度越大,网络中的阻塞就越少,这反过来增加了饱和度的恢复速度;性质3表明了任一时期的可用饱和的都不能超过总饱和度。实际经验表明,饱和度恢复函数可以使用线性函数,例如N(x)=x/3,从而A+N(S-A)=(S+2A)/3。根据以上约定的符号,最优方程可表示为:V(t,A)=EW,R{max{V(t+1,A-W+N(S-A))+R,V(t+1,A+N(S-A))}}且边界条件为:V(T+1,A)=0.V(Τ+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最优策略为:其中,RW(t,A)=V(t,A+N(S-A))-V(t,A-W+N(S-A))。并且,对给定t,RW(t,A)是非减的。证明:根据RW(t,A)及V(t,A)的定义,该策略是一个当前最优策略(myopicstrategy),由于该模型的收益函数是独立的变量R,根据马尔科夫决策过程的性质,该局部最优策略也是全局最优策略。并且,由于V(t,A)关于是A的凸函数及A+N(S-A)是A的非减函数,因此对给定t,RW(t,A)是非减的。我们的货物运输策略如下:(1)对于紧急货物,我们直接用速递路径来运输;(2)对于普通货物,依据其数量、收益、当前速递路径的饱和度等,用定理1决定是否用速递路径来运输。MDP模型及货物流配给原则的运用很复杂。在运用MDP模型及货物流配给原则时,应该考虑大量问题,包括:1)如何确定饱和度;2)如何划分时期;3)如何选择恢复函数;4)如何将ULD需求转化成离散的随机变量。以上问题我们将在下面数值试验具体实施过程中介绍。3实际造成的仿真实验为了评价我们定义的路径策略的有效性,我们设计了一个仿真体统,该仿真系统具有实际空运货站的主要特征。该仿真实验是在一台CPU双核2.0GHz,内存1024M的个人电脑上进行的。货物流分为两类:普通类和紧急类。3.1合成货物流配我们选两个不同的最短路径策略作为基准,一个是分类独立的最短路径(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量服从泊松分布。鉴于阻塞以指数形式增长,我们设定R(t)=σ(Wt)puWt,其中,σ(Wt)=3Wt是Wt的增函数,pu是紧急货物的成本系数,设为3。最后,普通ULDs以随机形式分配到普通路径,即将普通ULDs均匀分布到可能的普通路径上。3.2仿真结果的分析我们构建了一个仿真的系统,由166个重要设备和304个连接设备组成。这个系统共有3层,上述设备在这个系统中均匀地分布。此外,为了测试我们的策略在不同货物流环境下的表现,我们考虑了两种情形,稳定货物流(UR)和变动货物流(VR)。这两种情形下,货物流都是依照Poisson过程来到。但是第一种货物流情形下,Poisson过程的速率是常数不变的;但是在第二种情形下,Poisson过程的速率是变化的。速率的取值,见表格λn列。由于篇幅限制,这个仿真系统的细节和实验数据的取得详见。我们给出以下试验结果:其中表1给出给出UR情形下的绩效结果,