作者沈吟东，留英博士，分别于武汉大学获学士和硕士学位、于英国利兹大学计算机学院获博士学位，并先后赴英国北伦敦大学和美国麻省理工学院（MIT）做访问学者。现任华中科技大学自动化学院教授、博士生导师，中国运筹学会常务理事，排序（调度）专业委员会副理事长，湖北省运筹学会副理事长，国家“十三五”规划重点图书《排序与调度丛书》副主编。主要研究领域是运筹与优化、公共交通优化调度与运营管理、人工智能、数据挖掘。特别在公共交通规划、调度和运营管理方面取得了重要创新成果与实际应用。先后承担6项g家级课题和一系列省部级课题，近期还编制和完成了海口、荆门、等6个城市的公共交通专项规划。出版英文版专著1部，在包括Transportation Research Part B等学术期刊上发表学术论文60余篇，部分研究成果已入编中国科协技术协会主编的《运筹学学科发展报告（2012-2013）》。2005年在夏威夷获得国际运筹学会（IFORS）颁发的“运筹学发展奖”，2014年在巴塞罗那获得国际运筹学会颁发的“运筹学发展奖”提名奖，以及获得2014年中国运筹学会科学技术奖“运筹学应用奖”，同时，还获得2014年湖北省科协“科技创新源泉工程”

　　《公共交通驾驶员调度/排序与调度丛书》应用运筹学领域的优化理论方法，专注研究公共交通（包括城市公交、地铁和铁路运输等）的驾驶员调度（又称“乘务调度”）问题。全书由8章构成，安排如下：第1章阐明驾驶员调度问题的研究意义和历史发展，并给出相关的基础概念、问题模型和问题复杂性说明；第2章介绍组合优化问题及常用求解方法；第3章阐述驾驶员调度问题的三种主要求解模式，并以求解方法为主线给出驾驶员调度问题研究的全面综述。这前三章旨在帮助读者对驾驶员调度问题、相关理论和求解方法有个宏观、全面的认识。第4～6章分别阐述三类主要的驾驶员调度方法；基于整数规划的方法、基于邻域搜索的方法和基于进化计算的方法；第7章介绍基本型驾驶员调度问题的主要扩展问题，旨在帮助读者了解特殊需求约束下的驾驶员调度问题求解方法；第8章介绍在国外和国内分别得到成功应用的两个公共交通驾驶员调度商用软件系统：TRACSⅡ系统和iPTS系统。
　　《公共交通驾驶员调度/排序与调度丛书》可以作为高等院校运筹学、交通运输工程、公共交通、智能交通、物流管理、系统工程、管理科学与工程等专业师生的教学参考书，也可以供公共交通行业管理部门、协会和运营企业中的管理者、科技工作者、运营计划编制人员与调度人员等参考使用。

第1章绪论

公共交通是人们日常出行的主要方式，包括航空、铁路、水运、公路等交通方式。狭义的公共交通主要是指城市范围内定线运营的公共(电)汽车、轨道交通、渡轮、索道等交通方式。本书描述公共交通驾驶员调度问题，并总结其优化调度理论与方法。这些理论和方法对航空、铁路、公路和水运4种主要公共交通运输方式基本适用，因为其驾驶员调度在问题描述、建模与求解方法方面基本一致。但是鉴于航空有其自身特性，本书不作特别讨论。本书着重描述地面公共交通(包括城市常规公交、快速公交、电车、轻轨、地铁和铁路运输等)的驾驶员调度问题，水运的驾驶员调度问题可视为特例。

需要说明一下，本书中的驾驶员调度问题中的驾驶员是广义的概念，是对司机、公交售票员、机车乘务员和列车乘务员等的统称，属于公共交通运营企业中重要的人力资源。在不同的公共交通方式下，相应的人力资源调度问题，可以采用不同的习惯称谓，例如公交驾驶员调度、机车司机调度、列车乘务调度等。因此，本书中描述的驾驶员调度问题，亦可称乘务调度问题。书中有时会依据上下文及惯例而混用。

