帶油耗的單商品取送貨旅行商問題研究

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

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

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

中圖分類號：F252.14 文獻(xiàn)標(biāo)識碼：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 引 言

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

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

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

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

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

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

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

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

交叉：

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

變異：

采用GA_1的變異方法。

3 例 子

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

應(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，它對本文問題的目標(biāo)函數(shù)值為：236950/3=7.898331178012094e+04。

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

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，它對本文問題的目標(biāo)函數(shù)值為：323222/3=1.077406446095206e+05。

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

4 結(jié) 論

由于近年來對油耗問題的關(guān)注，本文針對過去的1-PDTSP，提出了帶油耗的1-PDTSP，這更具有現(xiàn)實意義。根據(jù)本問題的特點給出了求解算法，并通過例子對算法進(jìn)行說明，結(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問題及其遺傳算法求解[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問題的改進(jìn)蟻群系統(tǒng)[J]. 內(nèi)江師范學(xué)院學(xué)報，2013，28（10）：1671-1785.

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