美賽歷獎(jiǎng)得主僅供學(xué)習(xí)參考umcm2006b

2006年美國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽（MCM）B題機(jī)場(chǎng)中輪椅的使用（WheelchairAccessatAirports）清華大學(xué)姜啟源

乘飛機(jī)旅行需要在機(jī)場(chǎng)轉(zhuǎn)機(jī).

行動(dòng)困難旅客從一個(gè)走到另外一個(gè)候機(jī)廳特別困難.

解決辦法之一是航空公司為請(qǐng)求幫助的旅客提供輪椅和陪同人員.

通常能預(yù)先知道那些乘客要求幫助，但也常有旅客在到機(jī)場(chǎng)登記時(shí)才請(qǐng)求幫助.

航空公司面臨降低成本的壓力；輪椅昂貴且需要管理和維護(hù)；提供陪同人員需要費(fèi)用.

輪椅和陪同人員要不斷在機(jī)場(chǎng)移動(dòng)，花費(fèi)時(shí)間，輪椅需要有存放的地方.問(wèn)題背景

候機(jī)廳場(chǎng)地租費(fèi)昂貴而且有限，把輪椅留在客流繁忙的通道會(huì)妨礙行人通過(guò).

最大的代價(jià)之一是，如果某位旅客必須等候陪同人員的到來(lái)而導(dǎo)致飛機(jī)等他而延誤航班.

有可能影響到航空公司的平均航班延誤時(shí)間，其后果是有些潛在乘客會(huì)因此而避開(kāi)這個(gè)公司的航班，造成該航空公司機(jī)票銷售的減少.問(wèn)題背景Epsilon航空公司請(qǐng)為旅客提供輪椅和陪同人員服務(wù)的管理和維護(hù)問(wèn)題和成本進(jìn)行詳細(xì)的分析.

希望得到一個(gè)講求成本效益的輪椅調(diào)度方法，并找出和定義短期和長(zhǎng)期的預(yù)算規(guī)劃的各種成本.

形成一個(gè)投標(biāo)以幫助該航空公司解決問(wèn)題.

投標(biāo)應(yīng)包括對(duì)實(shí)際情況的概述和分析,以便這家公司能確定你們已經(jīng)完全了解他們的問(wèn)題.

提供算法的詳細(xì)敘述，該算法能確定輪椅和陪同人員應(yīng)安置在哪里及每天應(yīng)怎樣移動(dòng).

提供一個(gè)強(qiáng)有力的案例以說(shuō)明你們的解決方案是最佳的而且能夠處理各種環(huán)境下各種機(jī)場(chǎng)的問(wèn)題.問(wèn)題要求

投標(biāo)應(yīng)該包括該算法如何處理大型(至少4個(gè)候機(jī)大廳)、中型(至少2個(gè)候機(jī)大廳)和小型(1個(gè)候機(jī)大廳)機(jī)場(chǎng)在客流高峰和低谷時(shí)段的各種情況.

應(yīng)該確定所有潛在的成本并權(quán)衡它們各自的權(quán)重.

因?yàn)槔夏曷每驮诼每涂倲?shù)中開(kāi)始占有更大的比重，但也可能提出更多的幫助要求,所以你的報(bào)告還應(yīng)該包括對(duì)未來(lái)潛在成本和乘客需求的規(guī)劃,以及怎樣滿足未來(lái)需求的建議.問(wèn)題要求2007年8月4日攝于ChicagoO’Hare機(jī)場(chǎng)競(jìng)賽結(jié)果（共231隊(duì)）5名特等獎(jiǎng)（中國(guó)無(wú)）37名一等獎(jiǎng)（中國(guó)16名）56名二等獎(jiǎng)133名成功獎(jiǎng)SIAM獎(jiǎng)：HarvardUniversity“多候機(jī)廳機(jī)場(chǎng)中效益最大化的輪椅配置”INFORMS獎(jiǎng)(InstituteforOperationsResearchandManagementSciences)：MassachussettsInstituteofTechnology“最小費(fèi)用流在機(jī)場(chǎng)輪椅服務(wù)中的應(yīng)用”MAA獎(jiǎng)(MathematicalAssociationAmerica)：RiceUniversity“一個(gè)費(fèi)用-效益機(jī)場(chǎng)輪椅輔助服務(wù)的模擬-驅(qū)動(dòng)方法”HarvardUniversity“多候機(jī)廳機(jī)場(chǎng)中效益最大化的輪椅配置”（ProfitMaximizingAllocationofWheelchairsinaMulti-ConcourseAirport）

