趙麗娜+張麗華+竇冰潔+孫蕊

摘 要：文章研究了一種特殊的旅行商問(wèn)題——帶油耗的單商品取送貨的旅行商問(wèn)題，建立了該問(wèn)題的非線性混合整數(shù)規(guī)劃模型，并且根據(jù)文章問(wèn)題的特征，設(shè)計(jì)了求解它的一個(gè)貪婪式啟發(fā)式算法和一個(gè)遺傳算法，給出一個(gè)例子對(duì)算法進(jìn)行了說(shuō)明。

關(guān)鍵詞：運(yùn)籌學(xué)；單商品旅行商問(wèn)題；油耗；遺傳算法

中圖分類號(hào)：F252.14 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： In this paper， a kind of special traveling salesman problem-the one-commodity pickup and delivery traveling salesman problem with fuel consumption is studied， a non-linear mixed integer programming model for this problem is built， and according to the characteristics of the problem in this paper a greedy heuristic algorithm and a genetic algorithm are designed， an example is given to illustrated the algorithms.

Key words： operational research； one-commodity pickup and delivery traveling salesman problem； fuel consumption； genetic algorithm

0 引 言

單商品取送貨旅行商問(wèn)題（1-PDTSP）是傳統(tǒng)旅行商問(wèn)題（TSP）的一類新變種。與TSP相比1-PDTSP的特殊之處在于：一個(gè)特殊的城市作為車場(chǎng)，其它城市作為客戶，客戶根據(jù)其需求類型可被劃分為送貨客戶和取貨客戶兩類，而所謂的送貨客戶（需求量小于0）與取貨客戶（需求量大于或等于0）分別指需要一定數(shù)量的貨物被送達(dá)和被取走的客戶。1-PDTSP的特殊性還體現(xiàn)在貨物上：送貨客戶所需要的貨物不僅可以來(lái)自車場(chǎng)，還可以直接來(lái)自于取貨客戶，即從取貨客戶處取回的貨物可以直接供送貨客戶使用，此外，1-PDTSP還假設(shè)車輛必須從車場(chǎng)出發(fā)，并且最終回到車場(chǎng)，車輛的容量給定并且有限，車場(chǎng)有足夠的貨物供各客戶使用，也具備足夠的空間存放取回的貨物。

1-PDTSP由Hipólito和Juan-José[1]于2003年首次提出，并且在2004年[2]他們給出了一種分支—切割（branch-and-cut）算法對(duì)其進(jìn)行求解，該算法可以求得1-PDTSP的精確解，但當(dāng)問(wèn)題的規(guī)模較大時(shí)，分支—切割算法時(shí)間太長(zhǎng)，因此他們?cè)谕闧3]以及2007年[4]、2009年[5]提出了幾種啟發(fā)式算法來(lái)求解1-PDTSP；2006年Fan Wang等人[6]給出求解1-PDTSP的一個(gè)關(guān)于路徑和樹形拓?fù)浣Y(jié)構(gòu)的優(yōu)化算法；2009年趙方庚等人[7]給出一個(gè)遺傳算法來(lái)解決此問(wèn)題；2012年Nenad Mladenovic等人設(shè)計(jì)了求解1-PDTSP的變鄰域搜索算法[10]，這些啟發(fā)式算法都能較好地解決大規(guī)模1-PDTSP，然而由于1-PDTSP只考慮優(yōu)化車輛總的行駛費(fèi)用，而在當(dāng)今社會(huì)，隨著能源的短缺和環(huán)境污染的日趨嚴(yán)重，油耗問(wèn)題成為人們關(guān)注的焦點(diǎn)，因此本文研究帶油耗的1

-PDTSP，該問(wèn)題到目前為止還沒(méi)有人研究過(guò)，它與1-PDTSP的區(qū)別在于既考慮車輛的行駛費(fèi)用又考慮車輛的載貨量產(chǎn)生的耗油費(fèi)用，這樣一來(lái)，雖然兩個(gè)問(wèn)題的可行集是相同的，但最優(yōu)解不同，下面舉例說(shuō)明。

設(shè)有1個(gè)車場(chǎng)，4個(gè)客戶點(diǎn)，它們的需求及相互之間的距離分別如下列的表1和表2所示，車輛容量為10。

設(shè)單位距離費(fèi)用為1，單位距離單位重量費(fèi)用為1.2，于是所有可行解及相應(yīng)的費(fèi)用如表3所示。

所以不考慮油耗和考慮油耗的最優(yōu)解分別為：1→2→4→5→3→1和1→5→3→2→4→1，說(shuō)明帶油耗和不帶油耗的1-PDTSP是有區(qū)別的，求解后者的算法不適用于前者，本文第3節(jié)的例子也說(shuō)明了這一點(diǎn)，因此本文根據(jù)帶油耗的1-PDTSP的特點(diǎn)設(shè)計(jì)了一個(gè)貪婪式啟發(fā)式算法和一個(gè)遺傳算法求解它，其中的遺傳算法是將文獻(xiàn)[7]的遺傳算法進(jìn)行修改得到的。

1 帶油耗的1-PDTSP問(wèn)題及其數(shù)學(xué)模型

（4）計(jì)算可行解1、可行解2對(duì)本文問(wèn)題的目標(biāo)函數(shù)值，將目標(biāo)函數(shù)值最小的可行解存儲(chǔ)在一個(gè)1行3列的元胞數(shù)組的第2個(gè)元素里，該元胞數(shù)組的第1個(gè)元素存儲(chǔ)1，第3該元素存儲(chǔ)該解對(duì)本文問(wèn)題的目標(biāo)函數(shù)值的倒數(shù)，得到一條染色體。重復(fù)使用該方法生成100條染色體得初始種群。

交叉：

