采用的是枚舉法，要計算CiM1個(gè)多源多匯的最短路問(wèn)題，在網(wǎng)絡(luò )規 模比較大時(shí)，計算時(shí)間還比較長(cháng)，所以采用了三下標模型。本節以四下標亞馬遜頭程網(wǎng)絡(luò )模型為求解對象，討論一種啟發(fā)式算法—禁忌搜索算法，以期減少計算量，縮短計算時(shí)間。禁忌搜索算法是Glover于1986年提出的一種現代啟發(fā)式算法，它是對局部搜索算法的一種擴展，試圖做到全局逐步尋優(yōu)。

      搜索算法通過(guò)引入一個(gè)靈活的存儲結構和相應的禁忌準則來(lái)避免迂回搜索，通過(guò)特赦準則來(lái)赦免一些被禁 忌的優(yōu)良狀態(tài)，且當前解還可以通過(guò)一定方式接受劣解，從而保證多樣化的有效探索，以求FBA頭程運輸實(shí)現全局優(yōu)化。關(guān)于禁忌搜索算法的詳細論述可參閱相關(guān)文獻(Glover and Laguna,1997),這里結合網(wǎng)絡(luò )優(yōu)化中的最短路算法，利用禁忌搜索算法的優(yōu)良特性，設計一種解決四下標UMpHMP的啟發(fā)式方法—TSSPA算法。 在無(wú)容量限制的航線(xiàn)網(wǎng)絡(luò )中，任一O-D對需求都將沿著(zhù)一條運費最少的路線(xiàn) 運輸，因此UMpHMP最優(yōu)解中決策變量xm的值只能取0或1。另外，當樞紐選 定后，各城市間的連接方式可以通過(guò)求所有O-D對間的最短路問(wèn)題解決。

      基于UMpHMP的這些特點(diǎn)，這里將把禁忌搜索算法和最短路算法相結合，求解 UMpHMP網(wǎng)絡(luò )優(yōu)化模型。也就是，采用禁忌搜索算法選取樞紐，再利用亞馬遜物流最短路算法決定各O-D對之間的運輸路線(xiàn)，經(jīng)過(guò)禁忌搜索算法的反復迭代，亞馬遜頭程以得到問(wèn)題最優(yōu)解或較優(yōu)解。這里把這種算法命名為T(mén)SSPA算法。 

初始解的構造 

       TSSPA算法和其他禁忌搜索算法一樣，對初始解具有依賴(lài)性。好的初始解可 使算法在解空間中高效地搜索到最優(yōu)解，而較差的初始解則會(huì )降低算法的收斂速度。本節借助UMpHMP的信息來(lái)構造初始解。樞紐的選取與流量和成本都有 關(guān)系，因此在選取初始解的樞紐時(shí)用指標： 對各候選樞紐機場(chǎng)排序，選擇值最大的p個(gè)機場(chǎng)作為初始樞紐，然后對選定的p個(gè)樞紐，利用最短路算法求出各城市對間的最短路線(xiàn)，由此得到初始解。

      由于只在p個(gè)樞紐城市進(jìn)行轉運操作，當航空運輸成本滿(mǎn)足三角形三條邊長(cháng)之間的關(guān)系時(shí)，亞馬遜頭程可以利用Floyd最短路算法進(jìn)行求解，只需迭代p次即可。算法步驟如下。 假設樞紐集為H={h1，he…，hp}，構造圖G'=（N’，A'）。G'中每條邊的長(cháng) 度s（s）定義為：當i、j旺H時(shí)，g（s)=+o；當、jEH時(shí)，ls(s)=aC；(s);當iE H、j旺H時(shí)，LG（s)==6C（s)；當itH、jEH時(shí)，5(8)=XC；（s)。令d（s)表示只 有前k≤p個(gè)樞紐作為中轉點(diǎn)時(shí)從點(diǎn)i到點(diǎn)j的最短路長(cháng)度，用序（s）記錄從點(diǎn)i 到點(diǎn)j最短路徑上的第一個(gè)不同于i的點(diǎn)。這里的s表示需求和成本預測的時(shí)間 周期。 步驟1令d8(8)=lj(s)，d8(s）=0，r號（s）=j，i，j=1，2…,n,k=1。 步驟2對一切1