基于服务时间约束的在线旅行商问题研究

发布时间：2017-12-23 11:58

  本文关键词：基于服务时间约束的在线旅行商问题研究　出处：《西安交通大学》2017年博士论文　论文类型：学位论文

  更多相关文章： 服务时间约束 旅行商问题 在线算法 竞争分析

【摘要】：针对现实中的快餐送餐,快递收件员取件以及出租车等上门服务中存在的提前预订和顾客等待心理,探讨了基于服务时间约束的在线旅行商问题;并分别根据服务目标是最小化成本,最大化利润还是综合考虑两种目标的情形下对问题进行了分析。论文主要做了以下四方面的工作:1)研究了基于预知信息的在线Nomadic旅行商问题。针对现实中服务人员进行服务之后不必返回出发点的现象,将服务预订通过预知信息引入到旅行商问题当中,探讨了当服务器的目标为使成本尽可能小在线旅行商问题,并且对问题进行了竞争分析。通过构建特殊的网络结构给出了问题的下界,并且分别在直线网络上设计了ENO-dd算法,分析了算法的竞争比;在一般网络上设计了GTR-dd算法,给出了算法的竞争比。通过比较分析发现,在线服务器的竞争性能与预知信息具有正向关系。同时预知信息量的多少还控制着问题的占线性。2)研究了基于服务选择和时间约束的在线旅行商问题。考虑到现实中的顾客等待服务的等待心理以及顾客满意度,将服务时间约束引入到具有服务选择性的在线旅行商问题中。旅行商如果没有在规定的时间约束内对服务请求进行服务,则会产生惩罚。现实中惩罚可以表现为名誉受损或者是服务费用增加等,此惩罚进入到服务器的服务成本。在线服务器的目标为使服务成本尽可能小。通过对该问题在一般网络上的分析发现,不存在具有常数竞争比的确定性和随机性在线算法。因此对网络进行了限制,考虑线段网络上该问题的下界并且设计了Conjecture算法,给出了算法的竞争比。3)研究了基于预知信息和服务时间约束的在线旅行商问题。考虑到等待服务的顾客等待心理以及服务的提前预订,将服务时间约束引入到基于预知信息的在线旅行商问题当中。服务器的服务目标为尽可能多的在服务时间约束内服务需求。通过在一般网络上对问题的分析发现不存在具有常数竞争比的在线算法,因而分别考虑了网络为一条线段以及网络为均匀度量空间的情形。在线段网络上给出了问题的下界,设计了RePlan算法并且给出了算法的竞争比;在均匀度量空间上给出了问题的下界,设计了贪婪算法并且分析了算法的竞争比。通过比较分析发现,预知信息虽然可以提高在线服务器的竞争性能,但是在线服务器的表现还要受到网络结构的影响。4)研究了基于服务时间约束的在线Prize-Collecting旅行商问题。由于现实生活中考虑单一目标的情形比较少,大多数的服务人员或者企业都希望增加利润的同时减少服务成本,本部分结合顾客等待心理,将服务时间约束引入到在线Prize-Collecting旅行商问题中。通过在一般网络上的分析发现,不存在具有常数竞争比的在线策略,因而对网络进行了限制。在线段网络上分析了问题的下界,设计了CMC算法并且分析了算法的竞争比;在均匀度量空间上分析了问题的下界,设计了CGA算法并且给出了算法的竞争比。本文的研究成果,一方面可以为现实生活中的快餐送餐,快递取件,出租车等上门服务提供指导,使其提高服务效率,提升顾客满意度;另一方面由于综合考虑了多种目标函数下的基于服务时间约束的在线旅行商问题,因此可以丰富在线旅行商问题的研究。
【学位授予单位】：西安交通大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：F224;F724.6;F592.6

【相似文献】

相关期刊论文 前10条

1 杨国兴;;一种多出发点多旅行商问题到旅行商问题的转换[J];系统工程理论方法应用;1993年03期

2 苏丽杰,聂义勇;现实旅行商问题[J];小型微型计算机系统;2005年04期