采用GA_1的交叉方法，但要將在可行鄰居中挑選下一客戶點(diǎn)的規(guī)則改為在可行鄰居中挑選需求絕對(duì)值除以到未完成路徑中最后一個(gè)客戶點(diǎn)的距離最大者為下一個(gè)客戶點(diǎn)。

變異：

采用GA_1的變異方法。

3 例 子

在本例中，客戶數(shù)為70，本文用文獻(xiàn)[7]中的方法生成例子： 車場(chǎng)的坐標(biāo)為0，0，其它70個(gè)客戶點(diǎn)的橫縱坐標(biāo)在-500，500范圍內(nèi)隨機(jī)生成，每個(gè)客戶的需求q在-10，10范圍內(nèi)隨機(jī)產(chǎn)生，車場(chǎng)需求車輛容量為10，單位重量單位距離的運(yùn)輸費(fèi)用是1.5，空載時(shí)單位距離的行駛費(fèi)用是1。表4為各客戶點(diǎn)的需求量，圖1為車場(chǎng)和所有客戶點(diǎn)的位置圖。

應(yīng)用貪婪式啟發(fā)式算法和本文的遺傳算法GA_2得到的本例的次優(yōu)解相同，都為哈密頓回路：

0→27→14→58→34→43→47→32→1→57→51→40→26→21→48→61→18→41→37→35→23→59→29→3→16→53→52→31→66→15→44→4→65→8→54→36→46→30→69→11→62→39→67→9→25→28→56→22→68→42→64→50→55→63→38→12→20→45→70→24→5→19→60→33→2→6→49→7→10→17→13→0endprint

該解記為Solution_1，它對(duì)本文問(wèn)題的目標(biāo)函數(shù)值為：236950/3=7.898331178012094e+04。

應(yīng)用文獻(xiàn)[7]中的遺傳算法GA_1得到的求解不帶油耗的1-PDTSP問(wèn)題的次優(yōu)解（該解也是本文問(wèn)題的可行解）為哈密頓回路：

0→65→21→48→61→18→41→23→59→37→22→30→69→11→67→9→36→8→54→42→64→60→33→4→32→43→14→27→47→58→57→44→15→52→53→16→31→66→63→55→40→51→34→45→20→50→12→26→38→49→7→3→35→56→28→39→62→2→68→46→25→19→5→70→1→24→17→29→13→6→10→0

該解記為Solution_2，它對(duì)本文問(wèn)題的目標(biāo)函數(shù)值為：323222/3=1.077406446095206e+05。

顯然對(duì)本文的問(wèn)題而言Solution_1的目標(biāo)函數(shù)值要遠(yuǎn)遠(yuǎn)小于Solution_2的目標(biāo)函數(shù)值，因此求解不帶油耗的1-PDTSP的算法不適合求解本文的帶油耗的1-PDTSP。

4 結(jié) 論

由于近年來(lái)對(duì)油耗問(wèn)題的關(guān)注，本文針對(duì)過(guò)去的1-PDTSP，提出了帶油耗的1-PDTSP，這更具有現(xiàn)實(shí)意義。根據(jù)本問(wèn)題的特點(diǎn)給出了求解算法，并通過(guò)例子對(duì)算法進(jìn)行說(shuō)明，結(jié)果表明本文給出的算法適合用于求解帶油耗的1-PDTSP。

參考文獻(xiàn)：

[1] Hernández-Pérez H， Salazar-González J. The one-commodity pickup-and-delivery traveling salesman problem[J]. Combinatorial Optimization （Edmonds Festschrift）， 2003，2570：89-104.

[2] Hernández-Pérez H， Salazar-González J. A breach-and-cut algorithm for a traveling salesman problem with pickup and delivery[J]. Discrete Application Mathematics， 2004，145（1）：126-139.

[3] Hernández-Pérez H， Salazar-González J. Heuristics for the one-commodity pickup-and-delivery traveling salesman problem[J].Transportation Science， 2004，38（2）：245-255.

[4] Hernández-Pérez H and Salazar-González J. The one-commodity pickup-and-delivery traveling salesman problem Inequalities and algorithms[J]. Wiley Inter Science， 2007，50（4）：258-272.

[5] Hernández-Pérez H， Inmaculada M， Salazar-González J. A hybrid GRASP VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computers & Operations Research， 2009，36（1）：1639-1645.

[6] Fan W. Andrew L and Xu Z. The one-commodity pickup and delivery travelling salesman problem on a path or a tree[J]. Wiley Inter Science， 2006，48（1）：24-35.

[7] 趙方庚，李蘇劍，劉偉民，等. 一類特殊的集送一體化TSP問(wèn)題及其遺傳算法求解[J]. 計(jì)算機(jī)工程與應(yīng)用， 2009，45（2）：246

-248.

[8] Nenad M， Dragan U， Said H， et al. A general variable neighborhood search for the one-commodity pickup-and-delivery traveling salesman problem[J]. European Journal of Operational Research， 2012，220（1）：270-285.

[9] Fanggeng Z， Sujian L， Jiangsheng S. Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem[J]. Computer & Industrials Engineering， 2009，56（4）：1642-1648.

[10] Francois L， Salazar-Gonzalez J. On the one-commodity pickup-and-delivery traveling salesman problem with stochastic demands[J]. Math. Program， 2009，119：169-194.

[11] 付慧琳，牟廉明，戴錫笠，等. 求解1-PDTSP問(wèn)題的改進(jìn)蟻群系統(tǒng)[J]. 內(nèi)江師范學(xué)院學(xué)報(bào)，2013，28（10）：1671-1785.

[12] 牟廉明，戴錫笠. 求解選擇性單商品配送收集問(wèn)題的有效蟻群算法[J]. 計(jì)算機(jī)應(yīng)用與軟件，2013，30（12）：93-96.endprint