摘要為最小化Epsilon航空公司提供輪椅服務(wù)的費(fèi)用，考察顯費(fèi)用（輪椅和人員）與隱費(fèi)用（市場(chǎng)份額的損失）之間的折中。多候機(jī)廳機(jī)場(chǎng)模型模擬旅客、輪椅和陪同人員的相互關(guān)系。航空公司競(jìng)爭(zhēng)模型采用博弈論的觀點(diǎn)表述公司競(jìng)爭(zhēng)中追求利潤(rùn)的行為。為落實(shí)這些模型，綜合了大量的統(tǒng)計(jì)數(shù)據(jù)，并運(yùn)行了2005年西南航空公司來(lái)自3個(gè)機(jī)場(chǎng)的實(shí)例。結(jié)論是Epsilon公司應(yīng)采用每個(gè)候機(jī)廳設(shè)置輪椅港的”Hubandspokes”(中心和輻條)策略使輪椅的移動(dòng)規(guī)格化?？紤]不同大小的機(jī)場(chǎng)，發(fā)現(xiàn)每個(gè)候機(jī)廳2名陪同人員、每名陪同人員2只輪椅為最優(yōu)?；炯僭O(shè)

機(jī)場(chǎng)有1到10個(gè)候機(jī)廳，每個(gè)廳有2到50個(gè)登機(jī)門(mén)，廳之間的距離比廳內(nèi)門(mén)之間的距離大得多.2006年（模型運(yùn)行的開(kāi)始）需要輪椅的旅客的比例為1.6%（已知1996年為1.5%），這些旅客在飛機(jī)到達(dá)前通知機(jī)場(chǎng)需要輪椅的比例為95%。輪椅旅客失去轉(zhuǎn)機(jī)有兩種可能：飛機(jī)晚點(diǎn)到達(dá)（約1/3航班晚點(diǎn)，5%至少晚1小時(shí)）；陪同人員服務(wù)太慢（將盡力減少這種風(fēng)險(xiǎn)）.

陪同人員步行速度250ft/min（76m/min），推輪椅速度180ft/min（55m/min）;一名陪同人員只能推一輛輪椅，且在轉(zhuǎn)機(jī)前不能離開(kāi)輪椅旅客；陪同人員的年薪$40000，輪椅價(jià)格$135；對(duì)轉(zhuǎn)機(jī)旅客飛機(jī)最多等待15min.

輪椅服務(wù)雖不是法定的責(zé)任，但能提高市場(chǎng)競(jìng)爭(zhēng)份額，延誤轉(zhuǎn)機(jī)的旅客必須等待下一班飛機(jī).多候機(jī)廳機(jī)場(chǎng)模型MCAM（TheMulti-ConcourseAirportModel）控制變量：陪同人員與輪椅旅客比例E*，輪椅與輪椅旅客比例W*，陪同人員和輪椅的策略S,即（S,W*,E*）.參變量：輪椅旅客的比例b（=1.6%），天d（分高峰日、低峰日），年y（從2006年開(kāi)始，旅客數(shù)量變化），購(gòu)買(mǎi)輪椅費(fèi)用pW（=135），陪同人員費(fèi)用pE（=40000）.因變量：日費(fèi)用C，包括顯費(fèi)用（輪椅和人員）與隱費(fèi)用（延誤的損失）;一次延誤的損失D,包括轉(zhuǎn)機(jī)延誤及起飛延誤.用MonteCarlo模擬若干天，給出C，D的期望值，其結(jié)果作為f的代表.延誤與損失航空公司選擇飛機(jī)等待（走向登機(jī)門(mén)的）旅客的時(shí)間x*min，在等候旅客與被等候旅客之間尋求平衡以得到x*的最優(yōu)值.設(shè)短時(shí)等待造成的損失是線性的，即機(jī)上N=120位旅客等待15分鐘的利益損失為120

