對稱型旅行商問題在工程運輸中的應用

胡凱超

(江蘇科技大學工程管理系，江蘇 鎮(zhèn)江 212003)

0 前 言

旅行商問題(Traveling Saleman Problem，TSP)是VRP的特例，由于Gaery已證明TSP問題是NP難題，是指一名推銷員要拜訪多個地點時，如何找到在拜訪每個地TSP問題點一次后再回到起點的最短路徑。規(guī)則非常容易了解，也貼近人們的生活，但是當要參加的目的地變多時，難度就會急劇增大。本文所列的為30個地方，如果要列舉所有路徑后再確定最佳行程，那么統(tǒng)計工作量之大，幾乎不可能做完。多年來，全球數(shù)學家絞盡腦汁，試圖找到一個高效的算法，近來在大型計算機的幫助下才取得了一些進展。

“旅行商問題”的應用領域包括：如何規(guī)劃最合理高效的道路交通，以減少擁堵；如何更好的規(guī)劃物流，以減少運輸成本等[1]。在工程項目中，由于建筑中物資一般會儲存在偏遠地區(qū)以降低成本，故對于物資的運輸規(guī)劃有著非常高的要求，此時對于“旅行商問題”的求解對于提高企業(yè)經(jīng)濟效益，加快工程進度具有重要意義。

1 問題的引入

一個工廠將產(chǎn)品運送到各個不同的地點，已知城市個數(shù)和各地點之間的路程，要求找到從某一個地點出發(fā)，經(jīng)過所有地點并且每個地點只能被訪問一次，最后回到起始點，使總路程最小。以工廠為原點的坐標系，每個運輸點的位置相對坐標見表1。

表1 各運輸點的位置坐標

因為任意兩個工地的往返的距離都是相同的，所以該問題是對稱型的，比非對稱型的旅行商問題容易一些，不過其最優(yōu)解的求解過程依然不是一個容易的過程。一般而言，對于旅行地數(shù)目較少的TSP問題，可以利用動態(tài)規(guī)劃方法和枚舉法手動求出最優(yōu)解這兩種方法顯得有些無能為力，通常采用啟發(fā)式算法式算法借助計算機求其較好的解，比如蟻群算法[2]、基于遺傳算法的粒子群算法等。

2 數(shù)學模型

螞蟻k(k=1,2...m)在運動過程中，運動轉(zhuǎn)移的方向由各條路徑上的信息量濃度決定。為方便記錄可用tabuk(k=1,2...m)來記錄第k只螞蟻當前已走過的所有節(jié)點，這里可以稱存放節(jié)點的表為禁忌表；且該集合會隨著螞蟻的運動狀態(tài)進行調(diào)整。在算法的搜索過程中，螞蟻會智能地選擇下一步所要走的路徑。

設m表示螞蟻的總數(shù)量，用dij(i,j=0,1...n-1)表示節(jié)點i與節(jié)點j之間的距離，τij(t)表示在t刻ij連線上的信息素濃度。在初始時刻，各個位置的信息素濃度是相同的，在t時刻，螞蟻k從i節(jié)點轉(zhuǎn)移到j節(jié)點的狀態(tài)轉(zhuǎn)移概率為：

在螞蟻運動過程中，為了避免在路上殘留過多的信息素而使啟發(fā)信息被淹沒，每只螞蟻在遍歷完成后，要對殘留信息進行更新處理。由此，在t+n時刻，路徑(i,j)上的信息調(diào)整如下：

蟻群算法流程見圖1。

圖1 蟻群算法流程

禁忌表：與真實的螞蟻不同，人工蟻群系統(tǒng)具有記憶功能。為了滿足螞蟻必須經(jīng)過所有12個不同的工地這一約束條件，為每只螞蟻都設計了數(shù)據(jù)結(jié)構(gòu)，成為禁忌表。用來記錄t時刻螞蟻已經(jīng)經(jīng)過的工地，不允許該螞蟻本次循環(huán)中在經(jīng)過改工地，當本次循環(huán)結(jié)束后，禁忌表被用來計算改螞蟻所建立的解決方案。之后禁忌表清空螞蟻又可以自由地選擇方案。

運行結(jié)果見圖2～3。運輸?shù)南群箜樞蛞姳?。

圖2 運算結(jié)果(1)

圖3 運算結(jié)果(2)

表2 運輸?shù)南群箜樞?/p>

由此可見，最短路線長為428.959 2。

3 結(jié)束語

本文中通過蟻群算法對于工程項目中常遇到的旅行商問題進行了研究，案例中共涉及30個施工場地坐標，雖然是對稱型的旅行商問題，但30個點的情況下依然是非常復雜的，案例表明，蟻群算法對于處理此種類型的問題具有求解速度快、答案準確的特點。

[ID:009805]