公交车辆调度是公交运营的一项必要日常工作，结合数学算法实现排班系统的智能化，根据实际运营情况实现车辆调度优化，响应乘客的乘车需求。

1、自适应大邻域搜索算法
自适应大邻域搜索算法ALNS(Adaptive Large Neighborhood Search)由Shaw在论文中提出，分为remove和insert两部分算法，每次从当前的解中移除一定量的值随后得到一个部分解，对部分解应用inser算子，重新插入的所有可能情况构成了原始解的一个邻域，使用Branch and ound算法来搜索整个邻域的最优解，假如邻域中的最优解比当前解更优，则当前解进行改进。

2、算法流程
自适应大邻域搜索算法流程主要由生成规则、验收标准和算法的终止准则组成。首先初始化全局最优解，然后利用破坏算子和修复算子方法来获得临时解，并评估临时解的好坏，以此确定该临时解是否应该成为当前新的解。检查新解是否优于全局最优解，更新全局最优解，并检查终止条件，最后输出全局最优解。

3、自适应大邻域搜索算法在公交车辆调度应用
自适应大邻域搜索算法在需求响应公交调度上应用较广泛，公交车辆调度时需要考虑服务区域附件具备场站，满足发车条件后发出车辆，乘客预约的上下车点分布在起点、终点、M1个固定站点及M2个可变站点中，对于某一车辆班次k，该公交车从起点出发，依次在固定站点及被响应的可变站点服务，最后行驶到终点结束该班次服务。车辆行驶过程需要尽可能满足预约需求的上车时间请求，若车辆提前到达，则需要等待至最早乘客上车时间再开始服务，且等待过程中产生惩罚，同时满足车辆载客量与最长行驶时间等约束。

在建立车辆调度模型时，首先通过调研获取公交站点的相关信息和区域内乘客出行规律，将符合出行规律的乘客信息用于计算，将站点坐标转换为对应坐标值，根据每个时段内的预约数据，进行发车判断，将满足发车条件的数据输入线路调度模型，获取最优车辆调度方案，合理调度公交车辆降低运营成本，减少乘客候车时间。

4、结语
通过自适应大邻域搜索算法能够满足多对多的乘客公交出行需求,生成车辆调度优化方案，提高公交需求响应能力，制定合理确定发车时间和车次，最大化满足乘客出行需求。

参考资料：

[1]公众号 交通与优化
[2]靳文舟，杜昊，巫威眺 基于ALNS-TS算法的半灵活型需求响应公交调度问题.