對稱型旅行商問題在工程運(yùn)輸中的應(yīng)用

胡凱超

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

0 前 言

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

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

1 問題的引入

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

表1 各運(yùn)輸點(diǎn)的位置坐標(biāo)

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

2 數(shù)學(xué)模型

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

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

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

蟻群算法流程見圖1。

圖1 蟻群算法流程

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

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

圖2 運(yùn)算結(jié)果(1)

圖3 運(yùn)算結(jié)果(2)

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

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

3 結(jié)束語

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

[ID:009805]