公共交通驾驶员调度是公共交通运营企业必不可少的核心业务之一。对公共交通驾驶员资源实施优化调度，有助于增强公共交通服务水平和提高驾驶员的使用效率，并且能为企业节约巨大的人力成本。因此，研究驾驶员调度问题具有重要的现实价值，自20世纪60年代起就受到企业界和学术界的广泛重视，并且一直是公共交通研究领域的热点课题之一。本章首先介绍公共交通驾驶员调度问题的研究背景和意义，接着阐述该问题研究的历史发展，并定义相关的基础概念，然后给出驾驶员调度问题的两种主要模型，最后阐述现实的驾驶员调度问题的复杂性。

1.1引言

随着我国城市化和机动化进程的迅猛发展，越来越多的人享受了城市化生活和拥有私人机动车的便利，但也同时加重了对资源的消耗和环境的污染。目前，交通拥堵、交通事故和环境污染等问题日益严重，致使我国城市交通正面临着严峻挑战。优先发展公共交通是解决城市交通问题、实现城市可持续发展的根本出路，已成为我国城市交通发展的根本性战略。因此，如何大力发展公共交通，建设现代化、高品质的城市公共交通系统已成为我国经济社会发展中的重大理论和现实问题，亟待深入研究。

近年来，我国城市公共交通系统取得了比较大的发展，规划、建设和管理水平不断提高，在城市交通系统中承担的作用越来越重要。特别是在《国务院办公厅转发建设部等部门关于优先发展城市公共交通意见的通知》(国办发〔2005〕46号)颁布之后，城市公共交通系统在系统构成、设施建设、运营车辆、运营线路和客运总量等方面均有明显改善，城市公共交通的发展受到社会各界的广泛关注。2009年，各地按照国办发〔2005〕46号文件的要求，进一步提高认识，确立公共交通在城市交通中的优先地位，明确指导思想和目标任务，采取有力措施，加快发展步伐。特别是一些经济发展较快的大中城市纷纷投巨资建设城市轨道交通和快速公交(BRT)系统，以实现以轨道交通和BRT为骨架、常规公交(指公共(电)汽车，简称“公交”)为主体的城市公共交通体系。值得指出，由于轨道交通和BRT建设耗时且受城市财力限制，目前以及在未来相当长一段时间内，常规公交在我国绝大多数城市公共交通体系中仍将占主体地位。

总体来说，随着大力发展城市公共交通政策的贯彻落实，我国大部分城市的公共交通系统发展稳定，公共交通承担的出行比例逐年上升。但是，仍然面临因其他机动车的快速增加、各种模式的公共交通(例如公共汽车、地铁、列车以及航空等)运营企业间客源竞争加剧等所带来的挑战。此外，在相关理论研究以及信息化和智能管理方面仍然存在较大的改善空间。因此，如何提高公共交通服务水平、缓解运营企业成本压力、增强公共交通竞争力成为我国城市交通亟待解决的重要问题之一。

在大力发展城市公共交通的同时，我国铁路客运专线建设亦发展迅猛，目前已实现全国成网的目标，并且客运专线仍在快速发展完善中。于是，研究与之相匹配的铁路客运专线驾驶员和乘务员调度计划的优化编制理论与方法已经成为我国铁路目前亟待进行的重要课题之一。

西方发达国家的研究与实践已证明优化的公共交通调度方案能够降低运营成本、提高资源利用效益和服务水平(Steinzen et al，2010； Leone et al，2011a)。为此，公共交通调度问题自20世纪60年代起一直受到研究人员的广泛关注(Wren，1968； Hickman et al，2008)。公共交通调度问题主要是指对有限的资源，如车辆(公交车、电车、地铁、铁路机车和动车等)和人力资源(包括驾驶员、公交售票员和铁路乘务员等)，加以合理运用和优化配置，完成给定的运营任务，并且达到资源利用率最大化的目的，同时需要满足各种劳动法规等约束。由于该问题的巨大复杂性，一般被分解为如下三个子问题顺序求解： 车辆调度问题(Kwan and Rahin，1999； Shen et al，2016)，驾驶员调度问题(Wren and Rousseau，1995)和驾驶员轮班问题(Moz et al，2009)，如图11所示。

图11公共交通调度的

三个子问题

