随着国内经济持续、快速发展,人们对服务型企业的要求越来越高。因此,如何在日趋激烈的市场竞争中推出更具吸引力的服务已经成为这类企业占领市场、立于不败之地的关键。进入21世纪,在中国民航高速增长的带动下,代售各个航空公司机票,并提供各种附加值服务的航空票务公司(Flight Tickets Sales Companies,简称FTSC)应运而生。航空票务公司是一典型的服务型企业,其主要功能是代售机票,但是随着公司之间的竞争日益加剧,这些公司纷纷推出新的服务种类来吸引更多的顾客。近来一些航空票务公司为了吸引顾客,提高顾客的满意度,推出了免费上门接送顾客到机场的服务项目。该服务的推出不但方便了顾客的出行,节约了顾客的出行成本,而且成功地为票务公司吸引了很多潜在顾客。但是,由于该业务并不能给公司带来直接的经济利润,如何降低成本就成为该业务能否成功实施的决定因素。作为国家杰出青年科学基金(70625001)、国家创新研究群体科学基金(70721001)、国家重点基础研究发展计划资助项目(2009CB320601)和教育部博士点基金(20060145009)的组成部分,本文将航空票务公司中实施的机场接送服务描述为一种车次分配与调度问题(Vehicle Allocation and Scheduling Problem,简称VASP)。该问题从模型的角度来说,可以归结为经典的车辆路径与调度问题(Vehicle Routing and Scheduling Problem,简称VRSP)。VRSP是运作管理领域一种典型的优化问题。本文在对机场接送服务进行深入分析的基础上,研究了基于最小化成本的车次分配与调度中若干重要的优化问题。研究成果及核心内容主要有以下五个方面：1)根据机场接送服务的特点,将顾客满意度量化为顾客到达机场的时间要求,将运输成本分为车次启用的固定费用和车辆的运行费用。在一定满意度下,提出了一种集划分的模型来描述机场接送服务中的车次分配与调度问题。根据模型的特点,设计了基于集划分的精确解算法及启发式算法来分别求解小规模和大规模问题。最后通过结果分析,验证模型的实用性和算法的有效性。2)在考虑顾客的绕行限制下研究了机场接送服务中的VASP,同样将满意度量化为抵达机场的时间要求。在一定满意度和绕行限制下,建立了基于车辆流的最小化成本模型。并根据问题特征,设计新的评价因子,提出了一种基于最小评价因子的顺序插入启发式,通过与CW节约算法比较,说明算法的有效性。最后,在给定路径下研究了车次的最优调度问题,来提高顾客的满意度。3)根据近年来民航高速增长的情况,预测未来航空票务公司将购置大容量车辆,将问题扩展到混合车型,包括小轿车和中小巴士。同时为了体现实际中满意度设定的多样性,将满意度量化为顾客对上车时间的要求,在一定满意度和绕行限制下建立了混合车型的最小化成本模型,提出了一种基于移入移出的自适应局域搜索算法进行求解。该算法分别设计了三种插入和移出策略、并开发了一种多次重启的确定式退火搜索结构。大量的仿真结果验证了算法能在有效的时间内得到高质量的解；最后分析了变动成本,为FTSC根据市场价格选购车型提供支持。4)根据机场接送服务是一种短途城市交通运输服务的特点,允许在计划期内为每个车辆或司机安排多条路径,研究了中间无返回的多行程车次分配与调度问题(Multi-trips Vehicle Allocating and Scheduling Problem,简称MVASR)。提出了一种基于叫车接送问题(Dial-a-ride Problem,简称DARP)的MVASP模型。该模型考虑了司机的最长工作时间限制,同样使用顾客抵达机场的时间满意度和绕行限制。根据问题的特点设计了一种节约-插入结合的启发式算法。在结果分析中将MVASP与VASP进行比较,说明MVASP在节约时间和费用上的有效性；并将两种运输模式MVASP和DARP进行比较,为FTSC根据自身实际情况选择合适的运输模式提供支持。5)根据调度约束复杂多样,调度的可行性不容易判定的特点,研究了在给定路径下,调度的可行性判定问题。主要内容包括以下三个方面：a)研究了带最大等待时间和最大绕行时间的DARP在给定路径下调度的可行性问题；指出Hunsaker B和Savelsbergh M[1]设计的三阶段算法在检验最大绕行时间方面的不足；并给出了时间复杂度为二次的修正算法。b)研究了给定VASP路径下调度的可行性判定问题,分别针对满意度为抵达机场时间和上车时间,设计了两个时间复杂度为线性的判定算法。c)研究了给定MVASP路径下调度的可行性判定问题,开发了一个时间复杂度为线性的判定算法。