基于目標的改進的貨郎擔問題研究

劉倩++張心怡++逯瑤瑤+++杜曉磊

【摘要】TSP問題是一個經典組合優化問題，而最短路徑算法多樣，卻因其復雜性不具有最優算法.本文在目標改進的基礎上以江蘇省地級市為例，利用MATLAB和LINGO軟件模擬出最優路徑圖，改進算法確定回路，運用搜狗地圖獲取數據建立并求解數學模型以展開研究.

【關鍵詞】TSP問題；動態規劃；LINGO；優化算法

一、背景介紹

貨郎擔問題也叫旅行商問題，即TSP（Traveling Salesman Problem）問題，其要求很簡單：在各城市的集合中，找出一條經過每個城市各一次，最終回到起點的最短路徑.

求解該類問題可以使用精確算法，常用的方法包括：分支定界法、線性規劃法和動態規劃法等，但計算復雜度隨著網絡規模的增大呈指數增長，是NP困難的.當網絡達到一定規模時，通常使用近似算法或啟發式算法求解TSP.近似算法是把誤差控制在一定范圍的前提下快速得到解決方案，包括構造型算法和改進型算法，主要有遺傳算法、蟻群算法、模擬退火算法、人工神經網絡、LK算法、人工免疫算法、粒子群優化算法和混合智能算法等.

二、問題內容

目標①假設今年認識實習安排如下，從徐州市出發，需要訪問江蘇省的所有地級（以上）的城市，然后回到徐州市.本次實習搭乘我校的自備車，請設計路線要求至少經過每個城市1次，并且總的行駛里程最短.

目標②假設今年認識實習安排如下，從徐州市出發，需要訪問江蘇省的所有地級（以上）的城市，然后回到徐州市.本次實習搭乘我校的自備車，請設計路線要求至少經過每個城市1次，考慮公路的收費問題，假設汽車每千米的油耗是固定的，要求總的費用最少（注意：普通公路收費低，高速公路收費高）.

目標③假設今年認識實習安排如下，從徐州市出發，需要訪問江蘇省的所有地級（以上）的城市，然后回到徐州市.本次實習搭乘我校的自備車，請設計路線要求至少經過每個城市1次，考慮不同公路的車速限制問題，假設高速公路限速100千米/小時，其余公路限速60千米/小時，不考慮油耗和收費，汽車均按照最高限速行駛，要求總的時間最短.

三、模型假設

1.假設兩個城市之間的往返是互逆過程.

2.假設所選路線都是可行的，即沒有封路情況.

3.假設城市之間高速公路收費固定.

4.假設各城市的油價統一，均為國內統一油價.

5.假設車輛密度不隨時間變化，不考慮車輛密度變化帶來的速度變化.

6.假設在旅途中的車速一定，且不考慮突發事件干擾大巴的行程.

四、模型的建立與求解

首先用點來代替每個城市的位置，對江蘇省各城市徐州、宿遷、連云港、淮安、鹽城、揚州、泰州、鎮江、南京、常州、無錫、蘇州和南通等按順序編號為1，2，…，13.

（一）問題一

1.模型的建立

設城市的個數為n，dij是兩個城市i與j之間的距離，xij=0或1，假設一個TSP由城市1，2，3，…，13組成.當i≠j，設cij城市i到城市j的距離，設cij=M，其中M是一個非常大的數.設定cij=M將確保我們不會再離開城市i后不會馬上到達城市i，此外定義

xij=1如果TSP的解是從城市i到城市j，

0如果TSP的解不是從城市i到城市j.

通過求解：

minz=∑i∑jcijxij，

∑i=ni=1xij≥1（j=1，2，…，n）.（1）

∑j=nj=1xij≥1（i=1，2，…，n）.（2）

ui-uj+n≤n-1（i≠j，i=2，3，…，n；j=2，3，…，n）.（3）

xij=0或1，uij≥0.（4）

目標函數給出了包括巡回訪問路線中弧長的總長度，約束條件（1）確保我們到達城市至少一次，約束條件（2）確保我們只離開一個城市一次，（3）中的約束條件是表達的關鍵，他們確保：

