随机旅行时间旅游路线优化模型及其算法

计算机工程与设计

COMPUTER ENGINEERING ANDDESIGN

Feb. 2019

Vol. 40 No. 2

随机旅行时间旅游路线优化模型及其算法

伍雄斌'，关宏志'，韩艳2

(1.北京工业大学建筑工程学院，北京100124%2.北京工业大学交通工程北京市重点实验室，北京100124)

摘要

：在旅游城市内部空间尺度，针对城市交通网络中旅行时间不确定的旅游路线优化问题，以旅游出行效用和旅游活

动效用组成的旅游体验效用最大化为目标，考虑旅游景点服务时间、旅游时间和费用约束，建立旅游路线优化模型，设计 内嵌随机模拟方法的蚁群求解算法。由对给定的旅游交通网络的优化求解结果可知，该模型及其求解算法是可行的，所得 的优化路线符合旅游者出游的实际情况，对于旅游路线优化具有一定的参考价值。

关键词\"

旅游路线％随机旅行时间％旅游体验％随机规划模型％蚁群算法

中图法分类号：TP311

文献标识号：

A 文章编号：1000-7024 (2019) 02-0573-05

doi： 10. 16208/1. issnl000-7024. 2019. 02. 048

Optimization model and algorithm of tour route with stochastic travel time

WU Xiong-bin1，GUAN Hong-zhi1! HAN Yan2

(1. College of Architecture and 2. Beijing

Key

Laboratory

Civil

of

Engineering，Beijing

University

of

Technology,

of

Transportation Engineering , Beijing University time

uncertainty

on the tour route planning was

and travel algorithm，a

T

Abstract： At the intra-city scale , the impact of travel zing the tourism experience utility was presented to solve the mode..

which

was

studied

composed of effectiveness

tourism activities utility of the model

and

utility

tour route planning was established with the time and budget constraints. The ant colony algorithm with stochastic simulation

To verify the

signed and tested. Results show that the

model and

algorithm are effective and the optimal route

accords with

tourism

The model and algorithm are worthy of applying in tour route planning.

Key words： tour route； stochastic travel time； tourism experience； stochastic programming model； ant colony algorithm

旅游者在旅游城市的出游过程由出行和旅游活动两部

8引言

分组成。城市交通网络决定了旅游者的出行效率，从而影

针对旅游路线优化问题

，Gavalas等

指出旅游路线设计 响到旅游者在景点的旅游活动。城市交通网络具有一定的 不确定性。而旅行时间的不确定是交通网络不确定性的重 要表现6

。因此，将旅行时间不确定因素引人旅游路线优

是以旅游者满意度为目标用等约束的最优化问题解

算

法

龚

丹

丹

等

利

，考

虑景点距离

、游

览时间和费

，并

用

讨论了旅游路线优化问题的求

经网络模型研究了旅

Hopfeld神

化中进行深人的探讨更有现实意义。

游路线制定问题

，所

求路径为景点间的距离最短路径

2。

Bnlhante等

游路线

基于

TSP方

5A景

1旅游路线优化模型

在旅游城市交通网络中，旅游者出游的起点和终点间

法对景点进行串联为旅游者推荐旅

3。吴

劲草等用满意度来衡量旅游体验

区的旅游路线

用

，应

用贪婪

算法设计覆盖全国

4。郭

奇青等引人灰

分布着若干个可以进行旅游活动的景点，节点间有不同的 交通方式可供选择，旅游者在旅游景点进行旅游活动需要 花费一定的时间和费用。因旅游时间

熵评价方法分析景点路线

，应

Dikstra算

法确定最优旅游

5。

Tmx

和费用

C

的限制

收稿日期：2017-12-18；修订日期：2019-01-03

基金项目：国家自然科学基金项目（51378036、51308015)；北京市教委科技基金项目（KM201510005023)

作者简介：伍雄斌（982-)，男，福建三明人，博士研究生，讲师，研究方向为交通规划；关宏志（1959 -)，男

（满族），黑龙江牡

丹江人，教授，研究方向为交通行为；韩艳（1977 -)，女，江苏盐城人，副教授，研究方向为旅游交通行为。E-mail: fafuwuxb@163.com

• 574 •

计算机工程与设计

