向俾海，段彩雪

（長(zhǎng)安大學(xué)汽車學(xué)院，陜西 西安 710064）

基于道路分級(jí)的TSP問題研究

向俾海，段彩雪

（長(zhǎng)安大學(xué)汽車學(xué)院，陜西 西安 710064）

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

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

前言

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

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

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

1.1 問題描述

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

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

1.2 道路分級(jí)

根據(jù)我國(guó)現(xiàn)行的《公路工程技術(shù)標(biāo)準(zhǔn)》（JTGB01-2003），公路按使用任務(wù)、功能和適應(yīng)的交通量分為高速公路、一級(jí)公路、二級(jí)公路、三級(jí)公路、四級(jí)公路5個(gè)等級(jí)，各等級(jí)公路設(shè)計(jì)速度如下：

1.3 優(yōu)化模型

目標(biāo)函數(shù)：

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

2 案例分析

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

圖1 湘西各縣市交通地圖

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

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

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

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

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

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

3 結(jié)論與展望

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

[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].清華大學(xué)出版社,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-），就讀于長(zhǎng)安大學(xué)汽車學(xué)院，碩士研究生，研究方向：運(yùn)輸路徑規(guī)劃。

CLC NO.:U462.1

A

1671-7988(2017)22-46-03