安庆师范大学经济与管理学院 许争争

一、引言

目前，中国已成为世界上增长最快的航空客运市场之一，在此基础上应运而生的机场接送服务已经在中国很多城市展开，如北京、上海、深圳和沈阳等地，机场接送服务中的调度问题不仅对各个航空票务公司具有重要作用，而且对各个航空公司的运营成功与否也具有密不可分的重要意义。

二、机场接送问题概述

（1）车辆模式。机场接送服务中使用的车辆模式主要有三种：自有车辆、租用车辆、自有车辆和租用车辆并存。目前大部分大中型票务公司通常以使用自有车辆和租用车辆并存模式为主，在安排接送任务时以租用车辆为主，自有车辆主要用于突发状况，以及为租用的车辆提供协助等；中小型票务公司以使用自有车辆为主，有个别公司与一些个人或车辆出租公司签订合作合同，当自有车辆不足时，调用租用的车辆进行服务。租用的车辆按照单次服务付费，即每接送一次顾客到达机场给予一定的报酬，根据具体天气条件等，每次费用不等。

机场接送服务中使用的车辆类型主要有小型轿车和中小型巴士。现有机场接送服务中，大部分公司采用的车辆以小型轿车为主，也有部分公司拥有中小型巴士应用于一些集体出游和顾客点比较集中的位置。

（2）接送流程。顾客可以通过网络、电话或者直接到票务公司柜台订票，顾客的所有基本信息包括姓名、联系方式、航班号等将被记录下来，如果顾客需要机场接送服务，那么他需要指定具体的接送地点。接送地点由顾客指定后，一般票务公司会判断接送顾客时是否方便，比如是否在接送时间附近不方便停车等，在这些情况下，票务公司需要和顾客进行协商以确定接送地点。另外，从理论上说，顾客对时间的需求可能有两个方面：一是车辆到达接送顾客的时间；另一个是车辆到达机场的时间。目前的车辆调度安排都是由比较有经验的调度员在服务的前一天晚上作出。一般做法是，首先将计划需要出港的顾客名单列出，然后根据出港时间进行安排，将时间和地理位置比较近的分在一组，最后将每组内的所有顾客进行排序，构成每个车次的接送顺序。

三、机场接送中的车次分配与调度问题研究情况

机场接送中的车次分配与调度问题是车辆路径与调度问题的延伸与扩展，具有新的问题和新的情况。目前国内外的相关研究情况如下：

接送顾客到机场的车辆调度问题(Vehicle Scheduling for Airpassenger，VSAP)是车辆路径问题的扩展。属于典型的NP难问题，由于国内外环境的差异，在国外鲜有这方面的研究，而与之相似的是国外关于Dial-A-Ride问题(Dial-A-Ride Problem，DARP)的研究，电话预约叫车服务问题[1]是指使用者(乘客)主动打电话到控制中心告知自己所在位置和需要接送的时间后，考虑时间窗、容量等约束要求由控制中心的调度人员规划路线，指派车辆接送乘客，完成运送行为。电话预约服务主要分为两种模式：一种是静态模式，在静态模式下所有要求是预先知道的，根据要求可以提前计划好所有车辆的路线；另一种是动态模式，在动态模式下，车辆路线是根据用户一天的需求实时构造，或者初始时把问题考虑成求一个静态问题，以获得一个初始解，稍后又按照新的要求对路径进行修改。接送顾客到机场的车辆调度也是乘客打电话订票并预约接送服务，调度员根据航班时间和顾客所在位置对顾客进行分组，规划路线并指派车辆接送顾客，接送的终点是机场，而DARP中终点是不同的地点，别的假设和约束两者相似。DARP早期的研究以静态问题为主，侧重于单车辆路径问题。动态DARP[2]最早是由Psaraftis提出，他以总用时最少为目标，设计了一种精确的动态规划算法，不考虑顾客提出的时间窗，顾客提出要求之后被立即服务，但是由于算法的复杂度较大，只对小规模的例子有效，算法只被用在了10个顾客的例子中。Psaraftis后来将原方法扩展到考虑出发时间窗和到达时间窗的双时间窗约束中。Sexton等人[3]考虑单时间窗提出一种启发式算法解决类似的问题，以车辆行驶的理想时间和实际所用时间的加权和为目标，对7到20个实际生活中的用户进行了测试。Desrosiers等人[4]针对动态DARP提出了一种精确的列生成算法，应用于40个客户的例子中。Coslovich等人[5]设计了两阶段插入算法应用于动态DARP。目前的研究集中在研究动态的DARP，提出了一些模型和启发式算法。从时间窗的角度，VSAP问题主要可以划分成三类：考虑到达机场时间窗的VSAP问题；考虑顾客点预约时间窗的VSAP问题；考虑双时间窗的VSAP问题。目前已有的主要研究集中在考虑时间窗要求这一条件下的模型的建立和算法方面的设计。

