时变条件下追求最大效用的旅行规划问题
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游客对园区各展馆具有一定的偏好 ,偏好代 表
() 重集 如旅行时间。 游客对该展馆的参观意愿 ,也代表游客从该馆可 从定义可以看出 ,每个节点有一个权重集 ,表示 该节点在各个时刻的驻留时间序列 ; 每条边有一个
时变条件下追求最大效用的旅行规划问题
