基于道路分级的TSP问题研究

向俾海，段彩雪

（长安大学汽车学院，陕西 西安 710064）

基于道路分级的TSP问题研究

向俾海，段彩雪

（长安大学汽车学院，陕西 西安 710064）

不同等级的公路对应着不同的道路条件，这将会直接影响汽车的运行速度。文章在充分考虑公路等级影响的前提下，对TSP优化问题进行探讨，结合传统优化模型，利用lingo编码运行。

TSP优化；lingo；道路分级

前言

旅行商问题（TSP）是运输路径规划问题（VRP）的分支，可描述为：各运输点间距离提前预知，每个运输点访问一次且由一辆车辆完成，最终回到出发点，以总旅行路程最小化或时间成本最小为优化目标。然而，传统研究中在以时间成本为优化目标时，往往对道路条件所带来的影响很少有考虑。

在参与运输车辆参数固定的情况下，所选择的路径类型也将因对应的道路条件不同而直接影响到车辆行驶速度[1]，这种差异在山区道路中尤为明显。当两个运输节点间存在不同等级的道路时，所选择的路径类型也将对运输效率产生显著的影响[2]。本文在传统 TSP问题研究的基础上，充分考虑道路条件的影响，将不同等级公路对应的平均行驶速度引入传统运输路径优化模型，从而使改进后的模型更贴合实际。

1 建立优化模型

1.1 问题描述

直接影响目标的因素包括：总运输距离，车辆行驶速度、综合道路条件、交通拥堵等[3]，本文以运输的时间成本为优化目标，假定全部运输活动都在交通拥堵不明显的路段中进行，已知条件包括：

（1）所有配送点之间都有至少一条道路互通；（2）不带时间窗限制；（3）所有节点所需配送总量不超过单车载重量；（4）相同节点间不同类型道路的距离可以不同。

1.2 道路分级

根据我国现行的《公路工程技术标准》（JTGB01-2003），公路按使用任务、功能和适应的交通量分为高速公路、一级公路、二级公路、三级公路、四级公路5个等级，各等级公路设计速度如下：

1.3 优化模型

目标函数：

式中，Z代表总配送时间，i，j代表不同节点，r表示道路类型。tijr为由i点出发通过r型道路到达j点，Lijr表示i点到j点r型道路的里程。式①为目标函数；等式②、③确保从i点到j点只能通过一种类型道；等式④反映各节点之间运行时间与道路类型及道路里程的关系。

2 案例分析

湘西自治州位于湖南省西北部，州府所在地吉首位于自治州中部，下辖吉首（1）、龙山（2）、永顺（3）、保靖（4）、花垣（5）、古丈（6）、泸溪（7）、凤凰（8）等八县市。境内以高山、丘陵地貌带为主，高速公路、国道、省道、县道以及乡村公路纵横交错。受地形垂直起伏影响，各类型道路平均行驶速度相差明显，进而对路径规划影响显著。在此前提下，日常生产生活中有关TSP问题时，考虑不同公路等级的影响具有重要意义。

图1 湘西各县市交通地图

州府所在地吉首市，也是该地区的行政、物流中心，各企事业单位经常以吉首为出发点向下属各县配发物资。本文以武警支队单车向下属各县中队配发小件物资为例，应用运输优化模型进行路径规划。

在本案例中，出发地为吉首无配送需求，假定所有配送点配送需求之和小于货车载重量，汽车在行驶过程中都以相应公路等级的最高限速运行，出发点与下属各配送点，以及各配送点之间都有至少一条不同等级的道路可以通行。以Lijr表示i点到j点r型道路的里程，各点之间不同等级道路的里程如下表所示：

表2 各节点距离（km）

本例中应用软件LINGO（11版）编码运行。LINGO的适用对象主要为线性和非线性优化问题，求解路径优化问题时尤为方便。其中内置了最优化建模语言，可以简捷地表达大规模运输问题，快速求解并带有结果分析[4]。

图2 TSP问题优化结果

j代表通过第r类公路从节点i到节点j。由表1可以看出，由节点7到节点8点的最短距离为4级公路92.4km，明显大于高速里程102.6km，而在优化结果中却选用高速公路，由此可见相同里程下更高等级的公路应当优先考虑。而由节点4到节点3的选用了二级公路，这是因为高速路的87.4km比二级公路运行51.2公里所需时间更长。由此可见道路等级对路径选取的显著影响。

3 结论与展望

本文针对以往TSP问题中不考虑道路运行条件的实际，以道路等级决定车辆运行速度等级，在传统TSP路径规划模型的基础上，建立起一种基于道路分级的TSP问题路径优化模型。而后以湖南湘西地区一个配送案例为例，运用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] 谢金星,薛毅.优化建模与 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-），就读于长安大学汽车学院，硕士研究生，研究方向：运输路径规划。

CLC NO.:U462.1

A

1671-7988(2017)22-46-03