15=180分鐘.

一次延誤轉(zhuǎn)機(jī)的利益損失是Um

等候遲到旅客x*min，趕上轉(zhuǎn)機(jī)的概率是

等待時(shí)間的平均值是

按照經(jīng)驗(yàn)取x*=15，則平衡關(guān)系多候機(jī)廳機(jī)場(chǎng)模型MCAMAirportDayP(L≤15|L≥0)(%)E[T|0≤T≤15](min)MidlandLow-Delay31.55.0ColumbusLow-Delay23.26.9St.LouisLow-Delay19.88.5MidlandHigh-Delay25.92.5ColumbusHigh-Delay26.96.6St.LouisHigh-Delay26.37.7Average25.66.2取足夠的陪同人員與輪椅使需要的旅客立即得到，模擬等待遲到旅客15分鐘的結(jié)果延誤與損失多候機(jī)廳機(jī)場(chǎng)模型MCAMN=120,滿載率69.5%

一次延誤轉(zhuǎn)機(jī)的損失相當(dāng)于一位旅客等待1分鐘的2000倍.

靠近登機(jī)門(mén)的閑置的輪椅給旅客帶來(lái)不便，給公司帶來(lái)風(fēng)險(xiǎn)，設(shè)一只閑置的輪椅待一分鐘相當(dāng)一位旅客晚一分鐘損失的20%.

飛機(jī)起飛晚一分鐘造成的損失是NUm/2000=0.0005NUm

一只閑置的輪椅待一分鐘造成的損失是0.0001Um.延誤與損失多候機(jī)廳機(jī)場(chǎng)模型MCAM多候機(jī)廳機(jī)場(chǎng)模型MCAM陪同人員和輪椅的策略S隨機(jī)策略輪椅旅客到達(dá)后，被隨機(jī)選擇的空閑陪同人員送到登機(jī)門(mén)，陪同人員和輪椅等在門(mén)邊直到下一位輪椅旅客.智能策略機(jī)場(chǎng)預(yù)先得到多數(shù)輪椅旅客的信息，陪同人員和門(mén)旁的工作人員都有名單,名單中的旅客到達(dá)時(shí)陪同人員等在門(mén)旁,不在名單中的旅客到達(dá)時(shí)工作人員用傳呼機(jī)通知最近的空閑陪同人員，后者用傳呼機(jī)找到能用的最近的輪椅.

直接運(yùn)送運(yùn)送輪椅旅客后陪同人員和輪椅留在原處，等待下一個(gè)輪椅旅客，得到傳呼后陪同人員尋找離那個(gè)輪椅旅客到達(dá)的門(mén)最近的輪椅。輪椅分布在各個(gè)門(mén)旁，一些門(mén)附近有閑置的輪椅.

中心和輻條(HubandSpokes)

每個(gè)廳設(shè)一個(gè)貯存輪椅的輪椅港，陪同人員運(yùn)送輪椅旅客后將輪椅放在這個(gè)廳的港中.多候機(jī)廳機(jī)場(chǎng)模型MCAM長(zhǎng)期模擬(40年)時(shí)的參數(shù)變化人口年齡結(jié)構(gòu)2000年60歲以上的占1/6，60歲以上需要輪椅的是60歲以下的13倍，輪椅旅客中72%在60歲以上.20年內(nèi)65歲以上人口將增長(zhǎng)40%，2006年旅客有1.6%需要輪椅，假定老年人口與輪椅旅客同比例增長(zhǎng)，計(jì)算未來(lái)輪椅旅客的數(shù)量.邊際效益降低

由于燃油價(jià)格提高，公司面臨邊際效益的降低，在模擬長(zhǎng)期運(yùn)行時(shí)采用比短期較小的邊際效益.航空公司競(jìng)爭(zhēng)模型ACM（TheAirlineCompetitionModel)

對(duì)基于旅客滿意度的公司市場(chǎng)份額建模并給出利潤(rùn)函數(shù)，將失去未來(lái)市場(chǎng)作為費(fèi)用，則利潤(rùn)最大等價(jià)于費(fèi)用最小.ACM利用MCAM的輸出來(lái)確定若干公司的市場(chǎng)份額和利潤(rùn).航空公司競(jìng)爭(zhēng)模型ACM市場(chǎng)份額

