时变条件下追求最大效用的旅行规划问题

时变条件下追求最大效用的旅行规划问题 Vol . 19 , No . 4 中国管理科学第 19 卷 第 4 期 Chi ne se J o ur nal of Ma na ge me nt Scie nce A ug . , 2011 2011 年 8 月 () 文章编号 :1003 - 207 201104 - 0137 - 07 时变条件下追求最大效用的旅行规划问题 1 ,2 李金华 () 1 . 华南师范大学经济与管理学院 ,广东 广州 510006 ; 2 . 复旦大学管理学院 ,上海 200433 摘 要 :现有旅行规划问题的研究较少同时考虑旅行效用与网络时变两个因素 ,为此本文提出了一类时变条件下的旅行规划问题 ,考虑了三种约束 :旅行者在网络节点上的驻留时间及在边上的旅行时间是时间依赖的 、旅行者对 ( 网络的不同节点具有不同的偏好 、旅行者的最大旅行时间是有限制的 , 应用时间集合图 time aggregat ed grap h , ) TA G示旅行时空网络 ,建立了满足上述约束的求取最大旅行效用的旅行规划数学模型 ,并设计了相应的标号算 ( ) 法 ,最后进行了应用分析 。与采用时间扩展图 time expa nded grap h , T E G的相比 ,本方法虽然可能降低求解 精度 ,但是大幅度地减少了计算成本。 关键词 :时变 ;效用 ;时间集合图 ;标号算法 中图分类号 : T P202 , U1161 2 文献标识码 : A 优解。更通用的动态网络模型直接包含时间因素 ,1 引言[ 6 ,7 ] 网络边的行走时间是时间的函数。 有关时间依 现实生活中的许多旅行问题往往是与时间相关 赖的旅行规划问题的研究主要体现 的 ,例如旅行者在旅行途中遇到交通阻塞 ,或者在交 ( ) 在三个方面 : 时间依赖的最短路问题 TD SP P、时通节点遇到交通工具晚点 ,旅行者的旅行时间就会 ( ) 间依赖的旅行商问题 TD TSP和时间依赖的车辆 延长 ;又如在人流较大的大型参观活动中 ,每个展馆 [ 8 ] ( ) 路径问题 TDV R P。Ha mac he r 和 Ruzi ka 等 研 的排队人数是随时间变化的 ,在游客决定前往目标 ( 究了具有时间依赖性的双准则的最短路问题 Td2 展馆的时刻与游客到达展馆的时刻 ,排队人数已经 发生了变化 ,所需的等待时间也变化了 。大量的交 ) Bi SP,构建了基于离散时间依赖网络的模型 ,提出 通运输问题、应急疏散问题等问题都具有这种时变 了一个适用于非负数据 TdBi SP 的新算法。Bré u bé( ) 特征 ,而适应于经典的最短路问题 SS P、旅行商问 [ 3 ] 和 Po t vi n 等研究了一类具有时间依赖性且必经( ) 题 TSP等模型的网络表示法难以应用于解决此类 一个固定序列的若干节点的最短路问题 ,构建了基 时变网络的相应问题 。 于 T E G 的模型 , 设计了一个分解算法。魏航和李 [ 9 ] 目前先进的交通传感网络、物联网等智能化设 军等提出了一种求解时变网络下多式联运最短路 施设备 ,已经能够实时监测交通网络 、旅行网络等网 [ 10 ] 的算法。李妍峰和李军等应用动态搜索算法求 络流的动态变化 ,并且能够在智能信息系统的支持 解了 时 间 依 赖 型 旅 行 商 问 题。Soler 和 Al biach 下 ,通过统计分析、数据挖掘等手段找出网络的时变 [ 11 ] 等研究了时间依赖旅行时间/ 成本的具有时间窗 规律。合适的网络模型对时变网络数据的存储与分 的车辆路径问题的一般化 ,将这种扩展转化为非对 ( 析是 必 不 可 少 的。时 间 扩 展 图 ti me e xp a nded 称的容量限制的车辆路径问题。上述研究考虑了网 [ 1 - 3 ] ) ( grap h , T E G和时间集合图 ti me a ggre gat ed 络的时变因素 ,但是没有考虑旅行者的效用。旅行 [ 4 ,5 ] ) grap h , TA G是 离 散 时 空 模 型 的 两 种 代 表 , ( 线路设计的定向问题 t he o rie nt eeri ng p ro ble m , TA G 比 T E G 更能节省存储空间 ,并且具有更高的 [ 13 ] ) O P得到了许多学者的关注 。Va n st ee nwege n 等计算效率 ,但是应用 TA G 的算法不一定能获得最 研究了一类团体定向问题 ,设计了导引式局部搜索 [ 14 ] 和斜变邻域搜索算法 。Tricoi re 等研究多时间窗 多时段的定向问题 , 设计了可变邻域搜索算法 。 收稿日期 :2010 - 07 - 29 ;修订日期 :2011 - 04 - 26[ 15 ] Va n st ee nwege n 和 So uff ria u 等 对定向问题的研( ) ( ) 作者简介 :李金华 1972 - , 男 汉族, 湖北仙桃人 , 管理学博 究做了综述 。该类研究与旅行者的路径设计直接相 士 ,副教授 ,复旦大学管理学院博士后 ,研究方向 : 复 杂系统理论及应用.关 ,但是缺乏考虑网络的时变因素。 从以上分析可见 ,现有文献较少同时考虑旅行得到的效用 。 () 效用和网络时变这两个因素 ,对大型游览活动具体 2游客从某一入口进入 ,最后从出口离开 ,每 特征的考虑不足 。为此本文以 2010 年上海世博会 个展馆仅能参观一次 ,馆内的参观时间为已知的常 的参观活动为背景提出了一类时变条件下的旅行规 数 ,每个展馆都可直达出口 。 () 划问题。考虑了三种约束 : 旅行者在网络节点上的 3各展馆的排队时间与路段的旅行时间都是 驻留时间及在边上的旅行时间是时间依赖的、旅行 时间依赖的 ,并且时变规律已知。 () 者对网络的不同节点具有不同的偏好、旅行者的最 4在展馆的排队、参观及在路段的旅行都满足 ( ) 大旅行时间是有限制的 ,研究在满足上述约束条件 先进先出 F IFO的原则 。 () 下如何求取最大旅行效用的旅行规划问题 。 5路段的旅行时间取决于进入路段的时刻 ,即 一旦进入某路段则不再考虑该路段交通状况变化对 2 问题描述旅行时间的影响。 ( 根 据 上 海 世 博 会 官 方 网 站 ht tp :/ / () 6游客的最大参观时间是确定的 ,在该时间的) ww w1 e xpo 20101 cn/ yqkl/ i nde xn1 ht m发布的客流 () 限制下游客并不一定能完成所有展馆的参观 。 7量数据 , 本届世博会自 2010 年 5 月 1 日开园至 时间按离散时间单元来计。 问题可归纳为指() 2010 年 6 月 27 日 这是本文的撰稿时间累计入园 定起始点与目的点、具有时间 人数已经达到 19741 30 万 ,平均每日的游客数为 34 万多人 , 仅 6 月份日客流量超过 50 万人的就有 5 限制、求取最大参观效用的时间依赖网络的旅行行 天 ,一些热门场馆几乎每天都需要排队 2 个小时以 程规划问题 。 上。在这种大客流量的情景下 ,各场馆的所需的排 队等候时间是动态变化的 ,场馆之间所需的旅行时 3 时间依赖网络的表示 间也可能是动态变化的 ,如果将园区抽象为一个网 由于场馆容纳能力有限 ,在客流较多的情况下 络 ,这就构成了一个节点的驻留时间与边的旅行时 排队等候参观的现象不可避免 ,因而游客对展馆等 间都是时间依赖的时变旅行网络 。候时间的关注度要显著高于路段旅行时间 ,对时间 一般而言 ,参观世博会的大多数游客尤其是来 依赖的等候时间的忽略是不妥的 。根据上节的假 自外地的观光客 , 他们安排的参观时间是有限的 。 定 ,游客在场馆内部的参观时间是一个常数 ,为方便 游客对不同的场馆呈现出不同的偏好 ,并且更为偏 计 ,将等候时间与参观时间合并 ,统称之为节点的驻 好热门场馆。偏好值可以运用信息检索或语义识别 留时间 ,显然该驻留时间是时间依赖的 。 [ 12 ] 等技术获得,也可以通过游客直接表述获取 。毫 下面给出同时 考虑节 点与 边的时 变属性 的无疑问 ,每个游客都希望在参观期内获得尽量高的 TA G 定义 : 参观效用 ,这就意味着他们需要精心安排个人的参 观行程。 由于各种高科技手段的应用 ,目前世博会已经 ( )() 1 ta G = V , E , T , W v , W e 做到了实时采集、记录并发布园区的客流数据以及 其中 :各场馆所需排队的时间。通过对历史客流数据的进 V = { v| i ?[ 1 , n ]} 是节点集 ,表示园区各展i 一步统计分析 ,不难找出客流随时间分布的统计规 馆 , v是入口 , v 是出口 ;1 n 律 ,根据这个规律可以建立离散时间或连续时间的 E = { e| i , j ?V } 是边集 ,表示展馆间的通ij 网络模型 。游客在进入园区时通过预约系统登记个 ( ) 人的意愿场馆及意愿值 即偏好,那么在智能系统 道 ; 的支持下 ,利用已发现的客流规律 ,就可以为游客推 T 是总的时长 ; 荐客户化的参观行程 ,并发送其个人手机上 ,提升其 |i ?[ 1 , T ]} 是时间依赖的节点的= { w v W v i 参观效用 。 () 权重集 如驻留时间;为了方便下文的建模 ,对研究问题提出如下假定 : W e = { we | i ?[ 1 , T ]} 是时间依赖的边的权 i () 1游客对园区各展馆具有一定的偏好 ,偏好代 表 () 重集 如旅行时间。 游客对该展馆的参观意愿 ,也代表游客从该馆可 从定义可以看出 ,每个节点有一个权重集 ,表示 该节点在各个时刻的驻留时间序列 ; 每条边有一个 权重集 ,表示该边在各个时刻的旅行时间序列 。这 使得 TA G 可以反映出网络的拓扑结构随时间而变 化的情况 。 第 4 期李金华 :时变条件下追求最大效用的旅行规划问题 ?139 ? ( ) ( ) 作为一个例子 ,图 1 a , b , c显示了三个时刻用图 1 d的形式表示这种动态网络 ,在该图中边 e34的网络 ,该网络的拓扑结构与属性是随时间而改变 的属性[ 1 , ?,4 ]表示边的权重序列。又如节点 v,1 的。例如边 e在时刻 1 ,3 是存在的 ,在时刻 2 不存 34 ( ) 在时刻 1 ,2 ,3 的权重分别是 2 , 2 , 3 ,在 d中用[ 2 ,在 ,它的权重在时刻 1 是 1 ,在时刻 3 变为 4 。TA G 2 ,3 ]来表示其三个时刻的权重。 ( ) 图 1时间集合图 TA G图解 ( ) ( ) ( ) ) ( P v, v= { t, v, t, v,, t, v }1 n 1 1 2 2 n n 4 数学模型 表示起始节点 , v表示目标节点 , t 表其中 : vi 1 n 41 1 符号与变量定义 示游客达到节点 v的时间。i 41 3 数学模型T :总的时长 ; T n- 1 v:网络中下标为 i 的节点 ;i ( ) ()ma x z = px t,2 i ij ??? e: 网络中 v连接节点 v 的边 ;( ) ij i j t = 1 i = 2 j ?S iT T n : 网络总的节点数 ;( )x( ) ()s1 t1 t = = 1 , 3 1x in tj ? ?? ?( ) ( ) t = 1 j ?S 1t = 1 i ?P n ( ) P i: v的前驱节点集合 ; i T T ( ) S i: v的后继节点集合 ; i ( )( ) x tx t, k ik kj ? [ 2 , n -= ? ?? ?( ) ( ) t = 1 i ?Pkt = 1 j ?S k t:到达 v的时刻 ;i i ()4 1 ] , ( ) w v i t:时刻 t 到达时 v i 的驻留时间 ;T ( ) we t:时刻 t 进入时 e 的旅行时间 ;( )ij ij ()5 1 ] , x ij t?1 , j ?[ 2 , n - ? ?( ) t = 1 i ?Pj ( ) x t:时刻 t 是否进入 e , 进入则为 1 ,否则为ij ij T ( )()x ij t6 1 ] , ?1 , i ?[ 2 , n -0 ; ??( ) t = 1 j ?S i T p:对 v的偏好值 ,取[ 0 ,10 ]之间的整数 ;i i ( ( ) ) ( ) t + we ij t?x ij t= t , j ?[ 2 , n ] ,j 41 2 参观行程的表示? ?( ) t = 1 i ?Pj 以时间、空间两个维度表示游客的参观行程 ,游 ()7 T ( ) 客的行程是一个由二元组 t, v构成的列表 ,二元i i t ?x t ?t+ w v t, i ?[ 1 , n - 1 ] ,( ) ( ) ij i i i ??( ) 组 t, v表示某游客在时间 t到达节点 v 。活动行 i i i i ( ) t = 1 j ?S i ()8 程如下所示 : ( ) x t?{ 0 , 1} , i , ?[ 1 , n ] , j ?[ 1 , n ] , t ?[ 1 ,Q 选择满足最大时间约束的具有最大行程效用的节ij ()点并根据规则更新其后继节点的标号 ,且将满足条 T ] , 9 ()10 件的后继节点加入 Q , 依次迭代直到 Q 为空为止 ; 1 ?ti ? T , i ,?[ 2 , n ] , ()t= 1 。 11 根据最大效用节点的标号 ,逆向回溯得到最大效用 1 其中 : 行程。该算法依循了动态规划的思想。 () 式 2为目标函数 ,游客参观效用最大 ;下面给出具体的算法 : () () 式 3、4表示节点 1 是起点 ,节点 n 是终点 ;Inp ut : () () 式 5、6表示除起点和终点之外的其他每个 输入各节点的驻留时间集 W v 、边的旅行时间 节点最多被访问一次 ; 集 W e 、游客对各节点的偏好值 p;i () 式 7表示当经过 e时 ,达到 v 的时间等于进 ij j 起始点 v1 与目的点 vn 是必经点 , p1 = 0 、p n = 入 e 的时间加上 e 的旅行时间 ; ij ij 0 、w v = 0 、w v = 0 ; 起始时间为时刻 1 。1 n () 式 8表示当经过 e时 ,进入 e的时间大于等 ij ij 考虑到实际中任何一个展馆都可以到达出口 , 于到达 v 的时间加上 v 的驻留时间 ;i i 假设游客从任何一个展馆出来后都可以立即到达出 () 式 9是决策变量 ,表示时刻 t 是否通过 e , 通 ij 口 ,即任一节点到达出口的旅行时间为 0 。如果不 过为 1 ,不通过为 0 ; 做该假设 ,在很多情况下将会出现无解 ,因为当达到 () 式 10表示时间的取值范围 ;最大时长时 ,游客所在的节点可能并没有通路连接 () 式 11表示达到 v的时间 ,即初始值。1 到出口。 O utp ut : 5 算法设计 满足最大时长限制的具有最大行程效用的行 在本文的模型中 ,网络的每个节点具有一个权 程。 重序列和一个偏好属性值 ,每条边具有一个权重序 Met ho d : 列 ,模型的目标是要找出具有最大参观效用的行程 , St ep 1 :在起始点 v, u= 0 , Q = { v} , 标号为1 11 问题可转化为求取满足时变条件的 、从起始节点到 ( ) 0 , 1 , 1 , 0, 节点 v0 为节点 v1 的虚拟前驱点。其他目的节点的最大偏好路径的问题 ,这在本质上与最 短路问题类似。借鉴求解最短路问题的标号算法的 所有节点的最大行程效用 u= 0 , Π j ?1 。j St ep 2 :判断集合 Q 是否为空 ,如果为空则跳转 思想 ,本文提出一个求解上述模型的标号算法。 至 St ep 5 ,否则取出集合 Q 的最大行程效用最大的 下面先对算法中的相关符号与定义进行说明 :元素 v , 如果效用相同则取离开时间最早的节点 , i ( ) 1te 表示离开节点 v 的时刻 ,也是进入 v后 i i i 并将它从 Q 中删除。 继边的最佳时刻 ,满足 : ( ) St ep 3 :对 vi 的后继点集合 { v j |j ?S i} 中的 ( ( ) ) ( ) ()12 min tei + weij tei , tei ?[ ti + wv i ti , T ] 所有元素 ,循环执行如下子步骤 : ( ) ( )()ti = te k + we ki te k , k ? P i13 ( ) St ep 3 - 1 : 12 按式 计算进入 e的最佳时刻ij ( )u表示到达节点 v 并参观完后的游客最大2 j j te ; i 行程效用 ,满足 :() St ep 3 - 2 :按式 13计算到达 v j 的时刻 t j ; ()14 ( )u= ma x u+ p j i j () St ep 3 - 3 :按式 12计算离开 v 的时刻 te ;j j ( ) i ?Pj ( ) Step3 - 4 :如果 t+ wv t? T 并且 uu+ j j j j i 注 :由于存在排队等候的现象 ,游客达到某节点< ( ) p, 则 :令 u= u+ p,更新 v的标号为i , t, te , u,并不一定能立刻进入参观 ,所以节点的效用只有在 j j i j j j j j 如果 v不在 Q 中 , 则从 v开始进行路径回溯 ,如果 vj j j参观完成该节点后才能获取。 ()( ) 3 i , t , te , u表示 v 的标号 , 分别由最大没有在此回溯路径中再次出现 ,则 vj 进入 Q。j j j j 效用前驱节点下标 i 、到达 v 的时刻 、离开 v 的时刻Step4 :跳转至 Step2 。j j St ep 5 :找出满足最大时长限制的最大行程效 与该节点的最大行程效用组成 。 () 用。根据标号从目的点回溯路径 ,得到游客的参观 4Q 表示待处理节点的优先队列。 算法的 行程。如果存在多个最大效用相等的行程则取用时 基本思想是 : 从起始点出发对各节点进 行标号 ,该标号记录游客从起始点到该节点的前驱 最少的最大效用行程为最优行程 。 算法的复杂性 节点、达到时刻 、离开时刻与最大行程效用 ; 每次从 分析 : 该算法的计算复杂性略大 第 4 期李金华 :时变条件下追求最大效用的旅行规划问题 ?141 ? 于最短路问题的标号设定法。出口 ,其他节点为展馆 ,出口可与任一展馆相连 ,并 且展馆到出口的旅行时间全部为 0 。总的时长 T =6 应用分析10 , 时刻 1 为初始时刻。各个节点的驻留时间序列 61 1 算例分析 与各个边的旅行时间序列已标示在图中。入口与出 假设某展览园区的网络简图如图 2 所示 ,图中 0 ,所有节点的初始效用均设为 0 。口的驻留时间为 共有 7 个节点 ,节点 v为园区入口 ,节点 v为园区某游客对各节点的偏好值也标示在图中。1 7 图 2 时间依赖网络图例 详细的计算过程见表 1 。在表 1 中 : 集合 Q 列:引导服务的设计方法如下 中带下划线的元素表示本次迭代被选出的节点 ; 各 St ep 1 :抽象出上海世博会园区的网络简图 , 将 节点列中斜体的标号表示本次迭代发生了标号更 每天的开园时间离散化为时间序列 ; St ep 2 :每天定时统计开园至今各场馆在各时刻 新 ,带删除线的标号表示本次迭代因超时而不更新 。 ( ) ,在节点 v6 的行程效用最大 u6的平均等候时间、参观时间 ,以及主要道路的平均移 可以看出 = 13, 由 于从 v到出口 v行程效用不变 ,旅行时间为 0 ,所动时间 ,将这些统计数据转化为网络图的时变权重 ; 6 7 St ep 3 :对需要该项引导服务的游客在入园前采 以 v的标号实际上等同于 v的标号 。根据节点的 6 7 标号进行逆向回溯得到最优行程 : 集其游览意愿及偏好 ; ( ) ( ) ( ) ( ) ( ) P v, v= { 1 , v, 2 , v, 5 , v, 9 , v, St ep 4 :应用前面的求解算法计算该游客的游览 1 7 1 3 5 6 ( ) 10 , v}行程 ,并反馈给该游客。 7 在实际应用中 ,可将上述主要过程编制为计算 即该游客按行程参观可得到最大行程效用 u7 机软件系统 ,实现该过程的自动化。 = 13 , 共耗时 10 个时间单元 ,其中节点 v、v没有 2 4 被参观。 7 结语本算法也适用于求解不考虑最大时长约束的旅 行规划问题 ,以及只考虑时变旅行时间或者时变驻 现实生活中的旅行活动常常充满了诸多的不确 定性 ,路上堵车 、服务排队的情况常常为旅行者所抱 留时间的旅行规划问题。例如本例在不考虑最大时 怨 ,而现有旅行规划问题的研究文献较少同时考虑 ( 长约束的情况可得游客参观效用值为 19 即将所有 旅行效用和时变这两个因素 。基于此 ,本文做了如 ) 效用值 相加, 参观路 线为 : { v, v, v, v, v, v, 1 2 3 5 4 6 下工作 : v} 。7 () 1以上海世博会的参观为背景 ,提取了此类大 61 2 针对上海世博会的应用分析型游览活动旅行问题的一般特征 ,即三种约束 :旅行 上海世博会及其他大型展览活动一般人流较 者在网络节点上的驻留时间及在边上的旅行时间是 大 ,游客需要长时间的等候 ,容易引起游客的抱怨甚 时间依赖的 、旅行者对网络的不同节点具有不同的 至引发事故 ,降低活动的质量 ,因而可以针对一些特 偏好、旅行者的最大旅行时间是有限制的 ;() 定人群 如老弱残 、V IP 等提供个性化的引导服务 , 应用本文的方法可以实现该引导服务。 表 1 计算过程表 V V V V V V 1 2 3 4 5 6 迭代次数Q p = 0 p = 1 p = 3 p = 5 p = 8 p = 2 V 1 ( ) 1 0 , 1 , 1 , 0- V , V 2 3 ( ) ( ) ) ( 2 0 , 1 , 1 , 01 , 2 , 4 , 11 , 2 , 3 , 3- - V , V 2 5 ( ) ( ) ( ) ( ) 3 0 , 1 , 1 , 01 , 2 , 4 , 11 , 2 , 3 , 33 , 5 , 7 , 11- - V , V 2 6 ( ) ( ) ( ) ( ) ( ) 4 0 , 1 , 1 , 01 , 2 , 4 , 11 , 2 , 3 , 33 , 5 , 7 , 115 , 9 , 10 , 13- - V 2 ( ) ( ) ( ) ( ) ( ) 5 0 , 1 , 1 , 01 , 2 , 4 , 11 , 2 , 3 , 33 , 5 , 7 , 115 , 9 , 10 , 13- V , V 3 4 ( ) ( ) ( ) ( ) ( ) 6 ( ) 0 , 1 , 1 , 01 , 2 , 4 , 12 , 5 , 6 , 43 , 5 , 7 , 115 , 9 , 10 , 132 , 7 , 9 , 6- - V 3 ( )( )( )( )( )( )7 0 , 1 , 1 , 0 1 , 2 , 4 , 1 2 , 5 , 6 , 4 2 , 7 , 9 , 6 3 , 5 , 7 , 11 5 , 9 , 10 , 13 - ( )( )( )( )( )( )8 0 , 1 , 1 , 0 1 , 2 , 4 , 1 2 , 5 , 6 , 4 3 , 5 , 7 , 11 5 , 9 , 10 , 13 2 , 7 , 9 , 6 mar y of Result s [ C ] . In : Proceedings of Inter natio nal () 2建立了考虑这三种约束的求取最大旅行效 Sympo sium o n Sp atial a nd Tempo ral Data ba se s 用的旅行规划问题的数学模型 ,并借鉴最短路问题 ( ) SS TD07, Berli n Heidel ber g : Sp ringer2Verlag , 2007 : 的标号算法设计了求解该问题的标号算法 。相对于 460 - 477 . 采用 T E G 的方法而言 , 该方法虽然可能降低求解 [ 5 ] Geo r ge , B . , Shekha r , S. . Time aggregated grap hs : a 精度 ,但是大幅度地减少了求解的计算成本 ;mo del fo r sp atio2tempo ral net wo r k [ J ] . J o ur nal o n Se2 () 3对算法的有效性做了算例验证 ,并针对方法 mantic s of Data , 2008 , Vol ume XI , 11 :191 - 212 . [ 6 ] 谭国真 , 高文. 时间依赖的网络中最小时间路径算法 在世博会的应用进行了分析 ,提出了应用的一般程 () [J ] . 计算机学报 ,2002 , 25 2: 165 - 172 .序。 [ 7 ] 谭国真 , 柳亚玲 , 高文. 随机时间依赖网络的 K 期望最 本文讨论的引导方法主要适用于参观人流量较() 短路径 [J ] . 计算机学报 , 2003 , 26 3: 323 - 331 . 大、常常需要排队等候的场景。在该场景下 ,引导方 [ 8 ] Hamacher , H . W. , Ruzika , S. , Tja ndra , S. A . . Al2 () 法的应用有三个注意事项 : 1需要及时更新网络图 go rit hms fo r ti me2dependent bicriteria sho rte st pat h ( ) 的时变权重 ,保持时变规律的时效性 ; 2只能为部 p ro blems [ J ] . Di screte Op timizatio n , 2006 , 3 : 238 - 分人群提供引导服务 ,否则会违背之前的时变规律 , 254 . () 导致方法失效 ; 3为提供实时的引导服务 ,需要编 [ 9 ] 魏航 , 李军 , 刘凝子. 一种求解时变网络下多式联运最 制相应的计算机系统。该方法的局限是 : 在人流量 () 短路的算法[J ] . 中国管理科学 , 2006 , 14 4: 56 - 63 . 大的情况下不能为多数游客提供该项引导服务 ,这 [ 10 ] 李妍峰 , 李军 , 赵达. 动态搜索算法求解时间依赖型 也是需要进一步研究的地方。另外 ,虽然在人流量 ( ) 小的场景下也可应用本引导方法 ,然而应用的意义 旅行商问题研究 [J ] . 控制与决策 , 2009 , 24 2: 274 就不突出了。 - 278 . [ 11 ] Soler , D. , Al biach , J . , Ma rtínez , E. . A way to op ti2 mally solve a time2dep endent Vehicle Ro uting Pro blem wit h Time Windo w s [J ] . Operatio ns Re sea rch L et ter s , 参考文献 :2009 , 37 : 37 - 42 . [ 12 ] So uff rian , W. , Vansteenwegen , P. , Verto mmen , J . , [ 1 ] Ka uf man , D. , E. , Smit h , R. , L . . Fa stest p at h s in et al . A per so nalized to uri st t rip de sign algo rit hm fo r time2dep endent net wo r k s fo r intelligent vehicle highway mo bile to uri st guides [ J ] . Applied A rtificial Intelli2 () systems applicatio ns [J ] . IV H S J o ur nal , 1993 , 1 1: 1 () gence , 2008 , 22 10: 964 - 985 . - 11 . [ 13 ] Vansteenwegen , P. , So uff ria n , W. , Vanden Ber ghe , [ 2 ] Ko hler , E. , L angt au , K. , Skut ella , M . . Time2ex2 G. ,Va n O udheusden , D. . A guided local sea rch meta2 pa nded Grap hs fo r Flo w2dependent Tra nsit Times [ C ] . heuri stic fo r t hen tea m o rienteering p ro blem [J ] . Euro2 In : Proc. 10t h A nnual Europea n Sympo sium o n Algo2 ( ) pea n J o ur nal of Operatio nal re sea rch , 2009 , 196 1 : rit hms , 2002 : 599 - 611 . 118 - 127 . [ 3 ] Bér ubé, J . F. , Po t vin , J . Y. , Vaucher , J . . Time2de2 [ 14 ] Tricoire , F. , Ro mauch , M . , Doer ner , K. F. , Ha rtl , pendent sho rtest pat h s t hro ugh a fixed sequence of R. F. . Heuri stic s fo r t he multi2p erio d o rient eering no de s : applicatio n to a t ravel pla nning p ro blem [ J ] . p ro blem wit h multiple ti me windo w s [J ] . Co mp uter s & Co mp uter s & Op eratio ns Resea rch , 2006 , 33 : 1838 - Operatio ns Re sea rch ,2010 ,37 :351 - 367 . 1856 . [ 4 ] Geo r ge , B . , Kim , S. , Shekha r , S. . Sp atio2t empo ral [ 15 ] Vansteenwegen , P. , So uff ria u , W. , O udheusden , D. V . . The o rienteering p ro blem : A survey [J ] . Europea n Net wo r k Data ba se s and Ro uting Algo rit hms : A Sum2 第 4 期李金华 :时变条件下追求最大效用的旅行规划问题 ?143 ? J o ur nal of Op eratio nal Re sea rch , 2011 , 209 :1 - 10 . Time Varying Travell ing Plann ing Problem f or Ma ximal Ut il ity 1 , 2L I Jin2hua (1 . School of Eco no mics & Ma nagement , So ut h China No r mal U niver sit y , Guangzho u 510006 , China ; )2 . School of Ma nagement , Fuda n U niver sit y , Sha nghai 200433 , China Abstract : The c ur re nt re sea rc he s o n t ra velli ng p la nni ng p ro ble m ha r dl y co n si de r bo t h utilit y a nd ti me va r2 yi ng. So t hi s p ap e r p ropo se s a ti me va r yi ng t ra velli ng p la nni ng p ro ble m , w hic h co n sider s t hree co n2 () ( ) st rai nt s : 1No de ’s re si di ng ti me a nd e dge ’s t ra velli ng ti me a re ti me dep e nde nt i n net wo r k s ; 2 t he () t ra velle r ha s diff ere nt p ref e re nce fo r each no de ; 3The ma xi mal t ra velli ng ti me i s li mit ed. The t a velli ng ( ) net wo r k s a re rep re se nt e d by ti me a ggre gat ed grap h s TA Gfi r st l y. The n , a mat h matical p la n ni ng mo del fo r t he p ro ble m i s p ropo sed , a nd a la bel met ho d i s de si gned . Fi nall y , a n e xa mp le i s de mo n st rat ed a nd t he ( ) app licatio n i s di sc u sse d. Co mp a re d to ti me e xp a nded grap h T E G, t he app roac h may ha s subop ti mal sol u2 tio n , but it reduce s t he co mp ut atio nal co st si gnifica nt ly . Key words : ti me va r yi ng ; utilit y ; ti me a ggre gat ed grap h ; la bel met ho d