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

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

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

關鍵詞：運籌學；單商品旅行商問題；油耗；遺傳算法

中圖分類號：F252.14 文獻標識碼：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）是傳統旅行商問題（TSP）的一類新變種。與TSP相比1-PDTSP的特殊之處在于：一個特殊的城市作為車場，其它城市作為客戶，客戶根據其需求類型可被劃分為送貨客戶和取貨客戶兩類，而所謂的送貨客戶（需求量小于0）與取貨客戶（需求量大于或等于0）分別指需要一定數量的貨物被送達和被取走的客戶。1-PDTSP的特殊性還體現在貨物上：送貨客戶所需要的貨物不僅可以來自車場，還可以直接來自于取貨客戶，即從取貨客戶處取回的貨物可以直接供送貨客戶使用，此外，1-PDTSP還假設車輛必須從車場出發，并且最終回到車場，車輛的容量給定并且有限，車場有足夠的貨物供各客戶使用，也具備足夠的空間存放取回的貨物。

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

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

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

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

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

1 帶油耗的1-PDTSP問題及其數學模型

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

交叉：

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

變異：

采用GA_1的變異方法。

3 例 子

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

應用貪婪式啟發式算法和本文的遺傳算法GA_2得到的本例的次優解相同，都為哈密頓回路：

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

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

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

顯然對本文的問題而言Solution_1的目標函數值要遠遠小于Solution_2的目標函數值，因此求解不帶油耗的1-PDTSP的算法不適合求解本文的帶油耗的1-PDTSP。

4 結 論

由于近年來對油耗問題的關注，本文針對過去的1-PDTSP，提出了帶油耗的1-PDTSP，這更具有現實意義。根據本問題的特點給出了求解算法，并通過例子對算法進行說明，結果表明本文給出的算法適合用于求解帶油耗的1-PDTSP。

參考文獻：

[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]. 計算機工程與應用， 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]. 內江師范學院學報，2013，28（10）：1671-1785.

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