公司營(yíng)業(yè)在一個(gè)機(jī)場(chǎng)的市場(chǎng)中占的比例.

經(jīng)歷了起飛延遲或由于輪椅原因而延誤轉(zhuǎn)機(jī)后,輪椅旅客和非輪椅旅客都可能離開(kāi)本公司而轉(zhuǎn)向(defectto)其他公司.

將這種轉(zhuǎn)向作為總損失的函數(shù).設(shè)有m家公司，Nt(i)為公司i時(shí)段t的市場(chǎng)份額，ft(i)為時(shí)段t末離開(kāi)公司i的旅客比例，且離開(kāi)一家公司的旅客等概率地轉(zhuǎn)向其他公司.短時(shí)期內(nèi)可認(rèn)為Ft不隨時(shí)間變化航空公司競(jìng)爭(zhēng)模型ACM市場(chǎng)份額旅客轉(zhuǎn)向航空公司競(jìng)爭(zhēng)模型ACM

基于利潤(rùn)的模型應(yīng)該尋找接待輪椅旅客的費(fèi)用與不提供輪椅而失去市場(chǎng)份額的折中.

公司提供較少的服務(wù)，對(duì)市場(chǎng)份額的影響短期不會(huì)出現(xiàn).

從長(zhǎng)期看服務(wù)較差的公司的市場(chǎng)份額將受損.

短期運(yùn)行費(fèi)用包括購(gòu)買(mǎi)輪椅的固定費(fèi)用，而長(zhǎng)期運(yùn)行費(fèi)用中輪椅的管理和更換費(fèi)用較小.利潤(rùn)函數(shù)將只考慮輪椅分配策略帶來(lái)的利潤(rùn)增加或減少.ft(ij)為類型j的一天t離開(kāi)公司i的旅客比例,1-ft(ij)為保留率.MCAM中給定（S,W*,E*）

模擬旅客的總損失得到ft(ij)，給出隨機(jī)變量gt(ij)=log(1-ft(ij)),得到gt(ij)的均值和方差

一年的總保留率按照中心極限定理當(dāng)Vj充分大時(shí)設(shè)有J種飛行日(高延誤;低延誤),類型j的飛行日一年有Vj天.西南航空公司2005年3個(gè)機(jī)場(chǎng)的延誤數(shù)據(jù):高延誤約10%(35天),低延誤(330天),載客率分別為100%和66%(平均69.5%).旅客轉(zhuǎn)向航空公司競(jìng)爭(zhēng)模型ACM利潤(rùn)模型保持所有因素為常數(shù)，于是輪椅旅客耽誤一次轉(zhuǎn)機(jī)只是輪椅策略的原因.假定輪椅旅客耽誤一次轉(zhuǎn)機(jī)導(dǎo)致離開(kāi)該公司的概率為pd=1/4t天公司i在市場(chǎng)份額中有旅客nt(i)=PtNt(i)（Pt是旅客總數(shù)）

輪椅旅客耽誤n次轉(zhuǎn)機(jī)導(dǎo)致離開(kāi)該公司的概率為1-(1-pd)n

設(shè)損失Dt對(duì)旅客均勻分布，每位旅客損失ut=Dt/nt(i),即一次耽誤轉(zhuǎn)機(jī)的損失Um

輪椅旅客耽誤轉(zhuǎn)機(jī)的損失導(dǎo)致離開(kāi)該公司的概率為旅客轉(zhuǎn)向航空公司競(jìng)爭(zhēng)模型ACM利潤(rùn)函數(shù)航空公司競(jìng)爭(zhēng)模型ACM

l~每位旅客的利潤(rùn)，Wt~t年輪椅數(shù)，Rt~t年更換輪椅數(shù)（每年更換20%），Et~t年陪同人員數(shù)，pW~購(gòu)買(mǎi)輪椅費(fèi)用，pR~維護(hù)輪椅費(fèi)用，pE~陪同人員薪金

.按照輪椅最優(yōu)比例W*，t+1年的(目標(biāo))輪椅數(shù)為W*PtNt(i)，t+1年的陪同人員數(shù)為E*PtNt(i)，又設(shè)不能扔掉好的輪椅.

