基于目標(biāo)的改進(jìn)的貨郎擔(dān)問(wèn)題研究

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

【摘要】TSP問(wèn)題是一個(gè)經(jīng)典組合優(yōu)化問(wèn)題，而最短路徑算法多樣，卻因其復(fù)雜性不具有最優(yōu)算法.本文在目標(biāo)改進(jìn)的基礎(chǔ)上以江蘇省地級(jí)市為例，利用MATLAB和LINGO軟件模擬出最優(yōu)路徑圖，改進(jìn)算法確定回路，運(yùn)用搜狗地圖獲取數(shù)據(jù)建立并求解數(shù)學(xué)模型以展開(kāi)研究.

【關(guān)鍵詞】TSP問(wèn)題；動(dòng)態(tài)規(guī)劃；LINGO；優(yōu)化算法

一、背景介紹

貨郎擔(dān)問(wèn)題也叫旅行商問(wèn)題，即TSP（Traveling Salesman Problem）問(wèn)題，其要求很簡(jiǎn)單：在各城市的集合中，找出一條經(jīng)過(guò)每個(gè)城市各一次，最終回到起點(diǎn)的最短路徑.

求解該類(lèi)問(wèn)題可以使用精確算法，常用的方法包括：分支定界法、線性規(guī)劃法和動(dòng)態(tài)規(guī)劃法等，但計(jì)算復(fù)雜度隨著網(wǎng)絡(luò)規(guī)模的增大呈指數(shù)增長(zhǎng)，是NP困難的.當(dāng)網(wǎng)絡(luò)達(dá)到一定規(guī)模時(shí)，通常使用近似算法或啟發(fā)式算法求解TSP.近似算法是把誤差控制在一定范圍的前提下快速得到解決方案，包括構(gòu)造型算法和改進(jìn)型算法，主要有遺傳算法、蟻群算法、模擬退火算法、人工神經(jīng)網(wǎng)絡(luò)、LK算法、人工免疫算法、粒子群優(yōu)化算法和混合智能算法等.

二、問(wèn)題內(nèi)容

目標(biāo)①假設(shè)今年認(rèn)識(shí)實(shí)習(xí)安排如下，從徐州市出發(fā)，需要訪問(wèn)江蘇省的所有地級(jí)（以上）的城市，然后回到徐州市.本次實(shí)習(xí)搭乘我校的自備車(chē)，請(qǐng)?jiān)O(shè)計(jì)路線要求至少經(jīng)過(guò)每個(gè)城市1次，并且總的行駛里程最短.

目標(biāo)②假設(shè)今年認(rèn)識(shí)實(shí)習(xí)安排如下，從徐州市出發(fā)，需要訪問(wèn)江蘇省的所有地級(jí)（以上）的城市，然后回到徐州市.本次實(shí)習(xí)搭乘我校的自備車(chē)，請(qǐng)?jiān)O(shè)計(jì)路線要求至少經(jīng)過(guò)每個(gè)城市1次，考慮公路的收費(fèi)問(wèn)題，假設(shè)汽車(chē)每千米的油耗是固定的，要求總的費(fèi)用最少（注意：普通公路收費(fèi)低，高速公路收費(fèi)高）.

目標(biāo)③假設(shè)今年認(rèn)識(shí)實(shí)習(xí)安排如下，從徐州市出發(fā)，需要訪問(wèn)江蘇省的所有地級(jí)（以上）的城市，然后回到徐州市.本次實(shí)習(xí)搭乘我校的自備車(chē)，請(qǐng)?jiān)O(shè)計(jì)路線要求至少經(jīng)過(guò)每個(gè)城市1次，考慮不同公路的車(chē)速限制問(wèn)題，假設(shè)高速公路限速100千米/小時(shí)，其余公路限速60千米/小時(shí)，不考慮油耗和收費(fèi)，汽車(chē)均按照最高限速行駛，要求總的時(shí)間最短.

三、模型假設(shè)

1.假設(shè)兩個(gè)城市之間的往返是互逆過(guò)程.

2.假設(shè)所選路線都是可行的，即沒(méi)有封路情況.

3.假設(shè)城市之間高速公路收費(fèi)固定.

4.假設(shè)各城市的油價(jià)統(tǒng)一，均為國(guó)內(nèi)統(tǒng)一油價(jià).

5.假設(shè)車(chē)輛密度不隨時(shí)間變化，不考慮車(chē)輛密度變化帶來(lái)的速度變化.

6.假設(shè)在旅途中的車(chē)速一定，且不考慮突發(fā)事件干擾大巴的行程.

四、模型的建立與求解

首先用點(diǎn)來(lái)代替每個(gè)城市的位置，對(duì)江蘇省各城市徐州、宿遷、連云港、淮安、鹽城、揚(yáng)州、泰州、鎮(zhèn)江、南京、常州、無(wú)錫、蘇州和南通等按順序編號(hào)為1，2，…，13.

（一）問(wèn)題一

1.模型的建立

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

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

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

通過(guò)求解：

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）