图11中列出的公共交通调度的三个子问题都是世界公认的组合优化难题，是公共交通领域中备受关注的热点研究课题，也是公共交通企业的核心业务之一(Ceder，2007)。其中，驾驶员调度问题作为重要的人力资源调度问题更是受到极大的关注 (Kwan，2011； Jütte and Thonemann，2012)。其基础是前一阶段编制的车辆调度方案； 当驾驶员调度方案形成之后，其下一阶段是编制驾驶员轮班表，即安排一个周期(如一周或一月)内驾驶员的轮班或轮休方案。

本书专注研究公共交通驾驶员调度问题，旨在研究如何最有效地安排一组驾驶员完成预先给定的车辆运营任务(即车辆调度方案)，要求满足一系列的劳动法规约束，目标是采用最少的驾驶员和最小的工时成本。该问题是世界公认的NP难问题，一般被认为是公共交通调度三个子问题中最为复杂的一个，因为其中驾驶班次的形成受到来自国家、地区和企业等一系列劳动法规的约束，以及驾驶员对不同类型驾驶班次偏好的约束等。

1.2历史发展

编制高效的驾驶员调度方案能够为公共交通企业节省大量成本，因此，研究驾驶员调度问题具有重要的经济意义。自20世纪60年代起，该问题就逐渐受到学术界和企业界的重视，并且一直是公共交通研究领域的热点课题之一。迄今为止，已经研制出一系列调度方法和调度系统 (Voβ and Daduna，2001)，其中部分调度系统已经获得广泛的成功应用。

20世纪50年代，英国全国的商用及公用公路与铁路交通均由英国交通委员会(British Transport Commission)负责管理。该委员会于1959年资助英国利兹大学电子计算机实验室，对各种交通方式采用计算机调度的可行性进行分析。1960年8月预研报告完成，其中利用计算机进行铁路调度的建议被采纳。于是，利兹大学的Anthony Wren教授于1960年初开始承接此项世界开创性研究。经过约三年的研究，世界上第一个由计算机编制的公共交通调度方案完成，并于1963年5月在英国铁路(British Rail)投入使用(沈吟东和Wren，2008)。随后的半个世纪中，Anthony Wren教授研究组一直致力于研究和利用计算机进行公共交通车辆及驾驶员调度，研制出多种基于启发式的、超启发式的以及数学规划的公共交通调度方法。据英国卫报(Guardian)教育版2006年报道，Anthony Wren教授的成就已被列入“英国大学近50年中百项改变世界的发现、创新与研究”之中。Anthony Wren教授团队的研究经历，实际上体现了英国公共交通调度研究的发展历程，对世界公共交通调度研究与实践产生了重大影响。这也将对我国的公共交通调度研究与应用具有借鉴意义。

20世纪60年代，作为公共交通调度领域中极为重要的一个热点问题，驾驶员调度问题被建模为集合覆盖问题(set covering problem，SCP)或集合切分问题(set partitioning problem，SPP)。然而，由于受到当时计算机能力所限，在1978年之前一直无法求得SCP和SPP的解。20世纪60年代，Anthony Wren教授领导研发的基于启发式方法的公交驾驶员调度方法，是最早的求解方法。70年代开始，在世界其他部分发达国家如美国、加拿大等，也纷纷有学者开始从事这一问题的研究。特别是从1975年起至今，国际运筹与交通学界陆续召开了13届计算机辅助公交调度的专题国际会议，很多开创性的研究成果收录在一系列的会议论文集中(Wren，1981； Rousseau，1985； Daduna and Wren，1988； Desrochers and Rousseau，1992； Daduna et al，1995； Wilson，1999； Voβ and Daduna，2001； Hickman et al，2008)。

总的来说，在20世纪六七十年代，由于受到计算机求解能力的限制，对驾驶员调度问题的研究主要依靠纯粹的启发式方法(也称为“早期启发式方法”)。这些方法主要采用计算机模拟人工排班的过程和经验，生成可执行的调度方案(解)。受计算机的计算能力所限，早期启发式方法只能求解较小规模的问题，并且求解质量较差。

20世纪80年代之后，随着计算机性能的逐渐提升、运筹学理论与方法的不断成熟和发展，驾驶员调度问题的研究开始转向以整数规划为主的数学规划方法，并出现了一些商用的驾驶员调度系统。从80年代初到90年代末，文献报道过的驾驶员调度系统主要有： IMPACS(Wren and Smith，1988)、TRACS(Fores，1996)、HOT(Volker and Schutze，1995)、HASTUS(Blais et al，1990)和Carmen System(Wedelin，1995)等。2000年后，又涌现出一些新的商用驾驶员调度系统，例如： TURNI(Abbink et al，2005)、TRAPEZE(Shen，2001)和TRACS Ⅱ(Kwan，2004)等。