公司i第t年的實(shí)際利潤(rùn)（對(duì)貶值調(diào)整后）為Qt(i)

航空公司競(jìng)爭(zhēng)模型ACM利潤(rùn)現(xiàn)值設(shè)公司的費(fèi)用和利潤(rùn)以年率rc（=2%）增長(zhǎng)，銀行利率為rd（=4.5%）.

折扣因子δ=(1-rc+rd)-1=1/1.025≈0.975T（=40年）公司的利潤(rùn)現(xiàn)值為模擬實(shí)現(xiàn)航空公司競(jìng)爭(zhēng)模型ACMACM的計(jì)算機(jī)模擬依于MCAM的結(jié)果

對(duì)m家公司按照不同的策略（S,W*,E*）估計(jì)一年的總費(fèi)用和總損失.

第1年ACM模擬公司i的運(yùn)行（1年策略不變并作為MCAM的輸入），其中35天高延誤和330天低延誤.

第1年給各公司相同的份額,確定市場(chǎng)份額的改變,利用改變的份額對(duì)t年計(jì)算每個(gè)公司的利潤(rùn)

模擬40年，給出每個(gè)公司每年的利潤(rùn)，考慮折扣后比較由不同策略（S,W*,E*）產(chǎn)生的現(xiàn)值，判斷哪個(gè)策略是最有吸引力的.實(shí)例研究西南航空公司2005年利潤(rùn)$313(million),旅客70.9(million),每位旅客利潤(rùn)$4.41(估計(jì)被輪椅和陪同人員的費(fèi)用減少了$0.10).用3個(gè)機(jī)場(chǎng)(MidlandTX,ColumbusOH,St.LouisMO)的數(shù)據(jù)MCAM（S,W*,E*）3種策略S:隨機(jī)策略,直接運(yùn)送,HubandSpokes陪同人員/輪椅配置:陪同人員5,輪椅5,10,20;

陪同人員10,輪椅205位陪同人員對(duì)低延誤和高延誤各策略的損失相同，而10位陪同人員高延誤比低延誤的損失平均多40.解釋：5位陪同人員低延誤和高延誤都在忙，而10位陪同人員低延誤時(shí)可應(yīng)付全部輪椅旅客，高延誤時(shí)則會(huì)有誤機(jī)發(fā)生.結(jié)果與分析

隨機(jī)策略與直接運(yùn)送對(duì)所有陪同人員和輪椅配置及低延誤和高延誤執(zhí)行結(jié)果差不多.解釋:兩種策略的輪椅分布差不多.解釋:它涉及輪椅的移動(dòng)，需要足夠多的人員.

5位陪同人員時(shí)中心和輻條策略比其他兩種策略好不多，但10位陪同人員時(shí)則要好得多.ACM

3種策略和4種人員和輪椅配置,計(jì)算市場(chǎng)份額和最終利潤(rùn)中心和輻條策略，10位陪同人員配20只輪椅，2046年的市場(chǎng)份額最高（11.1%），利潤(rùn)也最高（106vs.101.9）.而5位陪同人員配20只輪椅，2046年的市場(chǎng)份額最低（7.2%），因?yàn)樵摬呗孕枰藛T把輪椅放到港里.實(shí)例研究MCAM（S,W*,E*）結(jié)果與分析優(yōu)點(diǎn)

用包括2005年365天飛機(jī)延誤的實(shí)際數(shù)據(jù)運(yùn)行輪椅策略,計(jì)算市場(chǎng)份額和利潤(rùn).從長(zhǎng)期看也適合輪椅旅客比例變化的情況。

把旅客的總損失轉(zhuǎn)化為轉(zhuǎn)向率,反映競(jìng)爭(zhēng)市場(chǎng)中服務(wù)質(zhì)量的影響

結(jié)果給出費(fèi)用與市場(chǎng)份額得失之間平衡的長(zhǎng)期和短期影響。缺點(diǎn)旅客的增長(zhǎng)取決于多種因素,這可能改變結(jié)果的數(shù)值結(jié)論

