免费机场接送服务中基于时间优先的聚类算法研究

发布时间：2020-11-09 09:42

　　 课题来源于面向城市内的航空票务公司提供的免费机场接送服务的管理实践。航空票务公司是一种新型的服务型企业,主要业务是代售机票。为了应对票务公司之间的日益激烈的竞争环境,近年来大多数航空票务公司推出了一项新的增值服务,为在公司订购机票的顾客提供免费接送机场服务。该增值服务不仅方便了顾客的出行,节约了出行成本,而且为票务公司吸引了更多潜在顾客。但是由于该服务无法给公司带来直接的经济效益,因此如何降低运营成本就成为该业务能否成功实施的决定性因素。 作为国家杰出青年科学基金(No.70625001)、中央直属高校基本科研业务费项目(N090204001)和国家自然科学基金青年基金(No.61004121)的重要组成部分,本文将航空票务公司的免费接送服务描述为接送顾客到机场的车辆调度问题Vehicle Scheduling for Air-passenger,简称VSAP)。该问题从模型的角度来说,可以归结为带有时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,简称VRPTW),是一种典型的面向商业和服务型企业的运作优化与决策问题。本文首先对机场接送服务的流程进行了深入分析,并对相关理论基础和研究现状进行了简要综述。然后,根据机场接送服务的特点,将顾客满意度量化为顾客对接送时间的要求,面向基于租赁车辆模式的航空票务公司建立了考虑绕行限制的最小化车次数模型,针对该模型设计了基于时间窗逆序聚类的两阶段启发式算法进行求解,最后通过计算实验与结果分析,验证了模型以及算法的有效性。针对VIP顾客需要提供更高的服务要求,根据该问题的特点将满意度量化为顾客对接送时间和到达机场时间的要求,考虑最大等待时间,并在一定满意度和绕行限制下建立了以租赁公司为主体的最小化成本模型,提出了一种基于随机聚类的三阶段启发式算法求解双时间窗问题,设计了车次优化策略；最后通过实例验证并分析该算法的有效性和适用性。 在上述理论研究的基础之上,针对调度工作人员的业务流程和功能需求进行了最小车次数算法软件模块的分析与设计,并完成了需求分析、功能设计、数据库设计和界面设计等工作。最后,完成了基于C/S结构的最小车次数算法软件模块。
【学位单位】：东北大学
【学位级别】：硕士
【学位年份】：2011
【中图分类】：F562.6;TP301.6
【部分图文】：

旅客周转量由1978年的27.9亿人公里增长到今天的3375.2亿人公里，分别增长99.8倍和121倍。图1.1中列出了中国航空旅客运输量和旅客周转量的发展变化趋势[2]。yT - 3500.0 旅to 20000 旅客运输量旅客周转量 —?—-??????. 客5 tHz - 3000.0 周j P 转5 15000 - - ? ? _ W - 2500.0 量S ￡重 分 -2000.0人TT 4 nnnn ___ _ _ _ __ __ __^ 上uuw ....- --.- — ~ y - 1500.0 里5 獨 —一—一——皿。—?咖.00 J——■ _ I I ■ ■ , I ——I . , ? . . . r——, L 0.0旁 i i i i i i i / / / / / / / / / / /年份图1.1中国航空旅客运输量和旅客周转量发展变化趋势Fig. 1.1 The trend of passenger traffic and turnover in China aviation而近几年，与航空物流相关的航空服务业的发展更为迅速，消费者对于航空服务行业的要求也越来越高。企业在保证服务质量的同时，还应提供多样性的服务项目来满足顾客越来越多的需求。航空票务公司就是随之应运而生的一种服务性企业，其主要服务项目就是为各航空公司代售机票，从中获得一定的利润。由于航空票务公司的数量越来越多，竞争也愈加激烈；为此票务公司推出了一些免费增值服务来吸引现有顾客、挖掘潜在顾客，免费接送机场服务就是其中颇受顾客欢迎的一种增值服务。但是，这种增值服务需要航空票务公司让出部分利润，提高了运营投入，因此如何在尽可能降低成本的同时

