随着经济的飞速发展,人民生活水平的不断提高,人们对服务行业提供的服务质量的要求也越来越高。航空票务公司是一种新型的服务型企业,主要业务是代售机票。为了满足顾客的要求,同时应对票务公司之间日益激烈的竞争环境,近年来大多数航空票务公司推出了一项新的增值服务,为在公司订购机票的顾客提供免费接送机场服务。该增值服务不仅方便了顾客的出行,节约了出行成本,而且为票务公司吸引了更多潜在顾客。但是由于该服务无法给公司带来直接的经济效益,因此如何在提高顾客满意度的同时降低运营成本就成为该业务能否成功实施的决定性因素。
本文将航空票务公司的免费接送服务描述为车辆分配与调度问题(Vehicle Allocation and Scheduling Problem,简称VASP)。该问题从模型的角度来说,可以归结为带有时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,简称VRPTW),该问题是运作管理领域一种典型的优化问题。
本文首先对机场接送服务的流程进行了深入分析,并对相关理论基础和研究现状进行了综述。然后根据机场接送车辆调度问题的特点,分析了该服务中运输费用和顾客满意度之间的关系,并将顾客满意度和企业满意度量化,建立了顾客满意函数和企业满意度函数。在此基础之上为基于租赁车辆模式的票务企业建立了车次数与顾客满意度均衡模型；针对均衡问题的特点开发了一种基于集划分的精确算法(EABSP),并通过大量的测试实例分析验证了该算法的有效性和适用性。
其次,为了改进基于集划分精确算法的局限性,本文在基于集划分算法的基础之上提出了一种基于标签和集划分的精确算法(EABLSP)求解机场接送车辆调度问题中的均衡模型。该算法也可用于求解机场接送车辆调度中的最小化成本模型和顾客满意度最大模型。通过对该算法有效性和适用性的分析,证明了该算法具有较高的应用价值。
最后,建立了混合车次分配与调度问题中的车次数与顾客满意度均衡模型,用改进的基于标签和集划分的精确算法求解了该问题。通过分析单车型和混合车型的调度结果,有效的说明了研究机场接送服务中混合车次分配与调度问题的必要性。通过对大量测试实例的计算分析,验证了基于标签和集划分的精确算法求解混合车次分配与调度问题的有效性和适用性。
现代服务行业在社会经济活动中的地位越来越重要。作为服务行业一员的航空票务公司(Fight Tickets Sale Agencies,FTSA)为了提高服务质量、吸引更多潜在顾客提出了一项的增值服务,即机场接送服务(Pickup and Delivery of Customers to t...
详细信息
现代服务行业在社会经济活动中的地位越来越重要。作为服务行业一员的航空票务公司(Fight Tickets Sale Agencies,FTSA)为了提高服务质量、吸引更多潜在顾客提出了一项的增值服务,即机场接送服务(Pickup and Delivery of Customers to the Airport,PDCA)。该服务已经在中国的很多城市中开展,然而这种增值服务并不能产生直接的经济效益,反而会因为需要满足顾客更高的要求、提升服务质量而产生额外的费用。因此,如何在满足顾客满意度的情况下尽可能地降低成本,就成为该服务是否能够成功运营的关键所在。到目前为止,围绕PDCA问题的研究都是在单行程模式下展开的,然而经过调研和理论分析发现,多行程模式下的机场接送服务(Multi-trip Mode PDCA, MTM-PDCA)不仅能够减少车辆行驶总长度,而且能够减少车次数,从而降低了PDCA的整体运营成本。本文正是针对多行程模式下机场接送服务车次分配与调度问题展开的研究,旨在为决策者提供更加节约成本的解决方案,同时也从理论上丰富和发展了车辆路径与调度问题。本文的主要研究内容如下：(1)首次研究了多行程模式下的机场接送服务问题,并从理论上证明了多行程模式相对于单行程模式的优势。针对MTM-PDCA问题的特点,创新地提出了面向行程的集划分(Trips Oriented Set-Partitioning,TO-SP)模型,设计了求解该模型的精确算法,并给出了精确性的理论证明。针对不同的实例和参数进行了大量的实验,并与单行程进行比较,分析了多行程模式下的代驾租车固定费用、平均每顾客点顾客数量与车容量的比率、时间窗分布、地理分布对多行程优势的影响；最后给出了在什么情景下使用多行程模式能减少更多运营成本的建议。(2)考虑到道路交通安全以及司机身体健康等因素,将司机连续工作时长作为约束引入到MTM-PDCA问题中。针对考虑司机连续工作时长的MTM-PDCA (Duration Considered MTM-PDCA, DCMTM-PDCA)司题的特点,创新地提出了面向行程链的集划分模型(Trip-Chain Oriented Set-Partitioning, TCO-SP)。鉴于该模型的求解速度取决于行程链的数量,对行程链数量进行了理论研究,给出了最坏情况下行程链数量的数学表达公式,并分析了影响行程链数量的因素。为了快速求得精确解,针对该问题的特点,提出了基于改进标签和TOC-SP模型的三阶段精确算法,并给出了该算法精确性的理论证明。改进的标签算法(Improved Label Algorithm, ILA)位于整个精确算法的第二阶段,他可以在构造可行行程链的过程中去掉那些不可行行程链,使获得可行行程链的速度更快。该精确算法能够快速高效地求解较大规模的实例。针对不同的实例和参数进行了大量的实验,分析了DCMTM-PDCA问题中行程链的数量和特点；比较考虑司机连续工作时长的多行程模式与单行程模式的总成本,分析了参数、实例特点对多行程建模优势的影响,讨论了目标函数中的人工成本对调度结果的影响,并给出了相关的应用建议。本文理论上首次研究了多行程模式下的机场接送服务问题,并为建模和精确算法的设计提供了新思路；实际上为FTSA提供了多行程模式下的机场接送服务提供管理支持,使企业在保证满意度的情况下,减少了运营成本,提升市场竞争力。
命题逻辑的可满足性问题(Propositional Satisfiability Problem,SAT)是计算机科学的重要研究问题。SAT问题是一个判定问题,为命题逻辑公式找到一个可满足解或证明其不可满足。在许多领域中,SAT求解器被要求枚举实例的所有可满足解,这推动了SAT全解问题(All Solutions SAT,All SAT)的研究。SAT全解问题具有广泛的应用,例如将序列数据挖掘问题编码为合取范式,公式的所有可满足解对应所有感兴趣的模式;在网络验证中,使用SAT全解求解器能够计算从源到目的的所有可达数据包;在程序验证中,基于SAT全解问题的方法可以对谓词进行更精确、更安全的抽象。在基于回溯与子句学习的SAT全解算法中,如果缺乏有效的公式缓存机制,将浪费大量的重复工作。为提高SAT全解问题的求解效率,本文基于精确算法的优势,提出了两个SAT全解算法。本文的研究工作和主要贡献包括以下内容:(1)提出了基于DPLL框架的All SATCC算法,实现了非时序回溯、冲突驱动子句学习与组件分析技术的结合。为了快速判定可满足性并节省无效计算,算法在分支阶段使用了有效的组件决策策略,包括基于组件大小的组件分支启发式策略与组件搜索顺序。为了降低缓存大量可满足赋值对算法性能的影响,算法使用三种生成部分赋值的方法,将一组完整可满足解压缩为一个有效的部分赋值。此外,算法采用适用于可满足解枚举的组件缓存方案,同时通过使用管理学习子句和赋值的有效策略,减轻了内存负担。实验结果表明算法是高效的,而且它的性能不会受到公式中骨架变量占比的影响。All SATCC算法可以解决最多数量的实例,尤其是在图染色实例上的效率远远高于其他求解器。此外,All SATCC算法在继续求解未解决实例方面也表现出了求解潜力。(2)提出了基于对称组件分析的Nu All SAT算法,通过设计两个策略改进了All SATCC。首先提出了基于变量缓存状态衰减的随机启发式VCHDS,它第一阶段交替使用VSADS和LRB对变量得分进行排序,第二阶段依据变量在缓存中的状态进一步选择分支变量。VCHDS结合了多种启发式的优点,既考虑了搜索过程中最近的冲突,又考虑了缓存命中的影响。观察到现有All SAT算法的缓存方案中没有更充分地利用缓存信息,为了进一步提高缓存利用率,算法采用了对称组件分析技术,通过检测对称的组件提高了缓存命中,减少了搜索量。评估Nu All SAT算法的实验结果表明了该算法的提升。Nu All SAT可以解决更多的实例,而且求解速度更快。在截止时间内,Nu All SAT可枚举的可满足解数量提高了多个数量级。消融实验也表明了VCHDS和对称组件分析技术的有效性。
一个团（clique）是一个任何两个顶点都相邻的完全图。在社交网络中,完全图代表着最为紧密的社交关系,因此在网络中挖掘出最大的一个团非常有现实意义,也成为了社会计算、数据挖掘等领域中的一个经典问题。但是由于团的要求非常严格,为了更好地刻画密集子群结构,各种松弛团模型被提出。这些模型常通过对团的某一方面性质进行松弛得到,比如对顶点度数进行松弛得到的模型有k-core,k-plex等;对路由长度进行松弛得到的模型有k-clique,k-club等;对连通度进行松弛得到模型有k-block,k-bundle等。其中k均是模型固有的参数。最大松弛团问题,即从给定的图中提取基数最大的满足松弛团定义的子图,是著名的组合优化问题最大团的推广。本文将研究三个与最大松弛团相关的问题,一是最大k-plex问题,二是最大k-bundle问题,三是最小染色和（Minimum Sum Coloring）问题。本文首先研究了最大k-plex问题,并提出了一个基于分支定界的精确求解算法。相较于已有的最大k-plex问题的精确算法,本文从理论上分析证明了我们的算法具有更低的时间复杂度上界,是第一个突破2~n时间复杂度的精确算法,其中n是图中的顶点数量。实验表明我们的算法在标准测试集上的表现也更优秀。接着本文研究了基于连通度松弛的模型k-bundle。针对最大k-bundle问题,我们分析了k-plex与k-bundle在结构上的异同,借鉴并改进了我们在最大k-plex问题的精确算法中提出的分支规则。同时本文还设计了更多基于直径,图染色等方法的剪枝规则用于加速我们的算法。在标准测试集上的实验对比表明,我们的算法相较于该问题已有的精确算法更高效,特别是在大规模的社交网络算例上。最后,本文给出了最大松弛团问题在最小染色和问题上的一个应用。最小染色和问题是在超大规模集成电路设计以及资源分配调度等领域有广泛应用一个的组合优化问题,本文给出了一个利用最大团和最大松弛团来构造最小染色和理论下界的方法。
暂无评论