教育事业统计培训
智能规划,让旅行更简单
2013-04-02
作者:胡建强
 
复旦大学管理学者研究为智能地实现旅游路线规划提供了一种可行的解决方案。借助互联网,基于旅行偏好,同时兼顾预算和时间约束,智能地为旅行者规划出最优旅游路线,满足旅行者个性化的需求。
关键字:旅行规划问题,团队定向问题,混合整数线性规划,启发式算法,局部搜索

    在互联网时代,越来越多的旅行者希望通过网络来规划自己的行程。想去哪儿玩,先看看“部落格”(BLOG),通过网络关键词搜寻旅游信息;在各旅行社网站上对行程和报价进行比较;通过社区、微博等途径与有经验的网友交流旅游攻略;通过网络购买旅游商品;旅行结束后,在网络上分享旅游经验……网络提供了大量的旅游服务,众多推荐系统也应运而生。2008年推出的旅行推荐系统(TRS)应用人工智能调用已存的信息,兼顾旅行者的偏好、时间与资金约束,通过算法给旅行者提供建议。日益强大的计算机和网络似乎可以为人们做出整一套旅程规划,但事实是否真的如此呢?

    不同的旅行推荐系统算法相异,但基本原理却是一致的。例如旅行者要选择一家旅馆入住。首先,旅行者输入自己对于旅馆的偏好,如离景点近、三星级以上等等。系统搜寻出符合要求的旅馆,并基于以往的数据对这些旅馆进行排序。旅行者可以根据排序后的旅馆清单做出选择。这样的服务相信大家在携程等网站上都体验过。

    不论哪种TRS系统,都需要一个庞大的前人评价与经验的数据库。旅行推荐系统更像是一个电子记录簿,记录旅行者们在每个单项旅行产品(如旅馆和交通等)上的选择,缺乏整体规划的技术支持。尽管一些网站声称它们有提供旅程规划的功能,但事实上只有现成的前人用过的旅程方案,并不能智能地为旅行者规划出最优或者较优的旅游路线。

    当规划问题规模不大时,这类旅行规划问题可以用整数规划精确求解,但需要花费大量的时间。当可选择旅馆、景点的数目比较大时,求解就变得非常困难。为此,我们设计了一种高效的近似算法来求解该问题,能够在一秒至数秒内为旅行者规划出合理的较优的旅游路线,我们也给出了一些样本运行检测数据,证明了算法的优化效果良好。

    我们构建了一个整数线性规划问题,以时间和资金为约束条件,以最大化旅行者效用函数为目标,为旅行者找出最佳景点组合以及相应的旅游路线。其中效用函数因个人具体偏好而定,给予符合偏好的景点更大的权重。例如比起历史景观,某旅行者更偏好自然景观,那么对于这个旅行者而言,去颐和园效用比去故宫的效用要高。另外,我们假设旅行者只选择一家旅馆,每天从这家旅馆出发旅行并返回。

    计算方法由两部分组成:旅馆选择(模块1)和路线规划(模块2)。在模块1旅馆选择方面,所有旅馆根据地域被分为R组,每组旅馆个数不得大于一个给定的上限,如不满足则继续划分。然后,我们在每组中分别随机抽取一家旅馆,基于每家抽取到的旅馆,分别计算从该旅馆出发的最佳路线(使用模块2路线规划)。比较这些最佳路线,我们选出旅行者效用最大的那一家旅馆(比如为A),并基于其所属组中剩余的旅馆(比如为B、C),分别计算从这些旅馆(B和C)出发的最佳路线,最后,从A、B和C三个旅馆出发对于旅行者来说效用最高的旅游线路即为最终方案。

    那么在模块2路线规划中具体是怎样操作的呢?首先应用一定的算法(贪婪算法)(线规划说馆,并对效用得到一个满足时间和费用约束的初始路线规划方案。为了提高这个初始路线规划为旅行者提供的效用,我们先根据一定的法则,在不同天的旅游路线之间进行景点调换,并调整同一天的旅游路线中景点的游览顺序,以达到压缩旅行时间为进一步增加旅游景点提供可能。然后,在仍满足条件约束的前提下,通过景点插入和调换来提高总效用,经过设定的有限迭代步骤,最终得到最大化效用的游览方案。

    出于算法的随机性,我们对每一个案例分别做10次模拟实验,平均运行时间为6.7秒,并取所有试验中目标效用函数值的平均数作为最终结果。

    团队定向问题是旅行规划问题的简化,我们的算法也能用在团队定向问题上,在现有的研究团队定向问题的文献中,Ke 等人(2008)和 Vansteenwegen等人(2009)的方法是最有效的。不妨与他们的实验结果进行比较。Ke等人的算法结果比我们的好0.89%,但是运行时间远远超出(26.0秒),而且他们使用的是速度更快的电脑。Vansteenwegen等人也使用了比我们更快的电脑,运行了10.3秒,而我们的目标函数结果高出0.23%。由此可见我们的算法是非常有效的。

    我们的研究为智能地实现旅游路线规划提供了一种可行的解决方案。基于此,可以开发出更复杂、满足旅行者更多个性化需求的互联网旅游规划产品。


改写作者:朱晨波,陈星宇  编辑:潘 琦

本文改写自论文On the tour planning problem,朱晨波(复旦大学),胡建强(复旦大学), 王逢春(IBM中国实验室),徐以汎(复旦大学),曹荣增(IBM中国实验室)发表于Annals of Operations Research。
相关内容
人物档案
胡建强
复旦大学管理学院  管理科学系教授
研究方向:离散事件系统、仿真模拟、排队论、供应链管理、金融衍生产品定价和风险控制
徐以汎
复旦大学管理学院  管理科学系教授/系主任
研究方向:服务管理,收益管理,供应链管理,最优化方法及应用
FBK百科
【整数规划】
是指一类要求问题中的全部或一部分变量为整数的数学规划。是近三十年来发展起来的、规划论的一个分支. 整数规划问题是要求决策变量取整数值的线性规划或非线性规划问题。
视频
关于我们
关于复旦商业知识(FBK)
复旦商业知识(Fudan Business Knowledge,简称FBK)是传播与分享创新型知识产品的综合媒体平台,由复旦大学管理学院商业知识发展与传播中心创建。
以“思维构架未来”为核心理念,依托复旦大学丰厚的学术底蕴,FBK致力于通过其原创报道和整合资讯服务,深入解读当下商业热点,转化学者研究成果,与商业菁英和社会公众分享国际国内先进的管理思想与实践经验,发现中国本土商业新生力量;同时亦重视社会责任意识与人文修养的全面提升。
FBK旗下平台包括:FBK在线(bk.fudan.edu.cn)中、英文频道,iFBK移动互联平台,FBK TV节目及衍生出版物,《管理视野》杂志,“复理学堂”以及复旦管理案例库等。
其中,iFBK微平台囊括安卓及iPhone/iPad 应用、微博、微信公众账号等多种传播方式,针对移动用户量身设计精品内容,带来革新性的阅读体验。
《管理视野》杂志是新一代的商业管理读本,由复旦大学管理学院和中国管理研究国际学会(IACMR)联袂出品,秉持“管理推动中国进步”的理念,促进管理思想与实践对话,致力于成为中国管理学界及商界的思想源动力。
复理学堂是一个在线学习平台,包括对学生和校友开放的预备课程、第二课堂等,以及为企业人群定制的移动学习课程。
关于商业知识发展与传播中心(KDCC)
商业知识发展与传播中心(Business Knowledge Development and Communication Center,简称KDCC),是创新型的综合性知识产品研发、出品与传播机构,由复旦大学管理学院于2010年创立。
KDCC以“传播管理思想、分享实践智慧”为宗旨,致力于成为学院、企业及社会各界人士的沟通桥梁,联结并吸纳社会各界最优势资源,促进前沿管理理念与当下商业实践的对接与融通,并成为社会公众分享商业思想与企业经营智慧的终身学习平台。
KDCC分享资源:
复旦商业知识(FBK)平台:无边界的网络商学院、随时随地的在线学习;
案例开发与研究:以发展中国本土化案例和促进中外商学院案例教学与科研交流为愿景,提供案例线索、资金支持、数据协助、版权推广管理等案例开发服务,同时为本土企业的成长及海外企业在中国市场的发展提供有实践指导意义的借鉴。
FBK学术顾问
薛求知:
复旦大学管理学院企业管理系教授,主要研究方向为企业国际经营、跨国公司管理(战略、营销)、企业集团、国际商务管理、大公司变革、集团的管理和控制以及欧洲企业研究。对管理学与经济学、社会学交叉的一些跨学科问题也有较大的兴趣。
蒋青云:
复旦大学管理学院市场营销系主任、教授,主要研究方向为营销渠道、组织间营销、市场营销理论,及中国企业营销战略。
胡奇英:
复旦大学管理学院管理科学系教授,主要研究方向为供应链管理、商业模式,及服务管理。
徐 莉:
复旦大学管理学院财务金融系副教授,主要研究方向为公司金融、金融市场,及金融机构。
孙 霈:
复旦大学管理学院产业经济系副教授,主要研究方向为公司治理、产业组织、产业政策,及战略管理。
KDCC团队
主任: 于保平

复旦商业知识主编: 程亚婷

课程开发总监: 王颖颖

运营与推广总监: 陈颖燕

编辑: 潘琦 黄漪 黄颖 宋旸

案例研究员: 陈扬波 杨华颖

视觉设计: 戴云

行政: 马晓楠

欢迎关注FBK - 复旦商业知识
官方网址: http://www.bk.fudan.edu.cn
官方微博:(新浪) http://weibo.com/fudankdcc
官方微信:公众号“复旦商业知识“
APP下载:
联系我们
编辑部
上海市国顺路670号复旦大学管理学院李达三楼615室
电话:8621-25011379
新浪微博:http://weibo.com/fudankdcc
腾讯微博:http://t.qq.com/kdcc_fudan
案例中心
电话:8621-25011388
Email:caseinst@fudan.edu.cn
读者服务:
电话:8621-25011378
Email:bkservice@fudan.edu.cn
市场合作
电话:8621-25011387
Email:bk@fudan.edu.cn
合作伙伴
版权所有
版权所有
复旦商业知识在线网站(包括移动终端)的所有内容,包括视频、文章、图片等均由复旦商业知识在线www.bk.fudan.edu.cn拥有版权或由内容合作伙伴授权提供,未经复旦商业知识在线书面许可,对于复旦商业知识在线拥有版权和/或其他知识产权的任何内容,任何人(包括博客及个人空间)不得复制、转载、摘编或在复旦商业知识在线所属的服务器上做镜像或以其他任何方式进行使用。一经发现,本网将依法追究责任。
复旦商业知识在线社区,以及评论问答的内容(包括文章、问题及问题回答等各种形式的内容)版权由内容发布者所有,未经内容发布者许可,对于发布者拥有版权和/或其他知识产权的任何内容,任何人(包括博客及个人空间)不得复制、转载、摘编或在复旦商业知识在线所属的服务器上做镜像,或以其他任何方式进行使用。
复旦商业知识在线严禁内容提供者复制、转载、摘编或以其他任何方式在复旦商业知识在线评论或社区中发布了他人拥有版权或其他知识产权的内容,严禁一切侵犯他人的版权或知识产权的行为。
凡复旦商业知识在线、社区或移动终端内容中注明“来源:XXX”的文/图等稿件,转载出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。
转载声明
1. 已经本网站协议授权的媒体、网站或获得书面授权的第三方,在引用、下载或转载使用时必须注明“稿件来源:复旦商业知识在线BK.fudan.edu.cn(XX频道)”字样,违者本网将依法追究责任。
2. 本网站内容中涉及复旦管院内外专家学者人物的观点和著作,引用、下载或转载中如有使用需做出和本网站一致的标注,不得随意隐匿、修改。
3. 本网站以下内容亦不可任意转载:
a. 本网所指向的非本网内容的相关链接内容;
b. 已作出不得转载或未经许可不得转载声明的内容;
c. 未由本网署名或本网引用、转载的他人作品等非本网版权内容;
d. 本网中特有的图形、标志、页面风格、编排方式、程序等;
e. 本网中必须具有特别授权或具有注册用户资格方可知晓的内容;
f. 其他法律不允许或本网认为不适合转载的内容。
4. 转载或引用本网站内容必须是以知识性或资料性公共免费信息为使用目的的合理、善意引用,不得对本网站内容原意进行曲解、修改,并自负版权等法律责任。
5. 转载或引用本网内容不得进行如下活动:
a. 损害本网或他人利益;
b. 任何违法行为;
c. 任何可能破坏公秩良俗的行为;
d. 擅自同意他人继续转载、引用本网内容。
6. 转载或引用本网中的专家学者及其他署名文章,请按规定或咨询协商向作者支付稿酬。
7. 对于不当转载或引用本网站内容而引起的民事纷争、行政处理或其他损失,本网站不承担责任。
8. 对不遵守本声明或其他违法、恶意使用本网站内容者,本网站保留追究其法律责任的权利。
网站地图
首页
特写|热点观察|学术发现|产业|人文|TV
热点观察
声音|政经|管理|创业|职场|专栏
学术发现
战略与变革|领导力与组织|市场营销|信息系统|运营|金融/投资|公司治理
产业
科技/创新|零售/流通|时尚/创意|旅游/会展|金融/地产|制造业|可持续|研究报告
人文
读书|管理人生|文化|生活方式
TV
专访|圆桌|公开课
关注FBK
官方网址: http://www.bk.fudan.edu.cn
官方微博: http://weibo.com/fudankdcc(新浪)
官方微信:复旦商业知识(账号BKfudan)
付费会员服务
请输入真实Email下载《管理视野》:
此下载服务仅供付费会员个人研究,本刊保留所有版权,文字和图片未经版权方书面批准,不得以任何方式转发或使用。
联系我们
上海市国顺路670号复旦大学管理学院李达三楼615室
电话:8621-25011379
新浪微博:http://weibo.com/fudankdcc
腾讯微博:http://t.qq.com/kdcc_fudan
读者服务
电话:8621-25011378
Email:bkservice@fudan.edu.cn
市场合作
电话:8621-25011387
Email:bk@fudan.edu.cn
关于我们 联系我们 合作伙伴 版权所有

复旦大学管理学院版权所有  www.fdsm.fudan.edu.cn