基于道路分級的TSP問題研究

向俾海，段彩雪

（長安大學汽車學院，陜西 西安 710064）

基于道路分級的TSP問題研究

向俾海，段彩雪

（長安大學汽車學院，陜西 西安 710064）

不同等級的公路對應著不同的道路條件，這將會直接影響汽車的運行速度。文章在充分考慮公路等級影響的前提下，對TSP優(yōu)化問題進行探討，結合傳統(tǒng)優(yōu)化模型，利用lingo編碼運行。

TSP優(yōu)化；lingo；道路分級

前言

旅行商問題（TSP）是運輸路徑規(guī)劃問題（VRP）的分支，可描述為：各運輸點間距離提前預知，每個運輸點訪問一次且由一輛車輛完成，最終回到出發(fā)點，以總旅行路程最小化或時間成本最小為優(yōu)化目標。然而，傳統(tǒng)研究中在以時間成本為優(yōu)化目標時，往往對道路條件所帶來的影響很少有考慮。

在參與運輸車輛參數固定的情況下，所選擇的路徑類型也將因對應的道路條件不同而直接影響到車輛行駛速度[1]，這種差異在山區(qū)道路中尤為明顯。當兩個運輸節(jié)點間存在不同等級的道路時，所選擇的路徑類型也將對運輸效率產生顯著的影響[2]。本文在傳統(tǒng) TSP問題研究的基礎上，充分考慮道路條件的影響，將不同等級公路對應的平均行駛速度引入傳統(tǒng)運輸路徑優(yōu)化模型，從而使改進后的模型更貼合實際。

1 建立優(yōu)化模型

1.1 問題描述

直接影響目標的因素包括：總運輸距離，車輛行駛速度、綜合道路條件、交通擁堵等[3]，本文以運輸的時間成本為優(yōu)化目標，假定全部運輸活動都在交通擁堵不明顯的路段中進行，已知條件包括：

（1）所有配送點之間都有至少一條道路互通；（2）不帶時間窗限制；（3）所有節(jié)點所需配送總量不超過單車載重量；（4）相同節(jié)點間不同類型道路的距離可以不同。

1.2 道路分級

根據我國現行的《公路工程技術標準》（JTGB01-2003），公路按使用任務、功能和適應的交通量分為高速公路、一級公路、二級公路、三級公路、四級公路5個等級，各等級公路設計速度如下：

1.3 優(yōu)化模型

目標函數：

式中，Z代表總配送時間，i，j代表不同節(jié)點，r表示道路類型。tijr為由i點出發(fā)通過r型道路到達j點，Lijr表示i點到j點r型道路的里程。式①為目標函數；等式②、③確保從i點到j點只能通過一種類型道；等式④反映各節(jié)點之間運行時間與道路類型及道路里程的關系。

2 案例分析

湘西自治州位于湖南省西北部，州府所在地吉首位于自治州中部，下轄吉首（1）、龍山（2）、永順（3）、保靖（4）、花垣（5）、古丈（6）、瀘溪（7）、鳳凰（8）等八縣市。境內以高山、丘陵地貌帶為主，高速公路、國道、省道、縣道以及鄉(xiāng)村公路縱橫交錯。受地形垂直起伏影響，各類型道路平均行駛速度相差明顯，進而對路徑規(guī)劃影響顯著。在此前提下，日常生產生活中有關TSP問題時，考慮不同公路等級的影響具有重要意義。

圖1 湘西各縣市交通地圖

州府所在地吉首市，也是該地區(qū)的行政、物流中心，各企事業(yè)單位經常以吉首為出發(fā)點向下屬各縣配發(fā)物資。本文以武警支隊單車向下屬各縣中隊配發(fā)小件物資為例，應用運輸優(yōu)化模型進行路徑規(guī)劃。

在本案例中，出發(fā)地為吉首無配送需求，假定所有配送點配送需求之和小于貨車載重量，汽車在行駛過程中都以相應公路等級的最高限速運行，出發(fā)點與下屬各配送點，以及各配送點之間都有至少一條不同等級的道路可以通行。以Lijr表示i點到j點r型道路的里程，各點之間不同等級道路的里程如下表所示：

表2 各節(jié)點距離（km）

本例中應用軟件LINGO（11版）編碼運行。LINGO的適用對象主要為線性和非線性優(yōu)化問題，求解路徑優(yōu)化問題時尤為方便。其中內置了最優(yōu)化建模語言，可以簡捷地表達大規(guī)模運輸問題，快速求解并帶有結果分析[4]。

圖2 TSP問題優(yōu)化結果

j代表通過第r類公路從節(jié)點i到節(jié)點j。由表1可以看出，由節(jié)點7到節(jié)點8點的最短距離為4級公路92.4km，明顯大于高速里程102.6km，而在優(yōu)化結果中卻選用高速公路，由此可見相同里程下更高等級的公路應當優(yōu)先考慮。而由節(jié)點4到節(jié)點3的選用了二級公路，這是因為高速路的87.4km比二級公路運行51.2公里所需時間更長。由此可見道路等級對路徑選取的顯著影響。

3 結論與展望

本文針對以往TSP問題中不考慮道路運行條件的實際，以道路等級決定車輛運行速度等級，在傳統(tǒng)TSP路徑規(guī)劃模型的基礎上，建立起一種基于道路分級的TSP問題路徑優(yōu)化模型。而后以湖南湘西地區(qū)一個配送案例為例，運用LINGO11軟件對模型編碼運行，并對結果進行分析，充分論證了模型的有效性。本文不足之處在于TSP問題只是車輛路徑問題（VRP）的特例，下一步將把道路分級應用于一般性的VRP問題中進行研究。

[1] Hasan Hosseini-Nasab,ParisaLotfalian.Green routing for trucking systems with classification of path types[J].Journal of Cleaner Production.2017 (146): 228-233.

[2] Gajanand, M.S., Narendran, T.T.. Green route planning to reduce the environmental impact of distribution. Int. J. Logist. Res. Appl. 2013 16 (5), 410-432.

[3] Demir, E., Bektas, T., Laporte, G. A comparative analysis of several vehicle emission models for road freight transportation[J]. Transp.Res. Part D Transp. Environ. 2011 16 (5), 347-357.

[4] 謝金星,薛毅.優(yōu)化建模與 LINDO/LINGO 軟件[M].清華大學出版社,2005.

Research on TSP optimization problem based on road classification

Xiang Bihai, Duan Caixue
（Chang’an university, School of Automobile, Shaanxi Xi’an 710064）

Different grades of roads correspond to different road conditions, which will directly affect the speed of the car.In this paper, the TSP optimization problem is discussed on the premise of fully considering the influence of highway grade,and the conclusion is different from the traditional method.

TSP optimization; lingo; road classification

U462.1

A

1671-7988(2017)22-46-03

10.16638 /j.cnki.1671-7988.2017.22.016

向俾海（1990. 9-），就讀于長安大學汽車學院，碩士研究生，研究方向：運輸路徑規(guī)劃。

CLC NO.:U462.1

A

1671-7988(2017)22-46-03