摘 要

L市人口约为390万，公共交通系统有待完善，且本地主要公司地理位置与企业员工住所相隔较远，在这样的背景下，本文借助数学软件MATLAB，对L市R公司所提供的通勤班车服务路径优化模型的搭建进行了模拟，随后运用改进蚁群算法——蚁群系统对上述模型进行仿真求解，所得结果对于减少R公司在租赁和管理通勤班车服务的开销以及缓解城市的交通压力上具有重要的指导意义。

论文主要研究了通勤班车路径优化模型构建与求解。首先，结合旅行商问题、车辆路径问题以及校车路径问题的国内外研究现状，阐述了TSP，VRP以及SBRP问题的建模原理和约束条件，为本文对于建立通勤班车的路径优化模型奠定了理论基础。其次，通过调查问卷的方法对通勤需求进行个体化交叉分析，并运用比较排序法得出影响通勤班车需求影响因素的重要程度表，根据此调查结论，从实际情况出发修改了基于理论基础的通勤班车路径优化模型。接着便在前人研究的基础上改进蚁群算法，修正蚂蚁系统的不足并引出蚁群系统，并将该算法在MATLAB中应用于对通勤班车路径优化模型的求解中，对模型进行了仿真运行和灵敏度分析；最后，结合模型运行结果，对通勤班车路径优化提出适当的建议。

研究结果表明：企业员工以通勤时间和乘车方便性为重要考虑因素，路径优化的研究也就显得尤为重要。本文优化的蚁群算法对求解通勤班车路径优化模型进行求解，所得结果公司班车的成本较低，且总载客效率高达83.8%。

本文的特色：通过对通勤需求的实际调查，分析了影响员工通勤的主要因素，以此为约束建立了通勤班车路径优化模型；对蚁群算法进行改进，并在MATLAB中构建了改进后的模型，并进行仿真求解，证明了模型和改进算法的可行。

关键词：通勤社会化需求；车辆路径问题；蚁群算法

ABSTRACT

The population of City L is about 3.9 million. The public transportation system needs to be improved, and the geographical location of major local companies is far from the residence of employees. In this context, this paper first simulates the construction of the commuter shuttle service route optimization model in MATLAB. Then solves the above model by using the improved ant colony algorithm - Ant Colony System. The results obtained have important guiding significance for reducing R company's expenses in leasing and managing commuter shuttle services and relieving traffic pressure in the city.

This paper mainly studies the construction and solution of the commuter shuttle route optimization model. Firstly, combining the domestic and foreign researches of traveling salesman problem, vehicle routing problem and school bus routing problem, the modeling principles and constraints of TSP, VRP and SBRP problems are expounded, which lays a theoretical foundation for establishing the route optimization model of commuter shuttle. Secondly, through questionnaire, the demand of commuter shuttles is individualized cross-analyzed. Using the ranking method, we obtain the importance level of the factors affecting the demand for commuter shuttles. According to the conclusion of this questionnaire, the theoretical basis of commuter shuttle route optimization model is modified based on the actual situation. Then, based on the previous research, the deficiencies of the ant system are corrected and the ant colony system is derived. The algorithm is applied to the solution of the commuter shuttle route optimization model in MATLAB. Finally, combined with the results, appropriate recommendations are made for the route optimization of the commuter shuttles.

The research results show that the employees value commuting time and ride convenience in the modeling of commuter shuttle path optimization. Using the improved ant colony algorithm leads to the result of low cost of shuttles and the total passenger efficiency as high as 83.8%.

The characteristics of this paper: Through the actual questionnaire of the demand of commuter shuttles, the main factors affecting it are analyzed, and the commuter shuttle route optimization model is established with the constraints. Then, the improved ant colony algorithm and model are constructed in MATLAB. The simulation is carried out to prove the feasibility of the model and the improved algorithm.

Keywords：Commuter Shuttles Demand; Vehicle Routing Problem; Ant Colony Algorithm

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景 1

