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

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

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

初始解的構造 

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

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