3 顾大权;徐四林;袁媛;汪晋;;求解旅行商问题的一个有效算法[J];解放军理工大学学报(自然科学版);2006年02期

4 马良,王龙德;旅行商问题在航标巡检中的应用[J];运筹与管理;1993年02期

5 杨忠,鲍明,张阿舟;求解中国旅行商问题的新结果[J];数据采集与处理;1993年03期

6 高尚;解旅行商问题的混沌蚁群算法[J];系统工程理论与实践;2005年09期

7 李妍峰;李军;高自友;;时变网络环境下旅行商问题研究[J];系统工程学报;2010年05期

8 张德富;顾卫刚;;解旅行商问题的一种有效方法[J];南京大学学报(自然科学版);1993年02期

9 赵玲,刘三阳;基于几何结构的求解旅行商问题的蚁群算法[J];苏州科技学院学报;2005年03期

10 郭靖扬;;旅行商问题概述[J];大众科技;2006年08期

相关会议论文 前10条

1 冯纯伯;;旅行商问题的一种解法[A];1991年控制理论及其应用年会论文集（下）[C];1991年

2 张雷;郑维敏;;广义旅行商问题、放映员问题和一类调度模型[A];1996年中国控制会议论文集[C];1996年

3 胡巧华;吴怀宇;陈乔礼;陈媛;;一种求解旅行商问题的启发交叉算子的研究[A];第25届中国控制会议论文集（中册）[C];2006年

4 张辉;王锡淮;肖健梅;;基于改进蚁群算法的旅行商问题[A];2007中国控制与决策学术年会论文集[C];2007年

5 李大卫;王梦光;;热轧调度与多旅行商问题[A];1996年中国控制会议论文集[C];1996年

6 刘春波;潘丰;杨丹;;基于改进的蚁群算法在中国旅行商问题中的求解[A];2007中国控制与决策学术年会论文集[C];2007年

7 冯纯伯;蒋珉;;应用模拟电场法解旅行商问题[A];1993年控制理论及其应用年会论文集[C];1993年

8 李丽;程玉荣;牛奔;;离散人工蜂群算法求解旅行商问题[A];第十三届中国管理科学学术年会论文集[C];2011年

9 孙启瑞;李俊;丁健;戴先中;;新型访问域部分重叠的多旅行商问题的GA求解[A];2013年中国智能自动化学术会议论文集（第四分册）[C];2013年

10 韩爱丽;朱大铭;;旅行商问题的一种新DNA编码方案[A];2006年全国理论计算机科学学术年会论文集[C];2006年

相关博士学位论文 前4条

1 张梦颖;不确定因素下路径规划问题研究[D];中国科学技术大学;2016年

2 温新刚;基于服务时间约束的在线旅行商问题研究[D];西安交通大学;2017年

3 谭阳;求解广义旅行商问题的若干进化算法研究[D];华南理工大学;2013年

4 王刚;两类圈问题的算法研究[D];国防科学技术大学;2013年

相关硕士学位论文 前10条

1 刘欣欣;旅行商问题的基因片段插入算法研究[D];闽南师范大学;2015年

2 陈玲;基于PSO-GA混合算法的时间优化的旅行商问题的研究[D];合肥工业大学;2015年

3 赵丽娜;带油耗的单商品取送货旅行商问题研究[D];沈阳师范大学;2016年

4 毛巍;一种新的改进人工蜂群算法及其在旅行商问题中的应用[D];四川理工学院;2016年

5 卢雨潇;基于多头绒泡菌模型的优化蚁群算法及其在旅行商问题中的运用[D];西南大学;2016年

6 肖聪;农产品配送中的流旅行商问题及启发式算法的研究[D];吉林农业大学;2016年

7 孙文成;基于多目标方法的旅行商问题复杂度研究[D];大连理工大学;2016年

8 徐东镇;蚁群算法及其在广义旅行商问题求解中的应用[D];合肥工业大学;2007年

9 黄厚生;求解旅行商问题的新方法研究[D];天津大学;2005年

10 王玲丽;随机存储下的有容量限制的广义旅行商问题[D];上海交通大学;2012年

，

本文编号：1323771