1.2 与路径优化相关研究课题 1

1.2.1 旅行商问题 1

1.2.2 车辆路径问题 2

1.2.3 校车路径问题 3

1.3 国内外研究现状 3

1.3.1 国内外与解决TSP和VRP相关算法的研究 3

1.3.2 国内外与解决SBRP相关算法的研究 4

1.4 本文研究方法与结构 6

第2章 通勤社会化需求特性分析 7

2.1 通勤个体特征 7

2.2 影响通勤班车需求的主要因素 10

2.2.1 选择乘坐通勤班车的因素研究 10

2.2.2 拒绝乘坐通勤班车的因素研究 12

2.2.3 结论 13

第3章 通勤班车路径优化模型的建立 14

3.1 通勤班车路径优化目标 14

3.1.1 问题定义与约束 14

3.1.2 优化目标 14

3.2 模型建立 15

3.2.1 变量解释 15

3.2.2 目标函数 16

3.2.3 约束条件 16

第4章 通勤班车路径优化模型的求解 18

4.1 蚁群算法概述 18

4.2 蚁群算法的实现 19

4.2.1 信息素更新 20

4.2.2 状态转移和节点选择概率 20

4.3 改进蚁群算法在通勤班车路径优化问题中的应用 21

4.3.1 信息素更新 21

4.3.2 节点选择概率 22

第5章 仿真结果与分析 23

5.1 R公司简介 23

5.2 班车路径问题求解 25

5.3 结果分析 26

第6章 结论与展望 29

6.1 结论 29

6.2 展望 29

致 谢 30

参考文献 31

第1章 绪论

1.1 研究背景

在过去几十年间，随着科技的不断发展和经济的不断进步，汽车产量突飞猛增。这极大的提高了人类的流动性，带给人们便利。然而城市道路与交通的发展跟不上汽车增长的步伐，导致城市道路与交通拥堵问题不可避免地恶化。在这场交通堵塞日趋严重的浪潮中，企业员工在通勤时不仅面临因交通堵塞带来的上班迟到的风险，而且大大增加了员工通勤的成本。本文所研究的L市人口约为390万。城市规模中等也即意味着公共交通系统并非十分发达，而且当地领先的几家企业均位于老工业区，而大多数员工则在新工业区居住，在这样的背景下，为了解决上述外部因素带来的问题，企业通勤班车应运而生。

随着通勤班车的涌入，这种新型服务模式还未得到成熟的管制，在通勤班车服务未被普及的情况下，城市交通堵塞可能进一步加剧。新型服务模式总会伴随着各式各样的问题，其中最为显著的问题则是线路规划混乱，载客效率低下，管理不集中等。这不仅增加了城市交通紊乱的风险，也大大提高了公司的成本。为了改善道路交通问题且减少公司在租赁与管理企业班车上不必要的成本，对通勤班车路径优化的研究就显得非常重要。

1.2 与路径优化相关研究课题

通勤班车的路径优化问题总体来说是车辆路径问题（Vehicle Routing Problem, VRP）的一种。对于车辆路径问题的研究，国内外学者对其进行了广泛的研究工作。车辆路径问题既是旅行商问题（Traveling Salesman Problem, TSP）的一种推广，也是校车路径问题（School Bus Routing Problem, SBRP）的前身。本章对以上三类问题进行了综述。

1.2.1 旅行商问题

在文献[1,2,3]中可以看到，长久以来旅行商问题（Traveling Salesman Problem, TSP）吸引了全世界来自各地的学者大量的研究工作，得到了广泛且深入的研究^[1][2][3]。直观来说，TSP是一个推销员的问题：推销员想找到从他的家乡开始并有且一次经过一组特定的客户城市的最短旅行并返回其家乡。正式地说，它可以用完整的加权图来表示，其中是表示城市的节点集，是完全连接节点的弧集。每个弧被赋值为，它是弧的长度，即城市和之间的距离，其中。旅行商问题是找到图的最小长度哈密顿电路的问题，其中汉密尔顿电路是一个连接图集G中每一个的节点的闭合回路。对于对称TSP，城市之间的距离与遍历弧的方向无关，即每对节点的。在更一般的非对称旅行商问题（ATSP）中，至少对于一对节点和我们有。在对称旅行商问题中，欧几里德旅行商问题则是最好的实例。在该问题在，城市是欧几里德空间中的点，并且使用欧几里德范数计算城际间距离。我们使用的所有旅行商问题实例都来自TSPLIB基准库，其中包含大量实例并且已被用于许多其他研究或源于旅行商问题的实际应用之中^[4]。

