蟻群算法求解帶有時間約束旅行商問題

李安穎,陳 群,宋 荷

(西北工業(yè)大學(xué)計算機學(xué)院,陜西 西安 710072)

0 引言

隨著線上線下(online to offline，O2O)商業(yè)模式發(fā)展迅速，對物流配送的要求越來越高。物流配送已成為O2O服務(wù)中的一個重要環(huán)節(jié)[1]，其服務(wù)質(zhì)量對提高O2O企業(yè)的競爭力具有重要意義。當前，物流企業(yè)一般提供的是由客戶下單時預(yù)先設(shè)定的貨物送達時間，進而在該設(shè)定的時間段內(nèi)實現(xiàn)配送服務(wù)。為了實現(xiàn)快速、有效的配送，可以將問題轉(zhuǎn)化為含時間約束的旅行商問題(traveling salesman problem,TSP)[2-3]。TSP其實是一個多項式復(fù)雜程度的非確定性問題(non-deterministic polynomial,NP)，常用粒子群算法、遺傳算法、蟻群算法等智能算法來解決。但是使用這些傳統(tǒng)的智能算法，存在運行時間較長、求解效率低的問題。本文采用以MapReduce為基礎(chǔ)的蟻群算法，從而更為高效地解決物流配送順序的帶時間約束TSP。

Hadoop框架是由Apache開源組織開發(fā)的、具有高可靠性、高可擴展性的存儲與分布式并行計算平臺[4]。MapReduce是Hadoop框架的核心模型之一，已經(jīng)廣泛應(yīng)用于大數(shù)據(jù)處理、分布式計算等[5]。本文使用MapReduce實現(xiàn)蟻群算法以及高效求解帶時間約束的TSP，從而快速地給出對含時間約束的物流配送問題的有效解決方案[6-8]。目前，對于基于MapReduce的蟻群算法進行求解傳統(tǒng)的TSP已經(jīng)有比較好的闡述，但是對于含時間約束的TSP，尚未有相關(guān)文獻對其進行詳細分析。

1 問題描述及構(gòu)建模型

傳統(tǒng)TSP是假設(shè)一個貨郎需要走訪N個城市，每個城市必須且僅經(jīng)過一次，最終回到起點城市，形成閉環(huán)。因此，必須找到一條最短的旅行路徑。

假設(shè)物流配送的客戶集為U={u1,u2,…,ui,…,un}，1≤i≤n。當前時間為T0,配送員配送過程中的速度為v,到達客戶ui的時間為Ti；客戶ui預(yù)定的配送時間在Ti1到之間，記為[Ti1-Ti2]，對于未約定配送時間的客戶，其配送時間設(shè)置為(-∞,+∞)。為了提高客戶滿意度，如果Ti?[Ti1-Ti2]，即未能在客戶約定的時間內(nèi)到達城市i，則設(shè)置懲罰值wi。不考慮配送員在每個節(jié)點上提留的時間，懲罰值可定義如下：

(1)

式中：εv為懲罰因子。該值為經(jīng)驗值。在計算過程中，通過將該懲罰值wi增加到路徑開銷中，可以將客戶ui的時間約束轉(zhuǎn)化為路徑約束Li。

假設(shè)物流配送人員訪問的節(jié)點順序為X={x1,x2，…,.xi,…,xn}，0≤xi≤N。xi表示物流配送人員到達的第i個節(jié)點。則該路徑對應(yīng)總路徑長度為：

(2)

式中：d(xi,xi+1)為總路徑中第i個、第(i+1)個節(jié)點之間的距離。

整個路徑上的懲罰值為：

(3)

式中：w(xi)為總路徑上第i個節(jié)點所對應(yīng)的客戶節(jié)點的懲罰值wi。

可構(gòu)建目標函數(shù)為路徑值與懲罰值的總和：

C=L+W

(4)

本文求解的最終目標是尋找目標函數(shù)的最小值，實現(xiàn)路徑最優(yōu)化與懲罰值最小。

2 改進的蟻群算法