使用中心和輻條策略，每個(gè)廳2名陪同人員，每位陪同人員2只輪椅,使市場(chǎng)份額和長(zhǎng)期利潤(rùn)達(dá)到最大。這個(gè)建議對(duì)于獲得更高的利潤(rùn)是一個(gè)快速、有效的方案.模型的分析RiceUniversity“一個(gè)費(fèi)用-效益機(jī)場(chǎng)輪椅輔助服務(wù)的模擬-驅(qū)動(dòng)方法”(ASimulation-DrivenApproachforaCost-EfficientAirportWheelchairsAssistanceService)摘要雖然美國(guó)人口中依賴輪椅估計(jì)只約占0.6%，可是在旅行人流中機(jī)場(chǎng)里需要輪椅的是這個(gè)數(shù)值的兩倍多。對(duì)輪椅服務(wù)的費(fèi)用和效率有重大影響的是輪椅數(shù)量及怎樣配置，如果陪同人員自己決定他們?cè)跈C(jī)場(chǎng)里的行動(dòng)，缺少關(guān)于他們位置的信息會(huì)導(dǎo)致有照顧不到的地方，需求的波動(dòng)又如此之大，基于區(qū)域的計(jì)劃會(huì)使有些陪同人員超負(fù)荷工作，有些又無(wú)工作可做。本文提出的關(guān)于陪同人員時(shí)間表的算法,既可以簡(jiǎn)單地實(shí)現(xiàn)，又在充分利用每個(gè)陪同人員的工作時(shí)間上是有效的。在給出該算法的實(shí)現(xiàn)之后，在一個(gè)機(jī)場(chǎng)模擬了滿足需求的時(shí)間表，找出使費(fèi)用達(dá)到最小的輪椅/陪同人員數(shù)量。

預(yù)模擬：產(chǎn)生模擬所必需的輸入，如機(jī)場(chǎng)配置、一天中輪椅旅客的需求列表.

模擬：旅客到達(dá)/離開(kāi)及輪椅/陪同人員移動(dòng)的連續(xù)事件模型.

優(yōu)化：確定陪同人員數(shù)量使費(fèi)用最小.假設(shè)與模型建立隨機(jī)的模擬-驅(qū)動(dòng)優(yōu)化程序，將問(wèn)題分為3部分：預(yù)模擬、模擬和優(yōu)化.需求列表按照一定分布產(chǎn)生一天(從6Am到10Pm)的航班時(shí)刻表，每個(gè)航班平均125位旅客;按照0.6~1.2%的比例產(chǎn)生輪椅需求，每個(gè)需求賦予到達(dá)和離開(kāi)的航班，假定停留時(shí)間不小于半小時(shí);設(shè)有一定比例旅客提前通知了輪椅需求，其需求時(shí)間設(shè)為0，其余的在到達(dá)前多于5小時(shí)至半小時(shí)產(chǎn)生隨機(jī)需求;調(diào)度員有每天的旅客需求單,模擬中每天改變旅客需求單，并注意在高峰時(shí)間需求比較集中;需求的頻率在節(jié)假日要增加。預(yù)模擬機(jī)場(chǎng)配置機(jī)場(chǎng)為有向圖，節(jié)點(diǎn)是可出入的門(mén)，邊是通道(候機(jī)廳的主路);人行速度3mph(80m/mim),任意兩門(mén)i,j之間行走最短時(shí)間為dij，記矩陣D={dij};陪同人員知道D.輪椅和陪同人員一輪椅及其陪同人員作為一個(gè)單元(下稱陪同人員);為防備失靈而附加的輪椅合并到輪椅運(yùn)轉(zhuǎn)的維護(hù)費(fèi)中;設(shè)陪同人員在一天的模擬中為常數(shù).陪同人員與調(diào)度員用步話機(jī)聯(lián)系,調(diào)度員有每個(gè)陪同人員的時(shí)間表,陪同人員在完成任務(wù)后通知調(diào)度員;調(diào)度員在一天的不同時(shí)間接到的需求信息包括：旅客到達(dá)時(shí)間和位置ta,a,離開(kāi)時(shí)間和位置td,d，為使旅客按時(shí)離開(kāi)，陪同人員必須在tf=td-dad前到達(dá)a.調(diào)度員要從空閑的陪同人員中選一個(gè)，以最優(yōu)的方法完成任務(wù)。時(shí)間表最壞情況陪同人員在點(diǎn)e完成前一任務(wù)的時(shí)間te滿足te+dea<tf+dw，其中dw是因旅客晚到使飛機(jī)推遲起飛的“窗口”,這樣的陪同人員歸入集O1.較好情況陪同人員可以按時(shí)完成任務(wù)，但要從他的時(shí)間表中移去一個(gè)需求，滿足te+dea<tf（沒(méi)有延遲dw），這樣的陪同人員歸入集O2.時(shí)間表更好情況陪同人員可以按時(shí)完成任務(wù)，只需將以后任務(wù)的完成時(shí)間后推而不會(huì)有任何起飛延遲，這樣的陪同人員歸入集O3理想情況調(diào)度員安排陪同人員完成一個(gè)需求，不需要改變陪同人員以后的時(shí)間表，若下一任務(wù)s開(kāi)始時(shí)間是ts，則需te+des<ts，這樣的陪同人員歸入集O4對(duì)新的需求調(diào)度員從以上的集合中確定最優(yōu)的，并選擇離該需求的旅客到達(dá)位置最近的陪同人員。若新需求破壞了已排隊(duì)的需求，則必須在調(diào)度員移動(dòng)名單上下一需求之前重排時(shí)間表.若一個(gè)需求不能安排（陪同人員不空閑或不能按時(shí)到達(dá)）,則旅客將被安排下一航班，得到誤機(jī)補(bǔ)償，離開(kāi)本程序.模擬算法化為“裝箱問(wèn)題”——調(diào)度員把盡可能多的任務(wù)放到陪同人員的時(shí)間表中.Algorithm:MainSimulation(D,R,NE)createescorttaskarrayEI=FindIndexUnfulfilledRequest(R)whileI>0Do