1.2.2 车辆路径问题

车辆路径问题（Vehicle Routing Problem, VRP）首先由Dantzig和Ramser学者于1959年提出^[5]，并且已于1981年被Lenstra和Kan学者证明为是NP-hard型问题^[6]。它是研究如何使用一组特征相同，即同质（homogeneous）的车辆，在满足客户要求的情况下，在仓库和客户之间的进行物品运输，使得车辆行驶的路程最短。VRP可以在许多实际领域中找到例证，如邮件递送，校车路线规划，固体废物收集，取暖油分配，包裹提取和交付等等。一般而言，解决VRP问题就意味着找到使用车队为所有客户提供服务的最佳路径。解决方案必须确保所有客户都得到服务且符合运营限制，例如车辆容量和驾驶员的最大工作时间，并最大限度地降低总运输成本。VRP可以被表述为数学规划问题，由目标函数和一组约束来定义。挖掘问题的数学特征，从而来设计出一种能够有效地解决问题的算法。

目标函数可以衡量解决方案的适用性。目标函数通常是多个并且可以是相互矛盾的。最常见的目标是使由行驶距离或行程时间反映的运输成本最小化；考虑与车辆和驾驶员相关的固定成本，因此也可以最小化车辆的数量。另一个目标是考虑车辆效率，由车辆负载容量的百分比表示。此外，目标函数也可以用于表示“软”约束，这些约束可以是顾客违反相应的约定进行罚款的约束。例如，如果车辆未按照客户约定的时间到达指定地点，则应支付罚金。道路收费计划也可以反映在目标函数中，从而使通过城市中心的路线的成本更高。定义和约束模型的变量包括：描述客户和仓库之间的连通性的道路网络；在道路网络上的客户和仓库之间运输货物的车辆；下订单和收货的客户等。

结合问题的各个变量以及目标函数，我们可以定义一整套不同的车辆路径问题。Vigo和Toth学者详细介绍了各种车辆路径问题^[7]。通过消除容量的约束并强制所有客户必须由单一路线的车辆提供服务可以得到容量车辆路径问题（CVRP），也即标准的旅行商问题；通过增加一个时间窗口和服务时间——一段持续的时间可以得到具有时间窗口的车辆路径问题（VRPTW）；通过考虑交通负荷随着一天的时间而变化可以得到时间依赖车辆路径问题（TDVRPTW）；通过添加用于接送和/或递送的时间窗口以及表示用户在接送点等待太长时间并且对骑行时间施加限制的不便的约束可以得到具有取件和配送的车辆路径问题（VRPPD）；以及通过引入在行进中加入的动态新订单可以得到动态车辆路径问题（DVRP）。

1.2.3 校车路径问题

校车路径问题（School Bus Routing Problem, SBRP）是一项日常问题研究，它首先被Newton和Thomas提出^[8]。在它的研究中，假设有许多住在不同地方的学生乘坐一定数量的校车去学校，且校车的行进路线应满足以下约束：在服务到所有学生的前提下，每辆车不超过汽车的容量，同时要考虑为每个学生设定的极限距离——换句话说，行进路线受到最大距离的限制。目标是使得运输所有学生的公交车数量最少且同时满足所有约束的情况下路径最短。该问题的目的函数是最小化运输的总成本。校车路径问题（SBRP）是组合优化问题的一种，它可以作为车辆路径问题（VRP）的一个版本呈现，类似于车辆路径问题的另一种形式，即开放式巡回车辆路径问题（Open Vehicle Routing Problem, OVRP）。开放式车辆路径问题（OVRP）由Schrage学者于1983年在论文中首次提出^[9]。该问题用于研究找到向给定数量的客户提供某些商品的车辆车队的最小总距离和成本的有效路线。其中每个客户只能被一辆车访问一次，而车辆活动受到容量限制，时长限制和时间点的限制。每条路线都是一系列客户，车辆从仓库开始并在其中一个货物交付的客户处抵达终点，或者每条路线的车辆都是某一个客户开始然后抵达总仓库。