、arrive , ( 、close,(,产 ^生的延误时间

2019 年

T;iay ( 、arrive, ( 及交通系统存在不确定性，如何对旅游路线进行优化，以 提升旅游者的旅游体验是值得探讨的问题。该问题可以定 义为有效网络&功

）、终

点

、doso ,(十

,,=

TOa+n,,，

且旅游者在景点的实际旅游活动时间

Ta+n

G

&认

= (V,£),）和门动

时和间景

关和

其中点门费

V

为由旅游者出发的起点

1)组成的节

别

为

,

景点 为连接

、close (( 、〇(〇 (。当、arrive ( ,。n,, =

、d+e (

TOra+n，（时

，产 ^生的延误

= 2,3,…时用

刻为

分

时间为〇,且

Ti_T0

_+

n„

。对于额外的等待时间或

点集合，景的

所

需

旅

点游

开活

延迟时间赋予一定的负效用，因而旅游者在景点因等待时 间或延误时间产生的负效用可表示为

、(：；《,(,(。£

）#

£

,

各节点的路段集合。对任意一条路段（,选择交通方式^出行，其

中

旅游者可

U~SD (

$(

UX[、pen，（

、an-i'K , ( ，〇 0 I

(5)

{Waft,

式中$

SclX(、arre , ( 、dose (^I T@ra+n ,(，〇 〇)

每条路段都有时间和费用权重，节点间交通方式^的旅行 为单位时间惩罚系数。

时间、费

用

分

别

为

、

,

且旅行时间是服从某

种分布规律的非确定值。

1.1旅游体验效用函数

使用旅游活动效用和旅游出行效用的概念来描述旅游

体验效用。旅游路线的旅游体验效用为组成该路线的旅游 活动效用与旅游出行效用之和。1.1.1旅游出行效用

假定节点间不同交通方式的旅行时间、

_(服正态分

布

，旅游者在出行过程中需要权衡旅行时间和费用来选择

交通方式。定义旅游者使用交通方式^从节点（到达节点j

的广义出行成本为

CC travel (ij # 1 D^a.r/1 (ij #2 0avel (j

( 1 '

式

中

为

费

用

一

时

间

折

算

系

数

，取

,= W〇

T

,

即出行时

间价值（VOT)

越高，,越小，反之，,越大；#1 ,##反映出游

时旅游者对交通方式的选择标准，可体现旅游者对旅行时 间和费用的偏好态度。

则旅游者广义出行成本的均值和方差分别为

£ (-CC travl (j ) # 1 £ ( T^j-aoel (ij '十 #2 ravel (j

C 2 '

Var CGClavehij ) = a\\Var ( Travel,j )

(3)

出行效用则意味着时间和金钱的损失，由于出行成本

是不确定的，可认为旅游者在做交通方式选择时会综合考 虑出行成本的均值和方差，则各种交通方式的出行效用 定义为

Uktravl ti] =$ £( CClavel ,i, ' $ 0 槡 Var CGClaEl.i,'

⑷

式中：0

为风险厌恶系数。

1.1.2旅游活动效用

旅游活动体验是获得一种接受服务和旅游经历的满足

感

，可认为旅游活动效用与旅游景点属性、旅游活动持续

时间和进行旅游活动所花费的费用有关。通常情况下，如 旅游者在景点开门前到达或到达景点后无法保证其在景点 所需的旅游活动时间内完成旅游活动，这将会产生等待或 者延误损失。因此，旅游活动效用还包括延误或等待时间 产生的负效用。

在出游过程中，当

旅

游

者

景

点

的

到

达

时

刻

、r

v

,( <

，（时，产^生的等彳寺时间T\"、 、〇pen , (

，（。当

、)Ei，(

、r(E，（ '

、+v，（时

，等 f寺时间为 〇。右

、dov ( TOra+n ( \"<^旅游活动效用函数表示为

U (、.=译人十/^2*(T@ar.。n，(）.、、..） ()

(ativity ()式中+ A,为景点（的吸引力；！

为旅游者对景点吸引力的偏

好系数；！2为旅游者对旅游活动时间的偏好系数；

为旅游

者对景点活动费用的偏好系数。

1.2优化模型的建立

进行旅游路线优化时，考虑的约束为旅游时间、费用

预算和景点服务时间约束。由于旅游城市交通网络中旅行

时间不确定性因素的影响，就产生了随机规划问题。而随

机规划问题可以用机会约束规划模型描述[70。旅游路线优 化模型如下

/ m n—1 n n—1

\\

max U = max (\"j

\"

Uravcl (

.

十

yiUaavvity , ( 7

\\ k=1 (=1 =2 (=2 f

)

(约束条件

\"\"7=1(8)

k=1 j=2

\"\"7n = 1

(9)

mk=1 (=1

n n\"

k\"

\"

4

=

1

(10)

=1 (=1 M=1

、arrvie，1

、start

(11)

\"

:

:C 'larrvLwait ,( 十 Tduration ,( 十 Ttravei，j )(arrive，j

(12)

P(、open , ( <<~. 、arrive , ( <<~. 、close , ( ) #0(13)T\"(，(

ril3.X[ C、open (( (arrive > ( ) ，〇〇

(14)T；day , ( ril3.X[ (arrive , ( (close , ( I T；irati〇n , ( ，〇 〇

(15)

/ m n—1 n n—12& \" \" \"7. Tjaei (十\"y( Ta、，（十

\\ k = 1 (=1 j = 2 (=2Tduroion , () '

Tax ) , !0 (17)

m n—1 n n—1

\"k\"\"]Tj7 Ciavl (.十

\"]yiCaai-vity，( '

C

(17)

=1 (=1 j=2

(=2

_丨1从节点（到

j

选择交通方式

k

出行 （=

(

(18)

1〇否则

1节

点

（被选中

(19)

0

否则

第40卷第2期

伍雄斌，关宏志，韩艳：随机旅行时间旅游路线优化模型及其算法

步

骤

2

开始搜索。将

• 575 •

式中：式数

/式

&)即以旅游者的旅游体验效用最大化为目标函

)

保证旅游者的出发点为住处，旅游行程

&0)要求旅游者在各路径上只选一 &1)〜

式

&2)为

景

旅点

游服

者务

的时

出间

发约

时束刻

5只蚂蚁放于起点0位置，每只

&)〜式&

蚂蚁分别进行搜索。

步

骤

3

读取当前节点编号，除起点和终点外，将未选

结束后返回住处；式种交

通

方

式

出

行

/式

中节点放入备选节点集合，基于路线的当前节点进行路线 的下一步扩展，即路线的备选节点数量为

和计算节点7到达时刻；式&3)为;

N

，在该线路的

成

式&4)〜式&5)计算旅游者在景点

z

的等待时间和延误时 当前节点之后分别插入备选点集中的节点，形

N

条路

间/式&6)〜式&7)为时间和费用预算约束；式(18)〜式 (19)为

01决策变量。

线。以选择效用最大交通方式出行为原则，采用随机模拟 方法计算备选节点集中各节点的到达时刻，判断是否满足 式（13)，同时检验备选路线的旅游时间和旅游费用是否分 2求解算法

旅游路线优化问题是

NP-Hard问

题（]，用精确算法很

难进行求解。蚁群算法是一种启发式仿生进化算法，已成 功应用于不同的领域（]。在旅游城市交通网络中，由于旅 行时间具有随机性，而随机模拟方法可依据概率分布对随 机变量进行抽样，得出问题的统计估计（0]。因此，采用 随

机

模

拟

方

法

处

理

随

机

机

会

约

束

，用

蚁

群

算

法

对

求

解

模型。

2.1

节点选择策略

蚂

蚁# 1，2,…，5)的初始解设为[T1，„]。在算法 中存

在

一

个

山

集

合

，所有当前允许访问的即满足约

束条件的景点均包含在该集合中。按

选

择

策

略

从

山

中选出节点并插入到％之前，如此反复，形成可行路线。 蚂

蚁

/在节点

Z选择节点7的策略：随机生成在（0，1)内

的变量

g

，当

g'

g。时

，根据

式

&0)选择节点/当

g

>

g。

时， 按式 &21) 选择

7 = arg L# malloawxe d ^&/)&('/)*

20)

^

，

L # allowedL

Pi7

.= (

L# allow l

• 'L

21)

0

，

l Q allowedL

式中：

是节点

z

和7间路径上的信息素•与路径有关的

启发信息函数，'7 #urw

，7 +认

^一

，7; &、*分别是信息素

因子和启发因子。

2.2

信息素更新

蚂蚁所经过路径信息素更新所采用的是局部信息素更

新规则

，

# & 一 p)，

+)0

(22)

式中：

为信息素挥发因子，# (0，1) ; )0是信息素初始值。

依据当前所得最优解，对全局信息素进行更新，更新

公式如下

，

# (1 一

p)Tij — p+Ttj

(23)

式中：

为信息素增加量。

2. 3

求解步骤

求解算法具体步骤如下：步

骤

1

读取旅游城市的交通网络数据，对求解算法的

参数进行初始化。

别

满

足

式（16)和式（17)，剔除不满足的路线和备选节 点，将

删

除

不

满

足

节

点

的

备

选

节

点

集

合

赋

予

山

。按

节点选择策略对下一个节点进行筛选。

步

骤

4

搜索的结束判断。如

山

#

0

，返回步骤

2,否则进行局部更新信息素并返回步骤3。

步

骤

5

对当前蚂蚁最优路线，全局更新路线上的信

息素。

步

骤

6

迭代终止判断。如果迭代次数达到最大代次数

如

r

，则转入步骤7，否则返回步骤2。步

骤

7

输出结果。终止算法，输出最优结果。

3算例分析

在一座城市里有多种类型的旅游目的地。如

图

1所示

的旅游交通网络包含不同类型的景点，节点间有多种交通 方式连接，各景点的属性参数取值见表1[11]。各节点间路 段旅行时间分布和费用见表2。

贯占

〇 U1謹d□〇自0△文然物风光

交餐休饮

古购迹物起闲娱乐彷点游⑶

通试 、；

、 ci、

WT

I一W W T

iiS

注：W.步行、B.公交、S.地铁、T.出租车

图

1

旅游交通网络

表1景点属性参数

景点景点等级

旅游活动时间/min

服务时间门票/元

15180[6,18]5025170817]553395[9,20]4043120[10,23]305

5100[8,20]456

4

130

[8，22]

35

• 576 •

计算机工程与设计

2019 年

表2路段旅行时间和费用

路段

步行

麵公交

賴施地铁

出租车

步行

费用元公交

地铁

出租车

0-10-20-30-40-50-61-2-31-4-5-62-32-42-52-63-43-53-64-54-65-6

———————————25/015/0——28/0—————

102/3051/1548/1467/233/1 083/2486/2574/22111/33108/32130/3822/62 /640/1239/1115/427/865/1935/1 059/1750/15

64/4 /36/45/3 /4 /7 /5 /8 /7 /83/——18/04 /16/021/05 /25/44/37/

40/1225/72 /638/112 /631/936/113 /945/1343/1355/1611/38/215/422/610/318/53 /919/635/1 021/6

———————————00——0—————

642324556672222223232

54444555556——24335454

7282133193668473799713131526121739224525

旅游者于8: 30从

处

0点

住处0点出发，预

。参

考

计文

17: 30返回住 献

[12，13]，

# 0. 05 %

看出，该模型所得的优化结果与旅游者出游的实际情况是 相符的。

，预算的旅游费用为250元

模型参数取值 〇〇 # 1、/?。# 0• 8、〇；1 # 〇# # 0• 5、

w # 0• !、/?i # 0• 2、/?2 # 0• 3、/?3 # 0. 002、

0. 15 / 景点

的吸引力用景点等级表示，在景点的旅游活动费用只有门 票如

。设定求解算法参数为

A #

1、(7 # 5

、P #

0. 1、，# 50、

r #

100、

g〇 #

0• 1、to # 0• 1。

依照求解算法，在

MATLAB

环境下编写算法程序对

建立的优化模型进行求解，得到的结果为〇3632333〇, 该路线时间安排如图2所示。在旅行时间不确定的情形下， /?。取值越大，旅游者对旅行时间的不确定性就越是规避。其余参数取值不变，当

择

# 1时，所得优化路线为〇353

图

!363〇。不同你取值的优化结果比较见表3。

从

松

表

3可看出，沐

取

0. 8时

，旅游时间预算约束较为放

表

3

不同沐取值的优化结果比较2

最优旅游路线安排

，所得优化路线的总旅游时间超出了给定的预算时间。

1时

，要求所得优化路线的旅游时间不能超出旅游

的旅游时间在预算范围内。由此可

序号

!〇旅游费用/元

旅游时间/min

当/?。取

12

0. 81. 0

141126

542515

时间预算，因此路线2

第40卷第2期伍雄斌，关宏志，韩艳：随机旅行时间旅游路线优化模型及其算法

• 577 •

[7] WU Panfeng， LIU Huiqing， PENG Jin. Uncertain program­

4结束语

本文考虑旅行时间不确定的影响，定义了以旅游出行

ming model for supermarket logistics distribution with time win­dows [J ]. Operations Research and Management Science， 2015, 24 (6): 58-64 (in Chinese).[吴攀峰，刘慧清，彭锦.

带时间窗口的超市物流配送不确定规划模型[].运筹与管

效用和旅游活动效用组成的旅游体验效用函数，以此为目 标

，建立了旅游路线随机机会约束规划模型，并设计了求

理，2015，24 (6): 58-64.]

解算法。通过算例计算，得到了最佳旅游路线方案。

在出游过程中，旅游城市交通状况复杂，不同时段的

旅行时间不尽相同，而且公共交通的车内拥挤状况也会影 [8] Gavalas D， Konstantopoulos C， Mastak

tics for the time dependent team orienteering problem: Applica­tion to tourist route planning [J], Computers \\ Operations响到旅游者的乘坐舒适度。如何量化这些因素对旅游体验 的影响，并应用在旅游路线优化模型中，是下一步需研究 的内容。

参考文献：

[1]

Gavalas D， Konstantopoulos C， MastakasK，et al. A survey on algorithmic approaches for solving tourist trip design prob­lems (].Journal of Heuristics，

2014，20 ⑶

：291-328.

[2]

GONG Dandan， WU Xiaofang. Design of special toursim route based on Hopfield algorithm A case study of Dalingshan forest park

[

J], Journal of Green Science and Technology，

2014

(5): 254-256

(in Chinese)

.[袭

丹丹，吴小芳.基于 Hopfield

算法的特色旅游路线设计以大岭山森林公园为例（].

绿色

科技

，2014 &): 254-256.]

[3]

Brilhante IR， Macedo

JA，Nardini

FM，

sightseeing tours with trip builder [J], Information Processing

\\ Management，2015，51 (2): 1-15.

[4]

WU Jincao， FAN Lijun， YAN Yawen. Multi-objective opti­mization model based on travel directions [J], Mathematics in Practice and Theory，

2016, 46 (15): 97-104

(in Chinese). [吴

劲草，范丽军，严雅雯.基于多目标优化模型的旅游路线

研究

[].

数学的实践与认识，

2016, 46 (5): 97-104.]

[5]

GUO Qiqing， LI Wei. Algorithm of tourist routes based on grey entropy decision model [

J], Computer Engineering and

Design，

2017， 38 (7)： 1988-1991 (inChinese).

[

郭奇青

，

李伟.基于灰熵决策模型的景区旅游线路规划算法[].

计算

机工程与设计，

2017, 38 (7): 1988-1991.]

[6]

Chen BY， Lam WHK， Sumalee A，

et al. Reliable shortest

path problems in stochastic time-dependent networks [

J],

Journal of Intelligent Transportation Systems，

2014，18 (2):

177-189.

Research， 2015， 62: 36-50.

[9] LUO Yabo. Topological sorting-based two-stage nested ant co­

lony algorithm for job-shop scheduling problem [J]. Journal ofMechanical Engineering， 2015， 51 (8): 178-184 (in Chi- nee).[罗亚波.面向作业车间调度的基于拓扑排序的二级嵌

套蚁群算法研究[J],机械工程学报，2015，

51 (8):

178-184K]

[0] HU Hui，GU Liqin，ZHA Weixiong. An ELECTER-based

evaluation method under uncertainty for multi-moal route selec­tion [J], Journal of Beijing Jiaotong University (Social Scie­nces Edition) ， 2017， 16 (4): 88-97 (inChinese).[胡辉，

顾丽琴，查伟雄.不确定环境下基于ELECTRE的多式联运 路径选择评价方法[],北京交通大学学报（社会科学版），

2017， 16 (4): 88-97.]

[11] et WU Xiongbin, al. GOnU A planning

N Hongzhi，HAN Yan. Tour route opti­mization model based on tourist experience under multi-con­straints [J]. Science Technology and Engineering，2018， 18 (3): 8-13 (inChinese).[伍雄斌，关宏志，韩艳.多约束下

基于游客体验的旅游路线优化模型[].科学技术与工程，

2018，18 (3): 8-13.]

[12] Li Q，Liao F， Timmermans HJP， et al. Areferencedepen-

dent user equilibrium model for multi-class activity-travel pa-­tern scheduling problems [ J ]. Transportation， 2016， 43 (6): 1061-1077.

[3] HUJihua，HUANG Ze，CHENG Zhifeng，et al. Analysis

on space-time benefit change of bus passengers? shopping in commercial center [J], Journal of Chongqing Jiaotong Univer­sity (Natural Science)， 2015， 34 (6): 101-105 (in Chi- nese).[胡继华，黄泽，程智锋，等.公交乘客在商业中心

区购物的时空效用变化分析[].重庆交通大学学报（自然 科学版），2015, 34 (6): 101-105.]