O=MakeOptimalityMat(D,RI,E)comment:Nowexecuterequest(R,E)=ExecuteRequest(D,R,E,I,O)I=FindIndexUnfulfilledRequest(R)totalmissed=Sum(Rmissedflights)totaldelay=Sum(delaytime)return(totalmissed,totaldelay)D~最短時(shí)間矩陣R~需求列表NE~陪同人員數(shù)量Ej~陪同人員j的時(shí)間表MOM~NE

4矩陣,Oij=0,1,表示陪同人員i在優(yōu)性集OjER安排陪同人員

MOM,ER確定哪一個(gè)陪同人員最適合完成當(dāng)前的需求，及他當(dāng)前的時(shí)間表怎樣改變?nèi)ミm應(yīng)新的需求.Algorithm:OptimalityCheck(D,RI,ej

)initializeOj=(0,0,0,0)ifEscortjisGroup1Optimal(canfulfillRI

withdelay)thenOj,1

=1ifEscortjisGroup2Optimal(canfulfillRI

w/odelay)thenOj,2=1ifEscortjisGroup3Optimal(canfulfillRI

w/oremovingtasks)thenOj,3=1ifEscortjisGroup4Optimal(canfulfillRI

w/oshiftingtasks)thenOj,4

=1return(Oj)模擬算法MOM(NE

4矩陣)的每一行由OC產(chǎn)生最壞情況較好情況更好情況理想情況Algorithm:ExecuteRequest(D,R,E,I,M)ifcolumn4ofOcontainsa1thenFindescortwithclosestprevioustaske?Inserttaskintoscheduleofe?MarkrequestRIasfulfilledelseifcolumn3ofOcontainsa1thenFindescortwithclosestprevioustaske?

DetermineinsertionspotsfortaskMovejobsaftersbackfarthestpossibleInserttaskintoscheduleofe?MarkrequestRI

asfulfilled

Movejobsaftersforwardfarthestpossible模擬算法ER安排陪同人員

先將s后的任務(wù)后推理想情況更好情況再將s后的任務(wù)前移模擬算法ER安排陪同人員

elseifcolumn2ofOcontainsa1thenFindescortwithclosestprevioustaske?DetermineinsertionspotsfortaskMovejobsaftersbackfarthestpossibleInserttaskintoscheduleofe?MarkrequestRI