得到的优化车次数为4。经过两阶段的启发式算法，结果的车次数达到了最优解。算法软件模块的小规模测试实例计算结果如图3.4所示。[Ifk禅其法计复査卷结果\建立脚试日志1 I运行丨阶赃t賊*(对丨:《德营兩IT_.h h ... [u[^计算结果I图3.4算法软件模块的小规模测试实例计算结果Fig. 3.4 Experiment results of a small scale instance in software module可见，通过第二阶段的启发式算法，车次数减少，在租赁车辆模式下，相应的运输成本也随之降低。-26-

表3.5 200个顾客点benchmark实验结果Table 3.5 Experiment results of 200 benchmark customer points实例 车次数 近优率(％) 运行时间I9O34 RBTFC 5.012s謂 1 cTlEX II 86.6%理论最小值 75 CPLEX 53m55s第一阶段 102 RRTFr 4 7S7.rim 第二阶段 93 ■。/ 则呢 4.757sClOl CPLEX 82 86.6/0理论最小值 75 CPLEX 46m40s第一阶段 100RClOl ? ：丨 ■ ?理论最小值 75 CPLEX Ihl2m2BrlDdt —_ _ ? _… 一 “ "‘ ■" ■“ ? ‘ —
【相似文献】

相关期刊论文 前10条

1 孙凤菊;;K-means聚类算法的研究实现[J];辽宁师专学报(自然科学版);2012年01期

2 张选平;祝兴昌;马琮;;一种基于边界识别的聚类算法[J];西安交通大学学报;2007年12期

3 李德强,黄莎白;一种新聚类算法在模糊神经网络中的应用[J];信息与控制;2002年05期

4 杨铭;;数据挖掘中聚类算法的分析与研究[J];网友世界;2014年15期

5 孟海东;宋飞燕;宋宇辰;;面向复杂簇的聚类算法研究与实现[J];计算机应用与软件;2008年10期

6 向继,高能,荆继武;聚类算法在网络入侵检测中的应用[J];计算机工程;2003年16期

7 李静;;关于聚类算法的探究与发展[J];数字技术与应用;2014年06期

8 张天伍;詹自熬;;一种基于引力的聚类算法[J];河南科学;2009年01期

9 高利军;王辉;张望;;个性化服务中自适应聚类算法的研究[J];微电子学与计算机;2007年08期

10 武森;张桂琼;潘静;全敏;;分类属性数据的泛化中心聚类算法[J];运筹与管理;2014年06期

相关博士学位论文 前10条

1 许玉杰;云计算环境下海量数据的并行聚类算法研究[D];大连海事大学;2014年

2 孙鹏岗;聚类算法研究及其在网络模块性分析中的应用[D];西安电子科技大学;2011年

3 王振佳;基于基因表达数据的双聚类算法研究[D];山东大学;2016年

4 刘位龙;面向不确定性数据的聚类算法研究[D];山东师范大学;2011年

5 万淼;基于群智能和随机索引的网络聚类算法研究[D];北京邮电大学;2011年

6 王冰;人工蜂群算法的改进及相关应用的研究[D];北京理工大学;2015年

7 王贵参;重叠社区发现中的边聚类算法研究[D];吉林大学;2016年

8 管仁初;半监督聚类算法的研究与应用[D];吉林大学;2010年

9 杨文超;顾客时间窗变化的物流配送干扰管理模型及其算法[D];大连理工大学;2012年

10 赖鑫生;演化算法与混合算法的性能研究[D];华南理工大学;2014年

相关硕士学位论文 前10条

1 鲍宇;免费机场接送服务中基于时间优先的聚类算法研究[D];东北大学;2011年

2 解英杰;聚类算法及其在高职院校学生信息管理系统中的应用研究[D];山东师范大学;2012年

3 陈超;生物信息学中模体聚类算法的研究[D];天津师范大学;2011年

4 刘昊;基于聚类算法的生物分析软件的设计与实现[D];复旦大学;2013年

5 侯丹丹;基于属性权重的聚类算法研究[D];河北工业大学;2011年

6 张婕;聚类算法在网页分类中的应用研究[D];北京化工大学;2013年

7 张燕;半监督进化聚类算法及其应用[D];西安电子科技大学;2013年

8 郭亚利;基于人工免疫系统的数据流聚类算法研究与应用[D];西安电子科技大学;2013年

9 刘毅;一种基于距离和密度的峰值自动检测聚类算法[D];天津大学;2017年

10 程顺宽;基于粒计算的聚类算法研究[D];南昌大学;2015年

本文编号：2876231