摘 要

随时代经济发展，为中小学生上下学提供优质的校车服务成为学校和教育部门的新目标。校车调度无疑成为校车服务中关键的一环，在繁忙的交通车流中为校车提供良好的调度路线至关重要。校车调度受到众多如学校站点、车站站点、学生上下学时间要求、交通地理环境等一系列约束条件。如何处理好校车调度问题已成为众多学者研究的热题。

本文首先介绍了校车调度问题的国内外研究情况，进而在现有文献的研究基础上论述了车辆路径问题和旅行商问题的基本定义、分类等研究情况，还进一步介绍了相关的VRP和TSP的算法，而后基于贪心算法，设计了一个求解TSP问题的c语言程序，最后实例研究了武汉市洪山区中小学校的校车调度情况，利用贪心算法从而安排出合理的校车路径。

关键词：校车调度问题；校车路径问题；车辆路径问题；旅行商问题；贪心算法

Abstact

With the economic development of the times, providing quality school bus services for primary and secondary school students to go to school has become a new goal for schools and education departments. The school bus scheduling is undoubtedly a key part of the school bus service, and it is essential to provide a good scheduling route for the school bus in busy traffic. School bus scheduling is subject to a series of constraints such as school sites, station sites, student’s time requirements, and transportation geography. How to deal with the school bus scheduling problem has become a hot topic for many scholars.

This article first introduces the domestic and foreign research situation of school bus scheduling problem, and then discusses the basic definition and classification of vehicle routing problem and travel salesman problem based on the existing literature research, and further introduces the related VRP and TSP. Algorithm, and then based on greedy algorithm, designed a C language program to solve the TSP problem. Finally, an example is given to study the school bus scheduling situation in primary and secondary schools in Hongshan District of Wuhan City,using a greedy algorithm to arrange a reasonable school bus route.

Keywords: School Bus Scheduling, School Bus Route Problem, Vehicle Routing Problem,

Traveling Salesman Problem, Greedy elgorithm.

目 录

第1章 绪论1

1.1 目的与意义1

1.2 国外研究现状1

1.3 国内研究发展1

1.4 主要工作2

1.5 论文结构 2

第2章 文献综述4

2.1 车辆路径问题（VRP）4

2.1.1 车辆路径问题概述4

2.2 校车路径问题（SBRP）4

2.2.1 校车路径问题概述4

2.2.2 单车型校车路径问题（SBRP）5

2.2.3 多车型校车路径问题（HSBRP）5

2.3 旅行商问题（TSP）6

2.3.1 旅行商问题概述及Hamilton问题6

2.3.2 TSP的数学描述及数学模型7

2.3.3 多旅行商问题（MTSP）7

2.3.4 旅行商问题的求解算法8

第3章 研究方法12

3.1 贪心算法12

3.1.1 贪心算法的定义12

3.1.2 贪心算法在旅行商问题TSP中的应用12

3.2 贪心算法的代码实现12

第4章 实例研究14

4.1 数据采集14

4.2 问题探究及前期设定16

4.3 具体实施方法17

4.4 校车调度路径方案22

第5章 结语27

参考文献28

致谢30

第1章 绪论

1.1目的与意义

在新时代背景下，中国经济进入了一个高速发展的阶段。全国中大型城市的流动人口不断增加，环境和交通每天都在发生着巨大变化，以及适学龄儿童数量的增加，中小学的增建不可避免。就武汉市而言，截止到2015年为止，武汉市普通中小学总数为953所，其中有588所小学和269所初中。逐年剧增的学校数量以及复杂交通的变化势必给中小学生上下学造成相当大的麻烦与不便。因此，越来越多的中小学计划采用统一的校车来接送中小学生上下学。但同样的问题也随之而来，由于校车在我国兴起尚晚，因此对校车进行调度缺少很多的实际经验，在这样一个交通繁忙时代，许多学校的校车服务现状并不良好。不合理的校车调度方案会造成一系列问题，如浪费校车资源、学校支出增加、交通负担加重、师生时间精力的浪费等。作好对校车的安全有序的调度优化，不仅能节约社会总成本，也能减少车辆使用数，降低购车的一次性投入，还能提升校车服务质量，节约学校以及学生家庭经济负担，减少师生的乘车用时，减缓交通拥挤。因此如何设计合理的校车调度路线也是困扰众多学者的一个重中之重的问题了。