在这些商用调度系统里，英国利兹大学研发的IMPACS和TRACS系统、加拿大蒙特利尔大学研发的HASTUS系统及其升级版，是有着持续性详细报道和广泛应用的驾驶员调度系统。英国利兹大学Anthony Wren教授领导的研究团队主要采用“生成”与“选择”相结合的模式，解决公共交通驾驶员调度问题(Kwan，2004)。其主要思想是先生成尽可能大的候选班次集，然后采用基于数学规划的方法从候选班次集中选择最优的班次子集，以覆盖所有车辆任务段。该研究团队研发出解决公交车辆和驾驶员调度的IMPACS系统，后对该系统进行改进并升级为TRACS Ⅱ(Fores et al，2002)，并用于解决列车乘务调度问题。20世纪80年代初期，加拿大蒙特利尔大学Rousseau教授领导的研究团队研发出著名的乘务调度系统HASTUS(Blais et al，1990)。该系统采用列生成算法为核心技术，其主要思想是在求解过程中动态生成新班次，因此与IMPACS系统的求解模式有较大区别。

20世纪90年代以后，铁路和航空的乘务调度问题逐渐受到重视，这些问题相对于常规公交驾驶员调度更加复杂，且其问题规模更大，原来基于数学规划方法的乘务调度系统已无法求解新的问题或者效率低下。在此阶段，元启发式算法如遗传算法、模拟退火以及禁忌搜索等发展迅速，并被用于求解各类优化问题(王凌，2001； 汪定伟，王俊伟，王洪峰 等，2007)。尽管它们难以从理论上保证解的最优性，但这些算法具有较强的全局搜索能力，能快速找到满意解。因此，为了克服问题的“大规模”所带来的困难，一些启发式方法如遗传算法(Kwan et al，2001)、蚁群优化算法(Forsyth and Wren，1997)、禁忌搜索算法(Cavique et al，1999； Shen and Kwan，2001a)以及基于遗传算法的混合智能优化算法(Loureno et al，2001； Li and Kwan，2003)，也被用于解决驾驶员调度问题。

20世纪90年代以后，基于传统整数规划的调度方法仍然在发展，尽管它在处理大规模复杂问题上具有局限性。一方面，在求解整数规划模型前，可通过人工经验或启发式方法对班次集进行筛选，使得模型所含班次集规模在整数规划技术可求解范围之内(Fores et al，1999)。另一方面，部分研究将数学规划方法和启发式、元启发式相结合，发挥出各自的优势。最典型的是，Caprara et al(1999)提出了将拉格朗日松弛技术与传统启发式方法相结合的方法，用于求解铁路运输的乘务调度和乘务轮班问题。该方法采用贪婪算法、评分机制固定变量法以及动态变化求“核心”问题等多种策略或方法，成为当时处理大规模乘务调度问题非常有效的方法之一。

此外，基于数学规划分解理论的列生成法也在不断发展。特别是，80年代末期至90年代，列生成法与分支定界相结合的方法(也称分支定价法或整数列生成法)逐渐被重视，并用于解决一维下料问题(Vanderbeck and Wolsey，1996)、车辆路径问题(Desrochers et al，1992)以及广义指派(Savelsbergh，1997)等各种组合优化问题。同时，列生成法也被用于求解包括城市公交、铁路以及航空等在内的乘务调度问题(Desrochers and Soumis，1989； Vance et al，1997； Gamache et al，1999)。虽然列生成法在理论上不受问题的规模限制且能保证最优性，但是，分支策略难以设计、主问题求解易于退化，以及子问题(通常是NP难问题)求解困难等，使得该方法在应用时收敛速度较慢，实际求解的问题规模仍然有限(在保证最优解的条件下)。更多关于列生成法的综述，可参见文献(Barnhart et al，1998； Lübbecke and Desrosiers，2005)。