OVRP与众所周知的车辆路径问题（VRP）的不同之处在于，车辆在向客户提供服务后不一定返回其原始位置；若返回，则车辆必须遵循相同的路径朝相反的方向返回。OVRP和VRP之间的理论上的主要区别在于OVRP中的路线由源自仓库的汉密尔顿路径和终止于客户端的路径组成，而VRP中的路线是单纯的汉密尔顿循环。对于OVRP中的每个车辆，必须解决具有固定源节点的最佳汉密尔顿路径问题，并且OVRP解决方案涉及为分配给车辆的每组客户找到最佳汉密尔顿路径，因此OVRP也是NP-hard型问题。

1.3 国内外研究现状

1.3.1 国内外与解决TSP和VRP相关算法的研究

在过去的几十年间，中外无数学者对旅行商问题和车辆路径问题已经进行了深入的研究，演算开发出了不同的元启发式算法，以找到NP-hard型问题的近似最优解。大多数元启发式方法都侧重于在检查解空间时如何平衡全局搜索和局部搜索。在这项研究当中通常有多个方向。早期的解决办法包括模拟退火算法（Simulated Annealing Algorithm）^[10]和禁忌搜索算法（Tabu Search）^[11][12]。这两中算法均侧重于基于一种避免局部最优解的机制来找到最佳的解决方案。在后期阶段的研究中，基于大规模群体的方法应运而生且更适合找到问题的最优解。一般来说，这种方法是生成大量解决方案，包括不同类型的学习机制。如在遗传算法^[13]和差分进化中，主要思想是将不同的高质量解决方案与一定程度的随机化相结合^[14]。粒子群优化则通过全局和局部找到的最佳解决方案的位置生成新的解来寻求解空间^[15]。这些基本思想已被应用于各种类似的方法，如布谷鸟搜索（Cuckoo Search），人工蜂群算法（Artificial Bee Colony Algorithm）^[16]，蝙蝠算法（Bat Algorithm）^[17]，磷虾群算法（Krill Herd Algorithm）^[18]等等。蚁群优化（Ant Colony Optimization, ACO）使用基于群体的方法，在贪心算法的基础上添加学习机制^[19]。

改进基于大规模群体的元启发式的最常用方法之一是将它们与局部搜索相结合。变量邻域搜索元启发式算法重点研究了局部搜索的有效使用。通过不同类型的增强手段或者通过创建一种或多种这种元启发式方法的混合方法，通常可以改善原始的元启发式算法的性能。然而应用这些方法的最主要的问题是在实施的过程中不断增加的复杂性，而且在运筹优化和应用数学以外的研究中，以上问题更为明显。因此在绝大多数的上述研究中，只有原始简单的元启发式方法被运用，来解决相关的问题。当谈论到简单中的重要性时，贪婪随机自适应搜索（Greedy Randomized Adaptive Search Procedure, GRASP）则是一个无法被忽略的例子。与众多与局部搜索结合的复杂算法相比，贪婪随机自适应搜索算法在性能上显然无法比拟，但它却被广泛使用。更复杂的元启发式算法的优势通常在规模非常大的问题中更为明显，如蚁群算法优化应用的一些例子中看出^[20]。因此，尝试增加GRASP可以解决的问题的规模是合理的，但是在某种程度上原始方法的复杂性最小。