校车调度问题.doc

关于校车车辆调度相关问题的研究摘要本文主要研究校车购买和调度的一系列问题，采用整数非线性规划、最小路径、统计检验、决策分析等方法，通过Matlab、SPSS、lingo等软件求解这6个问题。我们首先对附录中的数据进行数据分析得出教师与学生的乘车规律，及校车发车规律。其次对6个问题作出相应解答，下面作如下陈述：针对问题一的第一问，我们采用整数规划的方法，将最小租车费用作为目标函数，根据题目附录中的条件给出人数与车型之间的关系函数形成约束条件，通过lingo求得最小租车费用为13000元；之后否定第一问中的约束条件寻找在最小租车费用下的其他租车方式，通过lingo解得第二问的答案。针对问题二，我们使用图论中的floyd算法，将分析处理过的附录3数据，导入matlab，作出两校区的交通网络图，将每个路口化为有标号的点。之后以交通网络图中每段道路的平均行驶时间作为图中每个点与点之间的权，可以得到一个邻接矩阵F，使用floyd算法寻找到校车最短的行驶时间为0.5833小时约为35分钟，及其最短路径20-85-62-4-39-38-16-14-21-22-13。针对问题三，我们建立了一个供求关系模型。通过题中所给附录，使用SPSS对运输公司的运行规律进行分析。将零散的发车时间整理成为固定的发车班次时间，一个班次可以发多趟车。对整理过的数据使用K-S检验方法考察其正态性，得出教师在每个工作日的每一发车时间段的人数是服从正态分布的结果。之后使用比较均值中的单样本T检验获得每个发车班次的乘车人数均值及其95%置信区间，以区间上界向上取整之后的数值作为结果，从而得到教师在工作日每个班次的乘车人数。问题四、五、六，我们使用了相同的模型构架，并将三道题化为三个不同的分支问题。针对问题四，我们使用了图论中的最大流方法。根据问题二的结果，得到校车往返的平均时间为70分钟。则在教师乘车高峰期时，可能无法及时完成调度，因此必须购买足够多的校车来满足在高峰期时的最大需求量。由于本题不考虑运营成本，所以只要满足17:15的高峰期即可。基于以上分析，我们给出以最小购车花费为目标函数，满足高峰期流量为约束条件的lingo程序，解得最小购买额257.2564万元，及购买方案7辆车。同时还给出最优调度方案。针对问题五，考虑到在满足教师乘车需求前提下要使运营成本最低，从而必须考虑到，除了满足下午的教师乘车高峰客流量以外，还要满足早上的乘车高峰客流量的调度方案。以耗油量最少为目标函数，以满足早上下午高峰客流量为约束条件，通过lingo求解出最优的调度方案，即1、2、3号车行驶单边的次数分别为6、16、6及年总花费额28.8305万元。针对问题六，我们在建立决策模型时，使用教师乘坐校车的满意度和学校组建车队的净利润做为双重标准来作为决策变量。满意度是由教师上车的平均等待时间衡量的。组建校车队的净利润是根据学校的具体情况计算得到。解答中定义，只有在教师乘坐的校车的满意度低且组建校车对学校有正净利润时才选择组建校车队，否则均不组建。根据所给决策模型，估算出学校应该组建车队，同时每年大约会盈利9万元。并且在问题六中归纳总结了一套模型算法。【关键词】最大流 K-S检验 整数规划 Floyd算法 决策分析1.问题重述问题一：1、在某次会议上，学校租车往返接送参会人员从A校区到B校区。参会人员数量、车辆类型及费用等已确定（见附录1）。（1）最省的租车费用为多少？ （2）最省费用下，有几种租车方式？问题二：两校区交通网路及车辆运行速度见数据文件（见附录2）。试确定两校区车辆的最佳行驶路线及平均行驶时间。问题三：学校目前有运输公司经营两校区间日常公共交通，现已收集了近期交通车队的运行数据（见附录3）。（1）试分析运行数据有哪些规律，（2）运输公司调度方案是根据教师的乘车时间与人数来制定的，若各工作日教师每日乘车的需求是固定的（见附录4），请你根据运行数据确定教师在工作日每个班次的乘车人数，以供运输公司在制定以后数月调度方案时使用。问题四：学校准备购买客车，组建交通车队以满足教师两校区间交通需求。假设：（1）欲购买的车型已确定（见附录5），（2）各工作日教师每日乘车的需求是固定的（见附录4），（3）两校区间车辆运行时间固定为平均行驶时间（见附录2）若不考虑运营成本，请你确定购买方案，使总购价最省。问题五：若学校使用8辆客车用于满足教师两校区间交通需求。假设：（1）8辆客车的车型及相关数据已确定（见附录6），（2）各工作日教师每日乘车的需求是固定的（见附录4），（3）两校区间车辆运行时间固定为平均行驶时间（见附录2），（4）车库设在A校区，客车收班后须停靠在车库内。请你确定最佳调度方案，在满足教师乘车要求条件下，使该车队运营成本最低。问题六：事实上，教师及学生每日乘车的需求是随机的车辆运行时间是随机的。如果学校考虑是否组建交通车队满足教师两校区间交通需求。请你分析：（1） 应考虑哪些因素？收集哪些数据？（2） 建立合理决策模型，结合相关数据（附录3，附录7），并参考问题4、5的结论，估算模型的解，从而得到合理的解决方案。2.问题分析问题一的第一问是关于整数规划的问题，根据题目所给的数据，建立合理的租车模型使费用最小，同时获得在费用最小的情况下的租车方式。根据上述分析，将租车的数量和乘车人数结合考虑，使用lingo程序算出结果。第二问是基于接触第一问的最优解的情况下，采用遍历的方法否定最优解，看是否有替代的方案。问题二是关于图论的问题，求解最佳行驶路线即是求最短路线，通过matlab先将两校区交通网络图画出，再根据floyd算法求出最佳行驶路线及其长度，再根据表格中的平均行驶速度求出平均行驶时间。问题三的第一问是根据附录三将校车运行数据通过excel分析，得出每个工作日的教师乘车人数，每个时间段的发车班次的规律，和学生在周一至周五与双休日的乘车规律。第二问是根据第一问得出的规律将教师在每个班次的乘车人数固定下来问题四是使用直接观察法，根据第二问可以得到由于汽车往返时间为70分钟（由第二问可知，坐车一次用时0.5833小时），而客流量的最高峰在17:1517:45之间，其他时间段均可使用提前调用车辆来满足客流量。17:1517:45客流量需求总值222,即有足够的车辆能在这个时间段的各个校区的班次，并且车辆总价最小，即为最优购买方案，此时使用lingo求解。问题五是一个多目标规划的问题，与问题四十分类似。要考虑到运营成本的问题，所以除了要保证下午的四个高峰期以外，还要保证早上的一个高峰期。以及车辆的调度问题使得耗油量小，驾驶员成本小。第一目标为满足教师乘车需求，第二目标为运营成本最低。问题六是一个建立决策模型的过程，要知道如何建立决策模型，就必须确定决策变量，而决策变量又是受到哪些因素的限制都是需要我们考虑的。在用建立好的决策模型衡量该学校的情况时，必须将它的数据很好的转化为我们决策模型中的决策变量以达到评价的效果，并给出合理的解决方案。3 模型假设和符号系统3.1模型假设 1）题干中所给假设不再重复叙述2）租用全天的车可以将开半天会的参赛人员送回3）道路口之间的路是直线4）每段道路的路况相同5）平均行驶时间是每段道路行驶时间的加总6）每个工作日相同发车时间点上的教师乘客数服从正态分布7）6种车均为1.6升排量以上的，车辆购置税税率为10%8）校车可以空车往返于两校区之间9）一年教师的工作日为160天，即32周 10）附录六中耗油量单位为升/百公里 11）校车使用的是四川省的0号柴油，7.94元12）3.1.6假设见题5.613）题中所给数据均真实有效3.2 符号系统问题一xij： -车型的数量，=1为租用半天，=2为租用全天，为车辆的类型pij:租车费用，=1为租用半天，=2为租用全天，为车辆的类型Tj:载客量，为车辆的类型ai:是0-1变量，满足给出条件时则为1Wx：是最省的租车费用问题二Vi：交通道路的起点标号Vj：交通道路的终点标号F：问题二中交通路口以通过时间的邻接矩阵R：问题二中路径矩阵D（k）：问题二中的最短时间矩阵问题四M（y）:客车的总购价Pi: 第i种车型的价格，yi: 是第i种车的购买数量，ti: 第i种车的载客量yij:是指在第j个高峰期第i个型号的车问题五i:第i类型的车的载客数量，i=1是第一类，i=2是第三类，i=3是第六类zji:表示第i类型车在早上三个高峰期期的往返次数, :j=1:j=2:j=3C1:早上的高峰期调度最低耗油量C2:下午的的高峰期调度最低耗油量Ni：第i种车型走过的单方向的总次数G:每日校车所花费用G0:年校车花费4 数据分析在对题建立模型时，需要对题中所给数据进行分析。由题中附录三所给数据，我们可用SPSS分析且得到如下结果：4.1 处理方法首先，我们对所给数据进行了如下处理： 分别就A、B两校区、四周，每周周一至周五各时间段的乘车人数进行了环比分析。即比较同一工作日，不同周，各时间段的乘车人数情况。并以发车时间（t）为横坐标；四周内，各工作日在每个发车时间的乘车人数（x）为纵坐标，绘制出10张x-t图。 分别就A、B两校区、四周，每周周一至周五各时间段的乘车人数进行了同比分析。即比较同一周内，不同工作日，各时间段的乘车人数情况。并以发车时间（t）为横坐标；乘车人数（x）为纵坐标，绘制出2张x-t图。 分别就A、B两校区、四周，每周周一至周五各时间段的行驶时间进行算数平均，并同比比较一周内不同工作日的平均行驶时间。以此绘制以发车时间（t）为横坐标；平均行驶时间（T）为纵坐标，绘制2张T-t图。 根据中的平均行驶时间以及问题二中得到的理论行驶时间，计算一周内各发车时间段的校车行驶时间方差。42 A、B两校区一周五天不同时间段的乘车人数对比分析去每一时间段的均值作为固定的发车时间，例如：7：29，7:30,7:31出发的三辆车我们算作7:30这一时点发车；该时点内的教师乘车人数直接加总于是可以得到：A校区发车B校区发车 4.3 通过比对每辆车的往返行驶时间，可以得到校车的平均行驶时间 具体的计算过程见附录3A校区发车表示B校区在每个发车时间点的平均乘客人数和平均行驶时间发车时间周一行驶时间周二行驶时间周三行驶时间周四行驶时间周五行驶时间7:3090.7535.710036.287584.535.587587.7536.37586.535.88:15102.2535.625100.2536.3100.536.259935.02597.537.83759:2524.533.7523.536.2524.7538.252432.7524.253811:4547.2535.62546.7536.12545.7536.54532.2545.535.12513:053.2545.53.536.5937.753.534.253.532.7515:0035.7535.1254538.12535.2535.2545.536.754435.37517:1573.537.272.534.912572.2535.471.536.17573.2535.819:306.536.756.7534.756.5396.2533.50.2532B校区出发表示B校区在每个发车时间点的平均乘客人数和平均行驶时间发车时间星期一行驶时间星期二行驶时间星期三行驶时间星期四行驶时间星期五行驶时间10:3039.535.37541.2533.37539.753739.7536.12540.2537.2511:301036.59.2535.759.75369.2537.59.53712:2519.53819.534.51934.75203619.538.2513:004035.7540.2536.540.535.87539.7535.37540.535.62516:0026.2536.2533.538.53336.7533.536.87532.7536.62517:15109.2536.75115.2537109.536.0625110.2537.0625106.7536.37517:3013.53513.536.513.5371436.513.537.2517:4526.53825.7538.526.7538.526.7542.526.2537.520:3062.2538.2561.25366038.256234.62554.753521:252935.752834.7529.2538.752937.25004.4 A、B校区每个相同的工作日的乘车人士拟合曲线下附A、B各一张，其他图详见附录3A校区星期一乘车人数拟合曲线B校区星期一乘车人数拟合曲线5模型建立与求解5.1问题一5.1.1.1 模型的建立 设租用车的型号及使用方式为xij，租车费用为pij，j型车辆的载客量为Tj，由此可得最省的租车费用可表示为：Wx=min(j2i2pij*xij+j4i2pij*xij-a1*0.2*i2pi1*xi1-a2*0.2*i2pi2)1） 所有车辆所能载客人数必须大于等于开会人数：j4i2xijTj2222） 租用全天一二号车型的辆数所能载客人数必须要大于等于主席团开全天会的人数：j2Tjx2j73)租用全天的-的车型辆数所能载客人数必须要大于等于开全天会的人数：j4Tj*x2j1734) 租用-车型所能载客数量必须要大于等于主席团全体开会人数j2Tji2xij275) 添加0-1变量ai，使得当满足下列条件时有a1=1 0.5*x11+x2130 0.5*x11+x213a2=1 0.5*x12+x2230 0.5*x12+x223由此，可以得到问题一的第一问的模型为Wx=min(j2i2pij*xij+j4i2pij*xij-a1*0.2*i2pi1*xi1-a2*0.2*i2pi2)j4i2xijTj222j2Tjx2j7j4Tj*x2j173j2Tji2xij27a1=1 0.5*x11+x2130 0.5*x11+x213a2=1 0.5*x12+x2230 0.5*x12+x2235.1.1.2模型的求解最终输入lingo程序中求解可得，最省租车费用为13000元。租车的方式为（lingo程序见附录1）：第二种车型 租半天 3辆 第二种车型 租全天 2辆第三种车型 租半天 1辆第三种车型 租全天 1辆第四种车型 组全天 3辆5.1.2.1模型的建立基于第一问的基础上，继续分析题目，添加新的约束条件，即让第一问中租用的车型不等于其原来的解， 建立新的模型，使用lingo计算新的约束条件为：x123 或x222或x131或x231或x2435.1.2.2 模型的求解将新的约束条件加入原来的模型中，通过lingo解得新的方法（lingo程序见附录1）：最省租车费用为13000元租车方式为：第一种车型 租半天 1辆第二种车型 租半天 2辆第二种车型 租全天 2辆第三种车型 租半天 1辆第三种车型 租全天 1辆第四种车型 组全天 3辆5.2 问题二5.2.1模型的建立求最佳行驶路线即是求最短的行驶路线，从而可以求解出从A到B的最短行驶时间也即是平均行驶时间。1） 作图 通过matlab，附录2中的道路转变为二维的交通路线图，图中点与点之间的权为通过两路口所需的时间。由此得到图中交通路口有关时间的邻接矩阵F。2） 定义一个n阶方阵序列D（-1），D（0），D（1），D（k），D（n-1）其中D（-1）ij=arcsijD（k）ij=Min D（k-1）ij, D（k-1）ik+D（k-1）kj 0kn-1 上述公式中，D（1）ij是从 Vi到Vj的中间顶点序号不大于 k的最短时间长度；D（n-1）ij是从Vi到Vj的最短时间长度。通过floyd算法，依次找从Vi到Vj，中间经过结点序号不大于0的最短时间，不大于1的最短时间，直到中间顶点序号不大于n-1的最短时间，从中选取最小值，即为Vi到Vj的最短时间可以得到最短时间矩阵D和路径矩阵R。再通过对矩阵D，R的分析及回溯，得到A校区和B校区所对应的V13和V20之间的最短路径及平均时间。5.2.2 模型的求解）使用matlab编程，算法说明：若从Vi到Vj有弧，则从Vi到Vj存在一条长度为弧上权值（arcsij ）的时间，该时间不一定是最短时间，尚需进行n次试探。（1） 首先考虑从Vi到Vj经过中间顶点V0的时间（Vi，V0，Vj）是否存在，也就是判断弧（Vi，V0）和（V0，Vj）是否存在。若存在，则比较（Vi，Vj）和（Vi，V0，Vj）的时间长度，取较短的为从Vi到Vj的中间顶点序号不大于0的最短时间: arcsij=minarcsij,arcsi0+arcs0j;（2） 在此时间上再增加一个顶点V1，也就是说，如果（Vi，V1）和（V1，Vj）分别是当前找到的中间顶点序号不大于0的最短时间，那么，（Vi，V1，Vj）就有可能是从Vi到Vj的中间顶点序号不大于1的最短时间。将它和已经得到的从Vi到Vj中间顶点序号不大于0的最短时间相比较，从中选出最短的作为从Vi到Vj中间顶点序号不大于1的最短时间。(3)再增加一个顶点V2重复上述这个试探过程。一般情况下，若（Vi，Vk）和（Vk，Vj）分别是从Vi到Vk和从Vk到Vj的中间顶点序号不大于k-1的最短时间，则将（Vi，Vk，Vj）和已经得到的从Vi到Vj的中间顶点序号不大于k-1的最短时间相比较，其长度最短者即为从Vi到Vj的中间顶点序号不大于k的最短时间。（4）经过n次比较之后，最后求得的便是从Vi到Vj的最短时间。按此方法可同时求得V13和V20之间的最短时间。 Matlab具体程序见附录3）计算结果计算结果为平均行驶时间为0.5833 小时，近似等于35分钟。最佳路径为20-85-62-4-39-38-16-14-21-22-13，见下图红色部分为路线5.3 问题三5.31模型的建立与求解由4.数据分析中的数据，可以通过SPSS分析出每个工作日每个发车点的乘车人数呈正态分布，具体的图标见论文附录3同时我们可以看出校车有如下运行规律：不论A或B校区每一周的各个工作日的乘车教师人数趋于固定 A校区每个工作日在早上7:30和8:15两个发车时点是一个工作高峰期，在每个工作日在下午17:15又是一个工作高峰； B校区每个工作日在下午17:15、17:30、17:45为一个工作高峰期 A校区每个工作日在早上9:25，下午1:05，晚上19:30为工作的低谷期 B校区每个工作日在早上11:30，12：25，下午16:00、17:30、17：45和晚上21:25是工作的低谷期。校车在往返于A、B校区间的平均时间一般在3040分钟浮动校车最早的一班都是从A校区发往B校区5.321模型的建立本题是一个运输公司供给与教师乘车需求的问题，我们根据以下分析建立模型：根据附录4：由于每个工作日教师每日乘车需求为固定值，所以题目表达的意思指是每个工作日每个时间段的教师乘车需求固定，即剔除由于星期的不同导致的教师乘车人数不同这一因素。因为题目中已给出了教师的乘车需求，而运输公司需要提供的是教师乘车的供给。根据对附录3所给的运行数据进行分析，详细分析过程与数据参见4.数据分析和附录7，我们发现每天同一发车时间，不同工作日的乘车人数并不相同。即是说虽然每日的教师乘车需求是固定的，但是任然可能出现乘车人数超过或低于固定需求的现象。我们以附录3中每个发车点的数据可信度不低于95%的置信区间的上界为工作日每个班次教师的乘车人数，以此保证尽量不出现乘车人数大于已有车辆最大可承载人数，因为在此情况下最可能保证乘车人数的供给是大于需求的。对附录三中的每个发车时点教师乘车数据进行正态性检验，使用SPSS的K-S检验：结果如下：A校区：单样本 Kolmogorov-Smirnov 检验7:30频数8:15频数9:25频数11:45频数N111259正态参数a,b均值1.81821.66674.00002.2222标准差1.25045.778501.581141.09291最极端差别绝对值.289.304.136.206正.289.304.136.202负-.256-.196-.136-.206Kolmogorov-Smirnov Z.9581.053.305.618渐近显著性(双侧)P值.317.2171.000.839单样本 Kolmogorov-Smirnov 检验13:05频数15:00频数17:15频数19:30频数N39104正态参数a,b均值6.66672.22222.00005.0000标准差4.932881.301711.414213.55903最极端差别绝对值.349.234.300.300正.250.234.300.213负-.349-.174-.240-.300Kolmogorov-Smirnov Z.604.703.949.601渐近显著性(双侧)P值.859.706.329.863B校区单样本 Kolmogorov-Smirnov 检验10:30频数11:30频数12:25频数13:00频数N13131313正态参数a,b均值1.53851.53851.53851.5385标准差2.066213.356973.596652.18386最极端差别绝对值.233.410.435.375正.233.410.435.375负-.228-.323-.334-.241Kolmogorov-Smirnov Z.8411.4781.5681.351渐近显著性(双侧)P值.479.25.15.072单样本 Kolmogorov-Smirnov 检验16:00频数17:15频数17:30频数17:45频数N131388正态参数a,b均值1.53851.53852.50002.5000标准差2.10616.518874.342483.16228最极端差别绝对值.306.352.385.313正.306.312.385.313负-.233-.352-.282-.215Kolmogorov-Smirnov Z1.1031.2681.089.885渐近显著性(双侧)P值.175.080.186.414单样本 Kolmogorov-Smirnov 检验20:30频数21:25频数N86正态参数a,b均值2.50003.3333标准差1.927252.42212最极端差别绝对值.352.209正.352.209负-.218-.168Kolmogorov-Smirnov Z.997.512渐近显著性(双侧)P值.274.956由表中的的P值可以看出，每天的各个发车点的教师乘车需求均是服从正态分布的，所以我们可以用单样本T检验将A、B两校区，4月2号至4月27号的20天里，各发车时间的数据导入SPSS软件，运用比较均值中的单样本T检验得出各发车时间乘车人数的均值和95%置信区间：表格 1A校区T检验检验值 = 0 tdfSig.(双侧)均值差值差分的 95% 置信区间下限上限七点三十47.70019.00089.9000085.955393.8447八点十五82.60319.00099.9000097.3687102.4313九点二十五87.30019.00024.2000023.619824.7802十一点四十五81.62419.00046.0500044.869247.2308十三点零五4.20519.0004.550002.28526.8148十五点16.46519.00041.1000035.875446.3246十七点十五116.80619.00072.6000071.299173.9009十九点三十8.98519.0005.250004.02706.4730表格2 B校区T检验检验值 = 0 tdfSig.(双侧)均值差值差分的 95% 置信区间下限上限十点三十97.86519.00040.1000039.242440.9576十一点三十62.22819.0009.550009.22889.8712十二点二十五143.67419.00019.5000019.215919.7841十三点140.29419.00040.2000039.600340.7997十六点19.95319.00031.8000028.464335.1357十七点十五69.58019.000110.20000106.8851113.5149十七点三十101.66619.00013.6000013.320013.8800十七点四十五107.77819.00026.4000025.887326.9127二十点三十48.81919.00060.0500057.475562.6245二十一点二十五8.67519.00023.0500017.488528.61155.321模型的求解对上述数据进行取整整理后的：A校区发车时间-乘车人数T检验7:308:159:2511:4513:0515:0017:1519:30乘车人数（人）941032548747747B校区发车时间-乘车人数T检验10:3011:3012:2513:0016:0017:1517:3017:4520:3021:25乘车人数（人）411020413611414276329根据上面的两表可以得到模型的解：教师在工作日每个班次的乘车人数如下A校区发车时间7:308:159:2511:4513:0515:0017:1519:30乘车人数941032548747747B校区发车时间10:3011:3012:2513:0016:0017:1517:3017:4520:3021:25乘车人数41102041361114142763295.4 问题四5.4.1模型的建立客流量的最高峰在17:1517:45之间的四个高峰点，由于校车来回一个往返需要70分钟，因而从另一校区无法及时调度到有客流高峰的校区，所以考虑到满足最大流量的问题，只要购买的车辆可以满足客流高峰期即可。由于不考虑运营成本，所以在其他时间段均可使用提前调用车辆来满足客流量，在早上7:30到9:25这一期间A校区的班次可以随时调派校车往返。(见下表红色部分)教师乘车固定需求表A校区发车时间7:308:159:2511:4513:0515:0017:1519:30乘车人数881002446444 735B校区发车时间10:3011:3012:2513:0016:0017:1517:3017:4520:3021:25乘车人数401020403310914266230所以17:1517:45客流量需求总值为222,即只要有足够的车辆能在这个时间段的各个校区的班次，并且车辆总价最小，即为最优购买方案.于是可以得到条件： 根据车辆总价最小可以得到目标函数：My=i6Pi*yi+i6Pi*yi1.170.11在每个工作日的17:1517:45这个时间段的三个高峰期内，车辆的载客能力一定要大于其客流量需求总值：i6ti*yi2222. 每一个车型在四个高峰期内的值一定等于其总车辆数： i6j4yij=yi3. 在每个高峰点处的车辆其载客量一定要不小于那一时刻的老师人数：i6ti*xi173i6ti*xi2109i6ti*xi314i6ti*xi426根据上述条件可以建立模型：My=i6Pi*yi+i6Pi*yi1.170.1i6ti*yi222i6j4yij=yii6ti*xi173i6ti*xi2109i6ti*xi314i6ti*xi4265.4.2 模型的求解1） 通过lingo程序可解的答案（程序见附录4）：需购买1辆1号车，3辆2号车，1辆3号车， 2辆6号 车，共花费My=257.2564万元。并且通过调度，使A校区在17:15时有一辆2号车和1辆6号车,B校区有1辆1号车，2辆2号车，1辆3号车，1辆6号车即可。2） 同时我们给出一种满足条件的调度方案 假设开始时车 都停在A校区 1 3 1 2 0 0 0 0 7:30 从A开出3辆2号车到B校区 1 0 1 2 0 3 0 0 8:15 从A开出2辆6号车，辆1号车到B校区 0 0 1 0 1 3 0 29:25 从A开出1辆3号车到B校区 0 0 0 0 1 3 1 210:30 从B开出1辆6号车到A校区 0 0 0 1 1 3 1 111:30 从B开出1辆1号车到A校区 1 0 0 1 0 3 1 111:45 从A开出1辆6号车到B校区 1 0 0 0 0 3 1 213:00 从B开出1辆6号车到A校区 1 0 0 1 0 3 1 113:05 从A开出1辆1号车到B校区 0 0 0 1 1 3 1 115:00 从A开出1辆6号车到B校区 0 0 0 0 1 3 1 216:00 从B开出1辆2号车,1辆6号车到A校区 0 1 0 1 1 2 1 117:15 从A开出1辆2号车,1辆6号车到B校区 从B开出1辆2号车，1辆3号车，1辆6号车，到A校区 17:30 从B开出1辆1号车到A校区17:45 从B开出1辆2号车到A校区 1 2 1 1 0 1 0 119:30 从A开出1辆1号车到B校区 0 2 1 1 1 1 0 1 20:30 从B开出1辆1号车，1辆6号车到A校区 1 2 1 2 0 1 0 021:25 从B开出一辆2号车到A校区 1 3 1 2 0 0 0 0 5.5 问题五5.5.1模型的建立首先，本题与问题四十分相似，但是由于购买的车辆已经确定，且在满足教师的乘车条件下，要使运营成本最低，就必须考虑到在工作高峰时期校车调度的问题，使得油费最省，花费在驾驶员上的费用最少；使得可以满足乘客流量高峰期时的最大流量问题。其次，根据问题二的解答可以得到从A校区到B校区的最短路径长度为36.2公里。所以经过计算Qi=36.2*100qi可以得到：车型跑单次躺车所耗油量Q1为5.34升车型跑单次躺车所耗油量Q2为7.24升车型跑单次躺车所耗油量Q3为8.68升第三，由于要考虑到运营成本的问题，在尽可能节省油耗的情况下，我们必须出去要考虑到问题四中的4个高峰期的调度问题，还需要保证早上的高峰期有车的前提下，调度所耗油量最少。A校区发车时间7:308:159:2511:4513:0515:0017:1519:30乘车人数881002446444 735B校区发车时间10:3011:3012:2513:0016:0017:1517:3017:4520:3021:25乘车人数4010204033 10914 266230因而，需将早高峰的调度与下午的高峰分开来看。早高峰的调度模型：1） 耗油量最小minC1=i3Qi*j3zji 2) 由于校车已经购买完成所以可以得到下面的约束条件：j4zj11j4zj26j4zj313)同时调度方案还必须满足高峰期的教师乘客需求，则可得约束条件：i3z1i*i88i3z2i*i100i3z3i*i24则可得模型一minC1=i3Qi*j3zjij4zj11j4zj26j4zj31i3z1i*i88i3z2i*i100i3z3i*i24晚高峰的调度模型1）耗油量最小minC2=i3Qi*j4zji2） 由于校车已经购买完成所以可以得到下面的约束条件：j4zj11j4zj26j4zj313） 同时调度方案还必须满足高峰期的教师乘客需求，则可得约束条件i3z1i*i73i3z2i*i109i3z3i*i14i3z4i*i26则可得模型二：minC2=i3Qi*j4zjij4zj11j4zj26j4zj31i3z1i*i73i3z2i*i109i3z3i*i14i3z4i*i26在得到最优的调度方案后，计算出每种车型走过的单方向的总次数Ni所以最后可得日花费用为G=13*N1+15*6*N2+17*N3+C1+C2*7.99 年花费为 G0=G*1605.5.2模型的求解1）通过lingo程序可解得答案（程序见附录5） 早上最优调度 7:30 1辆1号 1辆3号， 1辆6号 8:15 3辆3号 9：25 1辆3号 下午最优调度 17:15 A校区 3辆3号车 B校区 2辆3号车 1辆6号车 17:30 1辆1号车 17:45 1辆3号车2） 同时我们给出具体的调度方案：假设开始时车 都停在A校区 1 6 1 0 0 0 7:30 从A开出1辆1号车到,1辆3号车，1辆6号车到B校区 0 5 0 1 0 1 8:15 从A开出3辆3号车到B校区 0 2 0 1 4 19:25 从A开出1辆3号车到B校区 0 1 0 1 5 110:30 从B开出1辆6号车到A校区 0 1 1 1 5 011:30 从B开出1辆1号车到A校区 1 1 1 0 5 011:45 从A开出1辆6号车到B校区 1 1 0 0 5 113:00 从B开出1辆6号车到A校区 1 1 1 0 5 013:05 从A开出1辆1号车到B校区 0 1 1 1 5 015:00 从A开出1辆6号车到B校区 0 1 0 1 5 116:00 从B开出2辆3号车到A校区 0 3 0 1 3 1 17:15 从A开出3辆3号车到B校区 从B开出2辆3号车，1辆6号车，到A校区 17:30 从B开出1辆1号车到A校区17:45 从B开出1辆3号车到A校区 1 3 1 0 3 019:30 从A开出1辆1号车到B校区 0 3 1 1 3 020:30 从B开出1辆1号车，2辆3号车到A校区 1 5 1 0 1 021:25 从B开出1辆3号车到A校区 1 6 1 0 0 0在这个过程中1号车运行 6个单边 一个单边耗油 5.43003号车运行 16个单边 7.2400 6号运行 6个单边 8.6880 所以根据G和G0的公式可以求得：一个工作日耗油 5.43*6+7.24*16+8.68*6= 200.5000 升一个工作日油价费用 现在四川油价7.94元/升 200.5*7.94=1591.97元 支付司机 费用为13*6/2+15*16/2+17*6/2=210 元 每个工作日花费1591.97+210=1801.97 元 每年有两个学期，每学期按16周计算，共160个工作日 每年日常费用为 1801.97*160=28.8305万元/年 每年