1.2国外研究现状

自1837年美国的校车诞生起,它一共经历了萌芽期、发展期和完善期三个时期^[1]。在十九世纪末的时候，美国的一些农村地区就已经出现了负责专门接送学生上下学的车辆。到了1910年，美国一共有30个自治州在不同程度上实行了校车运送学生计划。从那个时候起，美国的校车服务业便不断发展，更是形成了一个良好的校车服务系统。美国的校车调度研究更是很早就引起注意、发展迅速。早在二十世纪七十年代，Newton and Thomas，Bodin，and Bodinand Berman等人便假设有一些特殊的时间段，在每个时间段内，每辆汽车都只能为一所学校转运学生，并且最多只能一次出行,这样的校车调度问题他们采用一系列TP解决方案来解决^[2][3][4]；1981年Desrosiers等人描述了一个计算机化校车路线选择系统，包括由学生停车分配，路线生成，学校启动时间调度和路线调度等^[5]；1984年，Swersey和Ballard提出了校车调度问题的非线性规划模型及其离散近似MIP模型^[6]；2009年，Fügenschuh将校车调度问题提出为一个基于VRPTW的整数规划模型模块^[7]。今天，美国每年大约有45万辆校车正服务于接送学生上下学中，其行程多达40亿英里，形成了一个规模庞大的校车运送网络。

1.3国内研究发展

而在中国，校车服务的发展历史较晚，而基于公交车调度的校车调度理论与研究仍处在初步发展阶段。1999年，刘云等人对北京市的公交车智能系统，研究出了一个计算机网络方案^[8]；2000年以后，张飞舟等人运用遗传算法和混合遗传算法，来进行对车辆路径的优化^[9]；2002年，张无非等人在尽可能满足乘客和汽车公司双方利益下，通过基本的公交调度模型，从而排出了公交调度时刻表^[10]；2011年，许文龙等人运用GIS网络分析技术，提出了一个校车路径方案规划算法^[11]；2012年，丁常勇等人构建了一个多校车路径优化问题的数学模型,并通过在校车运行站点网络中引入了自行添加的虚拟节点的方法,将复杂的多校车路径优化问题转化为单校车路径优化问题,并对蚁群算法进行了改进来求解该问题 ^[12]；2013年，陈小潘等在研究校车路径规划的问题时,校车调度问题设定为带有时间窗的车辆路径问题,并设计了元启发算法对问题进行求解^[13]；2014年，杨梅等人建立了一个非线性的多目标整数规划模型，考虑到了校车数量最少、校车的发车总次数最少以及所有校车的路径差值平方和最小的目标，利用Lingo软件进行求解 ^[14]；2015年，牛宁分别键建立了单车型校车路径问题（SBRP）和校车调度问题（SBSP）两个数学模型,并分别改进蚁群系统算法(ACS)和最大最小蚂蚁算法(MMAS)对上述两问题进行求解^[15]；2017年，薛伟莲等人使用改进的蚁群算法，对校车路径规划问题做出了研究^[16]。

1.4主要工作

本文的主要工作是首先根据研究主题引出校车调度问题的现实意义，进而分别介绍国内外关于校车调度方面的研究现状。然后是文献综述根据校车调度的不同情况介绍阐述其定义及类别如单车单校型、单车多校型等，再分别介绍旅行商问题（TSP）及其衍生出的多旅行商问题（MTSP）以及其现阶段基本求解算法。并根据武汉市洪山区中小学的现状建立数学模型，进行实例设计校车调度方案。最后，对本文所做的研究内容和实例设计取得的结果进行简要的总结归纳，并将提出在未来对该问题的更为深入的研究方向和目标。

1.5论文结构

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：