蟻群算法 (ant system或ant colony system)由意大利學(xué)者Dorigo、Maniezzo等人于20世紀90年代提出。使用該算法解決優(yōu)化配送路徑問題的基本思路為：用螞蟻的行走路徑表示待優(yōu)化路徑問題的可能解，整個螞蟻群體的所有路徑構(gòu)成待優(yōu)化問題的解空間。路徑較短的螞蟻釋放的信息素(模擬螞蟻會在其經(jīng)過的路徑上釋放的物質(zhì)，能使得螞蟻根據(jù)感知到的信息素濃度行走)量較多。隨著時間的演化，較短路徑上累積的信息素濃度逐漸增高，選擇該路徑的螞蟻個數(shù)也將約來越多。最終，每個螞蟻會在這種正反饋的作用下集中到最佳的路徑上。此時對應(yīng)的路徑便是待優(yōu)化問題的最優(yōu)解。

本文在傳統(tǒng)的蟻群算法基礎(chǔ)上進行改進。因此，求解含時間約束的TSP算法詳述如下。

2.1 參數(shù)說明

設(shè)m為本算法中的螞蟻數(shù)目，di,j(i,j=1,2,…,n)表示從ui用戶到用戶uj之間的距離，τi,j(t)表示時刻t在用戶i、j之間的路徑上保留的信息素。將每條路徑上初始時刻的信息素設(shè)為τi,j(0)=c。在運動過程中，螞蟻k(k=1,2,…，m)根據(jù)各個路徑上的信息素確定下一步待轉(zhuǎn)移的目標用戶；S表示在t時刻，螞蟻k轉(zhuǎn)移到用戶uj的概率。

(5)

2.2 蟻群算法信息素改良機制

將信息素強度的值進行限定在范圍[τmin,τmax]內(nèi)，不在這個范圍內(nèi)的最小值與最大值分別設(shè)為τmin或τmax。限制最大值的目的是防止算法陷入局部最優(yōu)解；限制最小值的目的是防止搜索向錯誤的方向收斂。

當τij>τmax時，按式(6)計算信息素強度：

τij(t+1)=(1-α1)1+s(m)τij(t)+Δτij

(6)

當τij﹤τmin時，按式(7)計算信息素強度：

τij(t+1)=(1-α1)1-s(m)τij(t)+Δτij

(7)

當τmin≤τij≤τmax時，按式(8)計算信息素強度：

τij(t+1)=(1-α1)τij(t)+Δτij

(8)

式中：α1為揮發(fā)因子，表示信息素的保留率；Δτij為示信息素的增加量；s(m)為與迭代過程中被改進的解的個數(shù)m成正比的函數(shù)。

2.3 局部信息素更新機制

在采用局部信息素更新規(guī)則來修正信息素值時，螞蟻k對其走過的每條路徑，參照式(6)～式(8)來更新邊上保留的局部信息素值。

當0<α1<1時，信息素揮發(fā)參數(shù)：

Δτij=(ngLnn)-1

(9)

式中：Lnn為由最近鄰域啟發(fā)算法計算出的路徑長度。

2.4 全局信息素更新機制

對于應(yīng)用全局信息素更新規(guī)則來修正信息素值時，考慮在一次迭代的過程中，m個螞蟻生成m個解后，計算該求解過程中的最短路徑，作為本次迭代的最優(yōu)解。將這條路徑上所有保留的信息素按照式(10)更新：

τ(t+1)=(1-α)τ(t)+αΔτ(t)

(10)

當0<α<1時，信息素揮發(fā)系數(shù)為：

(11)

式中：Lgb為當前得到的全局最優(yōu)解的路線長度。

隨著信息素的揮發(fā)，全局最短路線上各邊上的信息素值得到增加。

3 基于MapReduce的蟻群算法的實現(xiàn)

使用MapReduce方法求解本問題的思路如下：在Map函數(shù)中初始化，設(shè)置蟻群，利用多個Map函數(shù)并行計算螞蟻的求解過程，獲得多個可行解，并在Map函數(shù)中設(shè)置局部信息素矩陣，對局部信息素進行更新。

首先，讀入待處理文件中記錄的數(shù)據(jù)，并設(shè)置m個Map，每個Map中設(shè)置n個螞蟻，并以鍵值對的形式輸出，key代表蟻群編號，value的形式為{X={x1,x2,…,xi,…xn}}，該Map計算得到的最優(yōu)解的路徑長度}。在Reduce函數(shù)中設(shè)置全局信息素矩陣為：

Pn×n=|pij|

(12)

式中：pij為用戶ui到用戶uj之間的全局信息素，1≤i,j≤n。

