校车管理正文

安排了校车，这样就形成了一个双赢的局面：家长不必为需要接送儿女上下学而愁苦，学校也因为家长满意学校的贴心的安排而保证了生源。

该校目前有三个乘车点，三个乘车点之间还是有一定距离的，但是该校只有一辆校车，每天早上6:30之前必须已经到达事先安排好的其中某一个乘车点，而这个乘车点周围的学生的家长就必须在6:40之前将学生送到乘车点，否则就会错过校车。校车在接完这一站点的学生之后，就必须立即赶往下一个站点去接下一个站点的学生，这辆校车的核定载客量是52个人，目前所存在的问题是：⑴ 这辆校车的载客量是一定，三个乘车点的学生数量也是有差距的，因此先去哪个站点等候的时间短时规划时需要考虑的问题；⑵三个乘车点只有一辆校车，这对于学校来说纵然是可以节约成本，但是对于学生来说却不是最方便的，先前的两个站点的学生需要起早赶时间，而如果遇上天气不好或者车辆中途出现故障，下一站点学生就无法按时到校，这会很大程度上影响教学质量的。

2.2 影响该校校车乘车点分布的因素分析

2.2.1 学生家庭住址的影响

由于是在农村，村民居住的地点并不是那么集中，所以学校在安排校车乘车站点时不能只从学校考虑，更需要从学生方面考虑。需要考虑的分为两点：学生步行或者家长送达所需要的时间的长短；还有就是对于住在相邻站点之间的学生来讲，他们所要考虑的就是路况以及这两个站点校车分别抵达的时间。 2.2.2 学生选择上车位置的偏好

学生在进行乘车站点选择的时候，会对影响其作出决策的一些因素(如步行时间，对站点本身的喜恶以及车辆到达站点的时间等)有所衡量。而不同的学生可能会对这些因素有不同的偏好，在不同的偏好选择下乘车站点的最终结果可能也会不同。

通过引入学生站点偏好概率从步行时间和校车到达站点的时间两方面对学生群的站点选择偏好进行研究。值越大，说明学生群在进行站点选择时越重视步行时间，而对车辆到达时间的关注程度较小。反之，说明学生群比较关注车辆的到达时间而对步行时间的关注次之。不同学生群在站点选择时对于步行时间和校车到达站点的时间偏好往往是不同的。因此，一般会随着学生群的不同而有所差异。

2.2.3 单位人数上车时间的描述

以往路径优化问题都是在假设单位乘客上车时间相同的情况下进行车辆总运行时间的计算。但是，在实际的运行过程中，乘客的上车时间与站点乘坐该车的总候车人数是相关的。而对于该小学而言，单位时间上车的人数也是需要关注的，因为校车数量是有限的，因此只有确保在固定的时间内达到最多的上车人数，这样才能保证现有的校车资源被充分使用。

三、校车路线的优化

3.1 线路的优化理论

3.1.1 双层规划

双层规划(Bilevel Programming)是在研究非平衡经济市场竞争时首先提出的。Bracken和Mcgill在1973年提出了双层规划数学模型。1977年，在Candler和Nonton的科学报告中，正式出现了双层规划和多层规划名词。从20世纪80年代起，双层规划开始引起大家的关注。双层规划的研究在数学规划领域里有了迅速的发展，现在已经成为一个新的运筹学分支。

双层规划问题一般描述为；上层先给定一个决策，下层各子系统则以这个决策为参量，根据自己的目标在可能的范围内选定一个最优决策，并将自己的最佳反应反馈给上层，上层再在下层的最佳反应的基础上，在可能的范围内作出整体的最优决策。

双层规划研究的是两个各具目标函数的决策者之间按有序和非合作方式进行的相互作用，上层决策者优先作出决策，下层决策者在上层决策信息下按自己的利益作出反应，由于一方的行为影响另一方的的策略选择和目标的实现，并且任何一方又不能完全控制另--方的选择行为，因此上层决策者要根据下层的反应做出符合自身利益的最终决策。

双层规划问题的一个重要特点是可以应用在双层决策问题中，在两个层次上的决策者都有其各自的目标函数，在某种程度上，本层的决策空间是由另一层决定的。此外，本层上的决策者通过特定的方法和手段影响另一层的决策制定，从而达到优化其自身目标函数的目的。双层规划问题的另一个重要特点是决策变量的控制权分别属于各层的决策者，而在传统的单层规划中，决策者同时控制所有的决策变量。但在很多的实际决策过程中，对决策变量的控制和处理并不是同时进行的，而是采用自上而下的双层决策方法。

在双层规划中，以优化自己的目标函数为目的的决策者在高层决策者事先确定决策变量值之后，对自己能控制的决策变量进行优化，以达到最优目的。双层规划比单层规划具有优势，包括能够明确建模表示顺序决策过程的能力，能够明确表示不同层次优化过程或不同决策系统之间的相互作用的能力 3.1.2 遗传算法

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等

领域。它是现代有关智能计算中的关键技术。

对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型：

?maxf(X)??x?R?R?U?3?13?2 3?3式中x为决策变量，式3-1为目标函数式，式3-2、3-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。 遗传算法的基本运算过程如下：

1)初始化:设置进化代数计数器t?0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

2)个体评价：计算群体P(t)中各个个体的适应度。

3)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

4)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。

5)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。

6)终止条件判断:若t?T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼进最优解。

遗传操作包括以下三个基本遗传算子(genetic operator):选择(selection)；交叉(crossover)；变异(mutation)。这三个遗传算子有如下特点：个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。

1）选择算子

选择算子是决定父代种群中每个个体都以多大的可能性被遗传到下一代的进化操作，它模拟的是“优胜劣汰、适者生存”的自然进化原理。选择算子以对

个体的适应度评价为基础，其主要作用是对GA 的搜索提供导向：挑选优秀个体，使算法避免无效搜索且能以较快的速度搜索到问题的最优解。

2）交叉算子

在生物的自然进化过程中，两个同源染色体通过交配重组，形成新的染色体，从而产生出新的个体或物种。模拟这种交配重组过程的进化操作即交叉算子。

本文求解公交静态调度模型选择实值编码，表3-1中列出三种适用于实值编码的交叉算子。

表3-1 交叉算子列表

算子名称 交叉1 （线性重组）

算子说明

两个父染色体a,b的所有基因位以相同的幅度? 交叉，生成子代个体

a',b'，每个基因位的取值为?L,R?。

a'??a?(1??)?b??b'??b?(1??)?a? ?if a'(b')?L then a'(b')?L???if a'(b')?R then a'(b')?R交叉2

中间重组与线性重组相似，只是每个基因位对应不同的幅度进行交叉。

（中间重组）

交叉3

对父染色体的各个基因位进行等概率随机选择，生成子个体。

（离散重组）

3）变异算子

变异算子独立地分别作用于种群上的每一个个体上，以某种概率方式生成变异后的个体。下表列出两种适用于实值编码的变异算子。

表3-2 变异算子列表

算子名称

算子说明