目標(biāo)函數(shù)給出了包括巡回訪問(wèn)路線中弧長(zhǎng)的總長(zhǎng)度，約束條件（1）確保我們到達(dá)城市至少一次，約束條件（2）確保我們只離開(kāi)一個(gè)城市一次，（3）中的約束條件是表達(dá)的關(guān)鍵，他們確保：

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

（2）構(gòu)成子巡回路線的任何一組xij都是可行的（存在一組滿(mǎn)足（3）的uj）.

2.模型的求解

為了直觀顯示江蘇省各城市之間的位置關(guān)系，我們搜集了江蘇省13個(gè)城市的經(jīng)緯度坐標(biāo)，不相鄰城市之間取非常大的數(shù)100 000 km.

根據(jù)江蘇省各城市的經(jīng)緯度坐標(biāo)及兩兩城市之間的最短距離，我們運(yùn)用Matlab軟件模擬出了實(shí)習(xí)路線效果圖，其中每一個(gè)“

Wingdings 2AB@ ”表示每個(gè)城市，折線表示實(shí)習(xí)路線，徐州市為實(shí)習(xí)起點(diǎn)，得到最優(yōu)實(shí)習(xí)路線為：徐州→連云港→鹽城→南通→泰州→蘇州→無(wú)錫→常州→鎮(zhèn)江→揚(yáng)州→南京→淮安→宿遷→徐州，路線距離總和為：1534.2 km.

（二）問(wèn)題二模型建立與求解

對(duì)于問(wèn)題二，運(yùn)用所建的模型，“最短距離”換為“最少費(fèi)用”.由調(diào)查得出，汽車(chē)百千米油耗約為30 L，國(guó)內(nèi)標(biāo)準(zhǔn)油價(jià)5.19元/L，且汽車(chē)每千米油耗固定，計(jì)算出汽車(chē)油耗費(fèi)用為1.557元/km.根據(jù)實(shí)際道路長(zhǎng)度，可以算出汽車(chē)油耗費(fèi)用，再加上路程高速費(fèi)用，從而可以得到江蘇省兩兩城市之間的最少費(fèi)用.同樣，我們把不相鄰的城市的行駛費(fèi)用設(shè)為100 000元，即足夠大，從而實(shí)現(xiàn)不可能選取.

我們基于上述模型及行駛費(fèi)用最小原則，最優(yōu)行駛路線為：徐州→連云港→鹽城→泰州→南通→蘇州→無(wú)錫→常州→鎮(zhèn)江→南京→揚(yáng)州→淮安→宿遷→徐州，行駛費(fèi)用總和為2 523.25元.

（三）問(wèn)題三模型建立與求解

1.理論時(shí)間模型

對(duì)于問(wèn)題三，將模型二中的權(quán)值“最短距離”換為“最短時(shí)間”.由題目假設(shè)，汽車(chē)高速公路限速100千米/小時(shí)，其余公路限速60千米/小時(shí)，不考慮油耗和收費(fèi)，根據(jù)問(wèn)題一搜集到的兩城市之間道路距離，再?gòu)闹屑?xì)化出高速距離與其他公路距離，根據(jù)車(chē)速，從而計(jì)算出江蘇省各城市之間所需行駛時(shí)間，同樣，根據(jù)江蘇省交通廳的實(shí)時(shí)交通圖及Lingo運(yùn)行特點(diǎn)，我們把不相鄰的城市的行駛時(shí)間設(shè)為100 000分鐘，即足夠大，從而實(shí)現(xiàn)不可能選取.

我們以任意兩城市之間的行駛時(shí)間矩陣為權(quán)重矩陣，利用w3（i，j）13×13構(gòu)造無(wú)向圖UG3，利用Lingo軟件按改良圈算法求解，首先設(shè)C=v1v3…vnv3，求出符合要求的最短距離的最優(yōu)圈circle3，保證從終點(diǎn)返回到出發(fā)點(diǎn)的行駛時(shí)間也最短.

從理論行駛時(shí)間模型的結(jié)果來(lái)看，基于總行駛時(shí)間最短原則，Lingo程序求解的認(rèn)識(shí)實(shí)習(xí)的最優(yōu)路線為徐州→宿遷→淮安→南京→揚(yáng)州→鎮(zhèn)江→常州→無(wú)錫→蘇州→南通→泰州→鹽城→連云港→徐州，行程總時(shí)間為1 011 min.

2.實(shí)際時(shí)間模型

由于實(shí)際路況的復(fù)雜性，各路況允許汽車(chē)行駛速度的不同，同時(shí)為了檢驗(yàn)可靠性，我們?cè)诟叩碌貓D上搜集了城市之間的實(shí)際最短行駛時(shí)間，這個(gè)時(shí)間更具有說(shuō)服力.

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

從結(jié)果可知，基于實(shí)際行駛時(shí)間的實(shí)習(xí)最優(yōu)路線與理論時(shí)間模型的最優(yōu)路線相同，說(shuō)明理論時(shí)間模型結(jié)果具有很高的可靠性，具體行駛路線與理論時(shí)間模型優(yōu)化路線一致.

【參考文獻(xiàn)】

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

[2]呂善國(guó)，曹義親，陳紅麗.求解旅行商問(wèn)題的一種新方法[J].華東交通大學(xué)學(xué)報(bào)，2012（05）：29-33.

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