（1)每一個航班必須指派且僅能指派一個停機(jī)位即式中,，W表示指派周期開始時已在位航班的集合,，同時也表示在位航班?？康耐? 機(jī)位的集合，對于航班iEM可以將W分成兩個子集,，一個是航班i進(jìn)港時仍然在 位的航班集合：W1(2)={k|D>A,，kEW)，D,，和A,，分別是航班k的出發(fā)和航班 i的到達(dá)時刻,；另一個是航班i進(jìn)港時已出發(fā)的子集W2。并且使用0-1型參數(shù)yw 表示使用機(jī)位的信息,，在指派周期開始時,，當(dāng)航班kEW停靠機(jī)位p時等于1,，否 則等于0,。要記住，,。是已知參數(shù),。約束條件（2-91）表示當(dāng)航班i進(jìn)港時，仍然被 占用的停機(jī)位p不能分配給航班i,，如果W為空,，則約束條件(2-91）也將為空。約 束條件(2-92）表示在指派周期開始時已經(jīng)空閑的機(jī)位最多可指派給一個航班,。
（2）停機(jī)位類型與機(jī)型的匹配約束 式中,，P。和L,，分別表示停機(jī)位p的類型和航班i的機(jī)型,，該約束表示機(jī)位類型可 向下兼容，這一點與2.7.1節(jié)和2.7.2節(jié)相同,。如果在航班波運作，給航班波指派 的機(jī)位不受機(jī)型限制,，可以略去這一約束條件,。 上述停機(jī)位指派問題是二次指派問題，是非線性的,。為降低非線性帶來的求 解困難,，可以將目標(biāo)函數(shù)轉(zhuǎn)化為線性的。為此引人新的決策變量yg=xpxm,，目 標(biāo)函數(shù)（2-89）變?yōu)? 引人新變量后,，目標(biāo)函數(shù)（2-94)已轉(zhuǎn)化為線性的，為保證新的線性整數(shù)規(guī)劃 與原非線性整數(shù)規(guī)劃等價,，應(yīng)滿足以下條件： 此時需要增加以下等價約束條件： 上述停機(jī)位指派問題可以直接用ILOG/CPLEX求解,，但求解時間較長，對于 稍大規(guī)模的問題（如一個航班波的航班數(shù)超過10個),，它幾乎不能完成求解任務(wù),。
此時需要設(shè)計宏啟發(fā)式算法，如模擬退火法,、遺傳算法等,。下面介紹一個應(yīng)用模擬 退火法求解上述問題的實例,。 解陳欣(207）詳細(xì)研究了這個問題的求解。將表2-20與表2-21的對應(yīng)數(shù) 據(jù)相乘然后代人目標(biāo)函數(shù)（2-89）或（2-94),，即構(gòu)成本問題的目標(biāo)函數(shù),，W是空集目 停機(jī)位無機(jī)型限制，因此不需要約束條件(2-91）和(2-93),，式(2-90）和式（2-92）是 最基本的約束條件,，很容易構(gòu)成。為節(jié)省篇幅,，這里不再給出該停機(jī)位指派問題數(shù) 學(xué)模型的細(xì)節(jié),。 如果采用目標(biāo)函數(shù)(2-89），應(yīng)用ILOG/CPLEX在一般臺式計算機(jī)上求解本 問題,，超過10h也不能給出結(jié)果,，將問題規(guī)模縮小到8個航班,，應(yīng)用非線性模型和 線性模型,，在同一臺計算機(jī)上分別花費了2h和22min才解出結(jié)果，線性模型的求解速度顯然快了不少,。但增加一個航班,，即9個航班時，線性模型的求解時間也增 加到6h,，其計算復(fù)雜度是指數(shù)型的,，而非線性模型則計算了10h仍然沒有結(jié)果。
如果采用啟發(fā)式算法,，如模擬退火法,，在同一臺計算機(jī)上求解該問題（10個航 班）則只需0.3s即可給出結(jié)果，收斂速度很快,。為了了解模擬退火法求解結(jié)果的精度,，這里對一個航班波中有8個航班、9個航班和10個航班的三種情況應(yīng)用模 擬退火法進(jìn)行求解,，發(fā)現(xiàn)在前兩種情況下,，模擬退火法給出了與ILOG/CPLEX求 解線性模型相同的結(jié)果，第三種情況下模擬退火法很快給出結(jié)果,，但I(xiàn)LOG/ CPLEX則未能給出結(jié)果,。表2-22給出了三種情況下模擬退火法求解得到的停機(jī)位最佳指派結(jié)果，表中F表示第i個航班,。計算中,，限制8個航班和9個航班的航班波只分別使用1~8號和1~9號停機(jī)位。
進(jìn)一步研究發(fā)現(xiàn),，即使一個航班波到達(dá)25個航班,，使用模擬退火法求解航班波停機(jī)位指派問題,，計算時間也只有123s，可見模擬退火法求解這類問題具有很 高的效率,，達(dá)到了實用化的程度,。 這個實例分析表明，非線性的整數(shù)規(guī)劃問題,，目前沒有好的精確解法,，采用啟發(fā)式算法，是可行且適用的,。