2000年以后，随着计算机硬软件性能的提升和各种优化技术(包含各种元启发式与整数规划方法)的快速发展，驾驶员调度的研究方法也呈现出多样化的趋势。一方面，为了克服纯粹启发式方法解的质量无法保证和纯粹数学规划方法无法解决大规模的复杂问题等缺点，将数学规划方法和启发式、元启发式相结合，设计优势互补的混合优化方法，成为一个重要研究方向(Joncour et al，2010； Azadeh et al，2013； Shen et al，2013)。另一方面，由于传统的列生成法具有收敛速度慢的缺点，研究其加速方法以解决更大规模或更复杂的问题，成了另一个研究热点。特别是2000年后(直到如今)，一些基于问题特征的改进列生成法被提出并用于求解大规模整数规划问题，例如离散批量订购问题(Jans and Degraeve，2004)、动态车辆路径问题(Chen and Xu，2006)、公交线路规划问题(Borndrfer et al，2007)等，也包括公交驾驶员调度问题(Faneyte et al，2002； Freling et al，2004； Muroi et al，2010； Ahmadbeygi et al，2009)。此外，在基于对偶稳定性的列生成加速研究方面也取得了部分成果(Desrosiers et al，2007； Rousseau et al，2007； Amor et al，2006； Amor et al，2009； Liang and Wilhelm，2010)。

近些年，其他非主流算法也在发展，特别是约束规划(Achterberg，2007)作为一个新的分支逐渐被重视，并被用于解决各类驾驶员调度问题(Curtis，2000； Yunes et al，2005)。同时，不少研究也开始考虑一些更加复杂和规模更大的问题，如集成的车辆调度和驾驶员调度问题(Kliewer et al，2012)、运营发生晚点或意外情况后的重调度问题(Huisman，2007； Rezanova and Ryan，2010)等，更多的可参考文献(JespersenGroth et al，2009)。

总之，驾驶员调度问题经过近几十年的研究发展，涌现出了大量的优化模型和求解方法。特别是驾驶员调度问题在求解方法上不断改进和发展，取得了大量研究成果。

第1章 绪论
1．1 引言
1．2 历史发展
1．3 基本概念与术语
1．4 驾驶员调度问题模型
1．4．1 整数规划模型
1．4．2 特征模型
1．5 驾驶员调度问题的复杂性
1．5．1 大规模组合优化
1．5．2 复杂约束
1．5．3 多目标

第2章 组合优化问题及常用求解方法
2．1 组合优化问题简介
2．1．1 最优化问题
2．1．2 组合优化问题
2．2 整数规划方法
2．2．1 分支定界法
2．2．2 列生成法
2．2．3 列生成和行生成相结合的方法
2．3 邻域搜索方法
2．3．1 一般邻域搜索算法
2．3．2 大规模变邻域算法
2．4 进化计算方法
2．4．1 遗传算法
2．4．2 粒子群优化算法
2．4．3 蚁群优化算法
2．4．4 分布估计算法
2．5 混合优化方法

第3章 驾驶员调度方法研究综述
3．1 驾驶员调度问题的求解模式
3．1．1 构造型模式
3．1．2 生成与选择两阶段模式
3．1．3 构造与选择迭代模式
3．2 早期的启发式方法
3．3 传统的整数规划方法
3．4 基于列生成技术的整数规划方法
3．5 智能优化方法
3．5．1 基于GA的驾驶员调度方法
3．5．2 基于TS的驾驶员调度方法
3．5．3 基于GRASP的驾驶员调度方法
3．5．4 其他智能优化方法
3．6 发展趋势及展望
3．6．1 驾驶员调度方法的研究
3．6．2 驾驶员调度问题的扩展

第4章 驾驶员调度的整数规划方法
4．1 基于分支定界的驾驶员调度方法
4．1．1 算法框架
4．1．2 分支定界策略
4．2 基于列生成技术的驾驶员调度方法
4．2．1 基于列生成技术的算法框架
4．2．2 主要求解策略
4．2．3 案例计算
4．3 基于改进列生成技术的驾驶员调度方法
4．3．1 改进列生成法的总体思路
4．3．2 三种加速策略
4．3．3 案例计算
……

第5章 驾驶员调度的邻域搜索方法
第6章 驾驶员调度的进化计算方法
第7章 驾驶员调度的扩展问题及其方法
第8章 驾驶员调度的商用软件系统

参考文献
索引
附录A 英汉排序与调度词汇