多车型校车路径问题优化算法研究

摘要

为中小学学生提供安全、高效的校车服务是我国义务教育发展中面临的新要求。校车路径规划是校车运营的基础环节，合理地规划校车路径可以显著地提高服务效率，降低运营成本。校车路径问题(SBRP)涉及学校、学生乘车站点、场站、校车类型、交通网络、学区地理环境、约束条件和规划目标等众多因素，是一类复杂度极高的NP-hard问题。SBRP通常是在保障校车服务质量的前提下，尽量减少车辆购置、维护等固定成本和校车的日常运营成本。
　　校车路径规划实践中，校车车队往往由多种类型的车辆构成。同时，受学生站点分布、道路状况等现实条件的影响，多种类型的校车组合能更好地满足实际需求。然而，相对于单车型SBRP，多车型SBRP(HSBRP)的研究较少。而且，现有HSBRP的求解主要采用构造启发算法或改进启发算法，优化性能有限，也难以适应较复杂的规划场景。鉴于此，本文针对HSBRP，在问题定义和数学建模的基础上，设计一个适用于多种应用场景的算法框架，进而探索单校、多校、车型混合和车辆数限制等不同场景下HSBRP的元启发优化算法。
　　研究思路如下：①针对不同应用场景下校车路径规划的需求，考虑校车类型、校车容量、校车数量、学校时间窗、学生最大乘车时间等约束条件，以校车固定成本和运营成本为目标建立HSBRP的数学模型，并尝试使用模型精确求解。②探讨HSBRP的求解策略，设计一个通用HSBRP算法框架，包括基本数据结构、常用操作函数、初始解构造算法、各种局部提升算子和启发策略；开发基础算法库，便于构造常见元启发算法。③利用算法库，针对单校车型混合、单校车辆数限制、多校多车型等问题类型，分别实现HSBRP算法，引入邻域解接受策略和车型调整策略提升解的质量；并使用基准案例进行算法测试和性能分析。④使用实际案例验证本文算法的实用性。
　　本文的主要工作和结论如下：
　　(1)完成了一个满足单校和多校问题求解的HSBRP算法框架。算法框架提供通用的数据结构、基础函数、初始解构造算法和邻域搜索算子，支持搜索算子选择、车型调整、邻域解接受、搜索扰动等启发策略的组合使用。基于算法框架实现了迭代局部搜索、变邻域搜索和贪婪随机自适应等元启发算法。算法的设计与实现表明：该算法框架不仅具有通用性，而且能够快速实现求解SBRP的元启发算法和混合元启发算法。
　　(2)针对单校HSBRP问题，分别完成车型混合HSBRP(FSMSBRP)和车辆数限制HSBRP(HFSBRP)的求解算法。针对FSMSBRP，设计贪婪随机自适应算法(GRASP)，并通过参数自适应选择对算法进行改进。该算法适用于求解总成本、固定成本和可变成本三种优化目标的FSMSBRP问题。在国际基准测试案例上的实验表明：参数自适应选择优于参数随机或固定选择；与现有FSMSBRP求解算法相比，GRASP算法具有明显的优势，三类问题的求解质量比RRH算法分别改进了5.28％、4.84%和7.22%，比自适应基于位置启发(ALBH)算法分别改进了6.26%、6.02%和7.55%。针对HFSBRP，建立了基于车型的整型规划数学模型，并设计一种迭代局部搜索算法和可变邻域下降算法混合的元启发算法(HILS)进行求解。使用HILS算法分别求解优化目标为总成本和可变成本的两类HFSBRP问题，测试表明所设计的HILS算法能够在较短的时间内获得高质量的解，并且算法稳定性较高。
　　(3)完成了混载和不混载两种运营模式下多校HSBRP的迭代局部搜索算法(ILS)。鉴于多校问题与带时间窗装卸一体化问题(PDPTW)模型具有相似性，在ILS算法中引入PDPTW问题求解中使用的SPI、SBR和WRI三个邻域算子优化总成本，并改进这三个算子允许车型调整。利用国际标准案例库对ILS算法进行测试，与随机基于位置启发算法(RLBH)和ALBH算法相比，ILS算法在不混载模式下的总成本平均下降了29.01%和34.84%，而在混载模式下ILS算法的总成本则平均下降了平均28.93%和34.66%。
　　(4)完成了一个案例实验。收集整理了无锡市惠山区的道路、学校和学生等信息，在ArcGIS10.2内完成数据整理、OD矩阵计算和网络分析等功能，完成单校和多校的案例研究。实验结果表明：使用多种车型规划校车路径优于单一车型的路径规划，多校运营模式比单校运营所需要的总成本更少。对于单校多车型校车路径规划，本文的GRASP算法优于ArcGIS网络分析中的VRP算法；对于多校多车型路径规划，本文设计的不混载和混载两种规划方案比现有方案分别节约了3.20%和6.62%的成本。
　　本文针对多车型SBRP问题的多种应用场景，设计了一个灵活通用的元启发算法框架，支持单校、多校以及不同优化目标HSBRP问题的求解。利用该算法框架，首次设计了求解车辆数限制HSBRP和多校HSBRP的元启发算法，且算法性能显著优于现有的算法。

目录

封面

声明

中文摘要

英文摘要

目录

缩略词

1绪论

1.1研究背景

1.2研究内容与目标

1.3研究意义

1.4研究方法

1.5论文结构

2文献综述

2.1车辆路径问题概述

2.2多车型车辆路径问题研究进展

2.3校车路径问题研究进展

2.4本章小结

3多车型SBRP元启发算法框架

3.1问题定义

3.2 SBRP求解算法分析

3.3算法框架设计需求

3.4算法框架设计

3.5基于框架的应用开发

3.6本章小结

4车型混合的单校校车路径问题

4.1问题描述与数学建模

4.2算法设计

4.3算法的复杂度分析

4.4实验与结果分析

4.5本章小结

5车辆数限制的单校多车型校车路径问题

5.1问题描述与定义

5.2算法设计

5.3算法复杂度分析

5.4实验与结果分析

5.5本章小结

6多校多车型校车路径问题

6.1问题描述与定义

6.2算法设计

6.3实验结果与分析

6.4本章小结

7案例研究

7.1案例区概况及数据准备

7.2案例区路径规划

7.3本章小结

8结论与展望

8.1主要工作

8.2主要结论

8.3创新之处

8.4进一步研究展望

参考文献

致谢

攻读博士学位期间主要的科研工作