(1)考虑到达机场时间窗的VSAP问题。Dong G等人[6]建立了最小化成本模型，提出了基于集划分的精确算法求解考虑到达机场时间窗的VSAP，在计算过程中，第一阶段生成了所有可行的车次，在第二阶段通过优化软件Cplex对模型进行求解，生成了最优方案，该算法对于小规模的实例均可以较快求得最优结果。

孔媛等人[7]考虑顾客满意度以运输成本最小为目标建立数学模型，提出了基于集划分的启发式算法求解考虑到达机场时间窗的VSAP，该算法采用两阶段求解的方法，第一阶段采用广度优先搜索的策略，生成了所有可行路径，第二阶段采用启发式策略，从所有可行路径中找到可行解。

李佳[8]针对多行程模式的机场接送服务中车次分配与调度问题，建立了面向行程的集划分模型，基于该模型设计了精确算法，并对算法的精确性进行了证明；接着将司机连续工作时长作为一个约束条件考虑进来，建立了基于行程链的集划分模型，在该模型的基础上，设计了基于标签和面向行程链集划分模型的精确算法，通过大量的计算分析了考虑司机连续工作时长下多行程模式与单行程模式对结果产生的影响，以及人工成本对计算结果的影响，并给出了相关的应用建议；最后通过大量算例测试，分析了采用出租车接送的单行程模式与采用代驾租车接送的多行程模式之间存在着一个代驾租车日租费用临界值，在此临界值以下采用多行程模式更加合适。

杨培颖等人[9]对机场接送服务中碳排放模型和成本模型进行了全面的比较分析，提出了基于标签与集划分的精确算法，通过比较分析两模型在各影响因素下的测试结果，验证了不同模型的有效性和适用范围。对机场接送服务中的车辆配置等提供了可供参考的意见。

杨培颖[10]针对大规模VASP，设计了最近点优先的双向极线扫描启发式算法求解机场接送服务中碳排放最小化单车型模型，通过对该算法有效性和适用性的分析，表明了该算法具有较高的实用价值；针对多车型碳排放最小化模型，提出了改进的基于标签与集划分的精确算法，这种算法适用于中小规模顾客点情况。通过分析多车型情况下的车辆调度问题，结果有效地说明了研究机场接送服务中多车型分配与调度问题的必要性和重要性。

(2)考虑顾客点预约时间窗的VSAP问题。唐加福等人[11]建立了顾客点满意度和公司成本的多目标优化模型，并设计了基于C-W节约算法的两阶段启发式算法求解考虑顾客点预约时间窗的VSAP。算法取得了较好的效果。Liu B X[12]考虑了顾客点预约时间窗的VSAP问题，建立了最小化成本模型，提出了一个基于时间和地域划分的极线扫描启发式算法，并采用多种算例将该算法与PCPH算法和Sweep算法进行了比较，证明了该算法在大规模求解问题时的优越性和可行性。

刘秉星[13]针对顾客点预约时间窗的VSAP问题，提出基于集划分的精确算法求解VSAP。提出了范围验证的方法来验证路线的有效性，克服了点对点验证方法容易遗漏的缺点，保证了求解结果的精确性和有效性。该文还分别考虑最小化成本和最小化车次两个不同的目标，设计了最近点优先的双向极线扫描启发式算法，对中等规模与大规模VSAP问题进行求解，通过比较，结果要优于SPTD算法，并得出结论：TSNP算法在顾客点人数差异不大时，适用于求解以最小化成本为目标的优化问题；顾客点人数差异显著时，适用于以最小化车次为优化目标。

孔媛[14]以最小化成本为目标，考虑不同车型的情况，建立了接送顾客到机场的混合车次分配与调度问题的数学模型，设计了自适应邻域搜索算法求解问题，采用141组数据，其中中等企业72组，小型企业69组。大量的计算和实例测试显示，算法能快速得到优秀的解，并且算法的稳定性高，不受数据类型和规模的影响，通过变动成本进行的分析，当单位座位的变动成本率为-30%以下时，公司应考虑减少购置小轿车增加中小巴士的车型。

(3)考虑双时间窗的VSAP问题。曹夏夏等人[15]设计了基于租赁模式下的双时间窗基于集划分的精确算法，在原有均衡模型的基础上综合考虑了顾客对接送时间窗、到达时间窗以及绕行限制的要求，通过实例分析验证了算法的有效性。针对基于租赁车辆模式下的票务企业，建立了顾客满意度和车次数的均衡模型，根据模型特点设计了一种基于集划分的精确算法(EABSP)。

所以国内的研究主要可以概括为以下三个方面：考虑不同时间窗条件下，单行程或多行程中基于集划分的精确算法的研究；考虑不同时间窗条件下，各种启发式算法如节约—插入启发式算法，扫描算法等算法的研究；除了最小化成本模型外，碳排放模型的建立或多目标均衡模型的建立。