（1）包含子巡回路線的任何一組xij都是不可行的（也就是它們違反了（3））；

（2）構成子巡回路線的任何一組xij都是可行的（存在一組滿足（3）的uj）.

2.模型的求解

為了直觀顯示江蘇省各城市之間的位置關系，我們搜集了江蘇省13個城市的經緯度坐標，不相鄰城市之間取非常大的數100 000 km.

根據江蘇省各城市的經緯度坐標及兩兩城市之間的最短距離，我們運用Matlab軟件模擬出了實習路線效果圖，其中每一個“

Wingdings 2AB@ ”表示每個城市，折線表示實習路線，徐州市為實習起點，得到最優實習路線為：徐州→連云港→鹽城→南通→泰州→蘇州→無錫→常州→鎮江→揚州→南京→淮安→宿遷→徐州，路線距離總和為：1534.2 km.

（二）問題二模型建立與求解

對于問題二，運用所建的模型，“最短距離”換為“最少費用”.由調查得出，汽車百千米油耗約為30 L，國內標準油價5.19元/L，且汽車每千米油耗固定，計算出汽車油耗費用為1.557元/km.根據實際道路長度，可以算出汽車油耗費用，再加上路程高速費用，從而可以得到江蘇省兩兩城市之間的最少費用.同樣，我們把不相鄰的城市的行駛費用設為100 000元，即足夠大，從而實現不可能選取.

我們基于上述模型及行駛費用最小原則，最優行駛路線為：徐州→連云港→鹽城→泰州→南通→蘇州→無錫→常州→鎮江→南京→揚州→淮安→宿遷→徐州，行駛費用總和為2 523.25元.

（三）問題三模型建立與求解

1.理論時間模型

對于問題三，將模型二中的權值“最短距離”換為“最短時間”.由題目假設，汽車高速公路限速100千米/小時，其余公路限速60千米/小時，不考慮油耗和收費，根據問題一搜集到的兩城市之間道路距離，再從中細化出高速距離與其他公路距離，根據車速，從而計算出江蘇省各城市之間所需行駛時間，同樣，根據江蘇省交通廳的實時交通圖及Lingo運行特點，我們把不相鄰的城市的行駛時間設為100 000分鐘，即足夠大，從而實現不可能選取.

我們以任意兩城市之間的行駛時間矩陣為權重矩陣，利用w3（i，j）13×13構造無向圖UG3，利用Lingo軟件按改良圈算法求解，首先設C=v1v3…vnv3，求出符合要求的最短距離的最優圈circle3，保證從終點返回到出發點的行駛時間也最短.

從理論行駛時間模型的結果來看，基于總行駛時間最短原則，Lingo程序求解的認識實習的最優路線為徐州→宿遷→淮安→南京→揚州→鎮江→常州→無錫→蘇州→南通→泰州→鹽城→連云港→徐州，行程總時間為1 011 min.

2.實際時間模型

由于實際路況的復雜性，各路況允許汽車行駛速度的不同，同時為了檢驗可靠性，我們在高德地圖上搜集了城市之間的實際最短行駛時間，這個時間更具有說服力.

同樣我們基于理論行駛時間模型的算法，以任意兩城市之間的行駛時間矩陣為權重矩陣，利用Lingo軟件按改良圈算法求解，首先設C=v1v4…vnv4，按改良圈算法求出此時的最優圈后，求出符合要求的最短距離的最優圈circle4，保證了從終點返回到出發點的行駛時間也最短.

從結果可知，基于實際行駛時間的實習最優路線與理論時間模型的最優路線相同，說明理論時間模型結果具有很高的可靠性，具體行駛路線與理論時間模型優化路線一致.

【參考文獻】

[1]管琳，白艷萍.用分支定界算法求解旅行商問題[J].中北大學學報（自然科學版），2007（02）：104-107.

[2]呂善國，曹義親，陳紅麗.求解旅行商問題的一種新方法[J].華東交通大學學報，2012（05）：29-33.

[3]W L Winston.運籌學應用范例與解法[M].楊振凱，等譯.北京：清華大學出版社，2006：572-599.endprint