asfulfilledRemoveoverlappingtasksinscheduleMarkcorrespondingrequestsasunfulfilledMoveremainingjobsaftersforwardfarthestpossible移去一個(gè)任務(wù)需求較好情況需求未完成模擬算法ER安排陪同人員

elseifcolumn1ofOcontainsa1thenFindescortwithclosestprevioustaske?DetermineinsertionspotswithminimumdelayMovejobsaftersbackfarthestpossibleInserttaskintoscheduleofe?MarkrequestRIasfulfilledRemoveoverlappingtasksinscheduleMarkcorrespondingrequestsasunfulfilledMoveremainingjobsaftersforwardfarthestpossible

LogdelayofRIelse

MarktaskasfulfilledLogRIasmissedflightreturn(E,R)需求延誤記錄目標(biāo)函數(shù)[X,Y]=

MainSimulation(D,R,NE)C(X,Y)=Cost(A)+Cost(X)+Cost(Y)調(diào)度計(jì)劃費(fèi)用:輪椅和陪同人員費(fèi)用（在一天的模擬中固定為A）;誤機(jī)旅客費(fèi)用;延遲起飛費(fèi)用（占據(jù)登機(jī)門(mén)）.X~誤機(jī)(人)數(shù)，Y~延遲起飛時(shí)間設(shè)每只輪椅費(fèi)用$130/年，陪同人員費(fèi)用$10/小時(shí)，Cost(A)=（10+130/365/24）hNE(h是模擬時(shí)間).誤機(jī)旅客$500/人（票價(jià)補(bǔ)償?shù)龋?，延遲起飛$1018/小時(shí)每個(gè)數(shù)據(jù)點(diǎn)做10次試驗(yàn)誤差限為一個(gè)標(biāo)準(zhǔn)差所有需求的一半是提前知道的結(jié)果與分析最優(yōu)時(shí)間表驗(yàn)證自適應(yīng)時(shí)間表的有效性Epsilon公司可能節(jié)約$10000/天.在優(yōu)性集O1,O2,O3中移動(dòng)陪同人員:最簡(jiǎn)算法~若O4中無(wú)人,需求失敗;次簡(jiǎn)算法~若O4，O3中無(wú)人，需求失敗.當(dāng)包含優(yōu)性集O3時(shí)有實(shí)質(zhì)的效果：避免雇傭5或6個(gè)陪同人員，節(jié)約$1000/天.模擬一個(gè)小候機(jī)廳,運(yùn)量中等(15000旅客/天),1.2%輪椅需求.對(duì)候機(jī)廳的性能和敏感性分析用ChicagoO’Hare機(jī)場(chǎng)檢查不同大小規(guī)模的性能對(duì)1個(gè),2個(gè),4個(gè)候機(jī)廳進(jìn)行模擬,旅客數(shù)設(shè)置3個(gè)水平,0.6%輪椅需求.用ChicagoO’Hare機(jī)場(chǎng)檢查不同大小規(guī)模的性能陪同人員數(shù)陪同人員數(shù)每天費(fèi)用1個(gè)廳陪同人員花費(fèi)時(shí)間比例對(duì)1個(gè)廳旅客數(shù)增加,最優(yōu)陪同人員數(shù)幾乎不變4個(gè)廳2個(gè)廳對(duì)2個(gè),4個(gè)廳最優(yōu)陪同人員數(shù)有明顯增加最優(yōu)陪同人員數(shù)大致與候機(jī)廳數(shù)成比例3個(gè)機(jī)場(chǎng)的比較分析:NewYork’sLaGuardia(LGA),ChicagoO’Hare(ORD),Dallas/FortWorth(DFW)，旅客數(shù)設(shè)置2個(gè)水平,1.2%輪椅需求.對(duì)機(jī)場(chǎng)的性能和敏感性分析從衛(wèi)星圖象可知3個(gè)機(jī)場(chǎng)的不同,行走距離DFW最長(zhǎng),ORD最短.算法性能沒(méi)有明顯差別人口總數(shù)增加與輪椅需求增加不完全一樣,人口總數(shù)增加10%導(dǎo)致每天的航班增加,輪椅需求增加10%則不會(huì)，即隨著旅客平均年齡增長(zhǎng)，不僅總需求增加，而且每架飛機(jī)上需求增加.老年