利用Reduce函數(shù)，求得全局最優(yōu)解和調(diào)整全局信息素。然后，利用云計算的管道能力，將Reduce函數(shù)的計算結(jié)果，即信息素的改變、全局最優(yōu)解、全局最優(yōu)解路徑，傳遞到Map函數(shù)，作為下一個Map函數(shù)的輸入，執(zhí)行迭代計算。使用的蟻群算法最終改進如下。

①初始化。

{1-1：構(gòu)造Map函數(shù)、Reduce函數(shù)，設(shè)置Map函數(shù)的個數(shù)NUM_MAP、Reduce函數(shù)的個數(shù)NUM_REDUCE，初始化局部信息素矩陣、全局信息素矩陣；

1-2：設(shè)置每個Map函數(shù)中的螞蟻數(shù)，螞蟻算法運行代數(shù)為no_iteration}

②對每個Map函數(shù)中的每只螞蟻隨機產(chǎn)生一個初始解：

{X={x1,…xi,…xn}}

③更新信息素。

{3-1：每個Map節(jié)點分別根據(jù)式(1)～式(4)計算本節(jié)點下各個螞蟻的解;

3-2：根據(jù)式(9)更新每個螞蟻的局部信息素以及局部最優(yōu)解。}

④調(diào)整信息素。

{4-1：將Map獲得的各個螞蟻分配到各個Reduce節(jié)點中;

4-2：通過Reduce函數(shù)計算全局最優(yōu)解;

4-3：根據(jù)式(10)調(diào)整全局解向量的信息素。}

⑤本次迭代結(jié)束。

{if 迭代次數(shù) => no_ iteration

算法結(jié)束；

Else 將全局最優(yōu)解信息更新到所有的Map節(jié)點中}

4 試驗

為了對以上理論進行驗證，試驗環(huán)境搭建如下。采用4臺普通的服務(wù)器進行搭建的Hadoop集群系統(tǒng)試驗，每臺服務(wù)器內(nèi)存2 GB，存儲空間250 GB。Hadoop的版本是hadoop.0.20.2。操作系統(tǒng)的版本是Red Hat Linux 9.0。測試方法是在Hadoop的框架下進行計算。以TSP標準測試集中的數(shù)據(jù)gr431為例，設(shè)置物流配送人員的配送時間段為[9：00-21：00]，在該時間段內(nèi)以兩個小時為一個預(yù)約時間段，隨機設(shè)置預(yù)約配送時間，求解了運算結(jié)果。另外，還比較了TSP節(jié)點數(shù)分別為48、120、229、431時，基于MapReduce的蟻群算法(記為并行)與串行的蟻群算法(即未使用分布式算法的蟻群算法)的運行時間。蟻群算法與串行蟻群算法的運行時間對比如表1所示。

表1 并行蟻群算法與串行蟻群算法的運行時間對比

經(jīng)過多次反復(fù)試驗，程序中用到的參數(shù)設(shè)置為ρ=0.1、α=0.7、β=0.1、θ=0.4比較合理，能夠得到較好的試驗結(jié)果。設(shè)置Map數(shù)m=4，每個Map上的螞蟻數(shù)n=200，車速為60 km/h。又以TSP標準測試集中的數(shù)據(jù)gr431為例，比較了螞蟻數(shù)不同時對運算時間的影響。

運行時間1 800 s，運行的解路徑長度為221 827.78。

如圖1所示，當 TSP 節(jié)點數(shù)為 48 和 120 時，并行算法的運行時間大于串行算法；當TSP節(jié)點數(shù)為229和431時，并行算法運行的時間小于串行算法所需的時間。隨著TSP節(jié)點數(shù)增多，并行算法運行時間比串行算法更短時間的趨勢。不同螞蟻數(shù)的運算時間對比如圖1所示。

圖1 不同螞蟻數(shù)的運算時間對比圖

從圖1中的結(jié)果可以看出，隨著螞蟻數(shù)量的增加，運行時間有縮短的趨勢。

5 結(jié)束語

本文采用基于MapReduce的蟻群算法求解包含時間約束的TSP，用螞蟻的行走路徑表示待優(yōu)化路徑問題的可能解，整個螞蟻群體的所有路徑構(gòu)成待優(yōu)化問題的解空間；利用MapReduce的并行機制，對蟻群算法進行并行處理，使其運行在分布式環(huán)境中，增強了求解大規(guī)模問題的能力，提高了運行速度。試驗結(jié)果表明，該算法有效。后續(xù)的工作將探索結(jié)合多種智能算法解決帶有復(fù)雜約束的NP問題。