组合优化主要研究最优匹配、划分与排序等问题的求解方法，从有限个离散状态中搜索最佳状态。交通、物流、医疗、电信、能源、零售、军事等众多领域中均存在大量组合优化问题。尽管各个行业的业务背景千差万别，经过数学建模，绝大多数组合优化问题均可抽象为混合整数规划问题，本质上属于同一类问题。为高效求解该类问题，众多启发式优化算法被相继提出，面向政府与企业的需求提供解决方案。
　　一方面，路径规划与人员排班作为极具代表性且应用广泛的组合优化问题，具有较高的研究价值。另一方面，路由与排班涵盖了大量复杂的离散优化与连续优化问题，且其中绝大多数问题均为NP难度的难以精确求解的极具挑战的问题。为对相关问题进行高效求解，本文首先对组合优化领域的发展现状进行了分析，然后调研了包括元启发式算法与数学启发式算法在内的多种智能优化算法。之后，对库存路由问题、多阶段人员排班问题以及班车线路规划问题进行了建模，给出了上述三个代表性的路径规划与人员排班问题的形式化描述，从理论上和实践上分析了三个问题的共性与特性。最后，以上述三个问题为切入点，针对性地设计了高效的求解算法，并通过与文献中的计算结果对比以及参与相关国际竞赛等途径对算法进行了系统地测试，验证了算法的有效性与可扩展性。
　　具体地，本文的主要工作与贡献包括以下几点：
　　首先，提出了一种用于求解库存路由问题的数学启发式算法。该算法深度结合问题的结构与特征，将其层次化地分解为路径调整、时机优化与配送量决策三个子问题，并采用局部搜索和数学规划方法对其进行求解。通过引入多种邻域精简、邻域采样以及近似评估策略，提高了搜索效率。为验证所提算法的有效性，参加了2016年度ROADEF/EURO挑战赛，并取得了全球第三名的成绩。通过对比赛结果进行分析，进一步优化了所提算法，并将其应用于普适性更强的库存路由问题模型的求解。在220个公开的数据集上的测试结果表明，所提算法改进了60个大规模算例中46个的最优解，并在剩余的160个小规模算例上与其他启发式算法相比有较大优势。
　　其次，提出了一种用于求解多阶段人员排班问题的带偏见的禁忌搜索算法。该算法包含新增排班、移除排班与变更排班三个简单邻域动作，以及整块移动排班、整块交换排班与对齐连续排班三个复合邻域动作。算法结合各邻域的历史表现自适应地选择待评估的邻域结构，能够合理地协调多种邻域之间的选择与权衡。此外，提出了多种跨阶段软约束的预估方式，以实现在多阶段的条件下，充分确保算法的健壮性。所提算法在第二届国际护士排班竞赛中取得了全球第四名的成绩，该结果在一定程度上验证了所提算法的有效性。
　　然后，提出了一种用于求解班车线路规划问题的多阶段元启发式算法。该算法集成了多种从简单高效到复杂精细的优化策略，包括基于拓扑变换的约束松弛与问题转换、针对潜在的约束违反提出的候选路径搜索、冲突节点升级以及连通性松弛策略，保障了算法的求解质量，提升了算法的稳定性。在863个公开算例上的测试结果表明，所提算法在607个稀疏图算例上均能在一秒内完成较高质量的线路规划，同时能够在文献中的算法几乎无法处理的256个大规模稠密图上保持较高的求解效率。
　　最后，通过分析上述算法在不同实际应用场景下的实验结果可以发现，一个高效的组合优化算法，往往需要对复杂问题进行合理的分解或层次划分，通过适当的问题转换充分利用针对不同问题的最新研究成果，综合考虑启发式算法与精确算法求解不同规模问题的优势与劣势，在优度与速度、时间与空间、集中性与多样性之间寻找平衡点。在今后的研究中，将尝试推广相关启发式优化算法到更多组合优化问题的求解，甚至形成组合优化问题的通用规划引擎，达到融会贯通的境界。