公交车排班模型

问题背景

随着X市经济的快速发展，公交车系统对于人们的出行扮演着越来越重要的角色。在公交车资源有限的情况下，合理的编排公交车的行车计划成为公交公司亟待解决的问题。以下给出公交车排班问题中的部分名词说明和假设。

（1）班次：1辆公交车从起点出发到达终点停止为1个班次。

（2）公交车公司有两种类型的班车：单班车和双班车。除非特殊说明，单班车和双班车都可以用于公交车排班。

（3）单班车：由同一个驾驶员驾驶的公交车。单班车通常要求在早高峰跑2-3个班次，晚高峰2-3个班次，一天不超过5个班次。

（4）双班车：由两个驾驶员驾驶的公交车。双班车要求上、下午各一个司机，上午和下午司机的工作时间尽可能均匀，并且都不超过8小时。每辆双班车一天运行不超过10个班次。

（5）公交车运行的单程时间，已经包含乘客在各站(包括起点和终点)的上下车时间。

（6）假设每辆公交车可以运行1整天不需要加油。

（7） 末班车的发车时间，可以在原有发车间隔的基础上调整2分钟（±2分钟）。

（8）本题以简单的环路公交路线为例，即公交车从A点出发，经过一系列站点后再次回到A点为1个班次。

（9）最短停站时间是指公交车完成1个班次之后，开始运行下一个班次之前，需要在终点停留的最短的时间。在问题1-3中，每辆公交车的最短停站时间为0，即：公交车回到终点后不需要停留，可以继续进行下一班次的运行。

问题1: X市2路公交车，从X市火车站出发后经沿途站点后回到X市火车站，2路公交车行车信息如表1:

请建立数学模型，计算X市2路公交车，在早高峰时段(6:00-8:00)运行所需要使用的最少公交车数量(需要给出含单班车和双班车各多少辆)。

假设：各时间段内各班次的发车间隔都相等

设置如下符号：

因为第一问只研究早高峰段，所以如何控制这个时间段内数量最少是需要考虑的（局部最优）。

由题可知，双班次车的使用率最高（一天运行不超过10个班次），所以尽可能多的投入双班次车，尽少量投入单班次车，能有效减少公交供应量。

并且，在这一问中，单班次与双班次车并没有本质的区别。（这个很致命）

因为在高峰段，车辆行驶一圈的时间为80min，即只要在2h的前80min不断保证有车辆输出，就能够保证这些车辆维持一个循环，其中前40min出发的车行驶了2圈。

所以保证单班次车在前40min发出，既能保证班次不少于2次不多于3次的约束。

这里让单班次车为1辆，即M11=1

所以得到：

LINGO求解结果如下：

即总共投入16辆公交车，其中单班次1辆，双班次15辆。

（这个含参数的线性规划问题除了用LINGO还真的不知道该怎么解）

问题2. 在问题1的基础上，请建立数学模型并设计相应的求解算法，给出X市2路公交车完成一整天的运行所需要最少的公交车的数量(需要给出含单班车和双班车各多少辆)，并按照表2的格式给出公交车排班计划表。

局部最优是不是整体最优呢？？ 不知道

这里仍以这16辆车为投入的总数，那么只要能够求出各时段的班次数，进而得全天的班次数后，我们就能对全天进行排班，再看是否满足约束。

运用Lingo求解得出早高峰间隔时间为5分钟，早平峰间隔9分钟，晚高峰间隔时间6分钟，晚平峰间隔7分钟，全天所需的最少公交车数为16辆，其中单班车1辆，双班车15辆。最后所求得的最小班次为119班经排班发现，满足约束。

故局部最优（16辆）为整体最优。