校车路径规划问题

1、关于校车路径规划模型的建立与分析摘要本文就校车路径规划的问题，要求我们查阅相关学校的上学放学时间，充分调研各个学生的家庭住址和北京市交通情况，综合考虑校车运营方式和盈利方法，对实际的校车运营问题进行分析。我们采用了图论的方法，假设了两个运营方案，推导了不同情况下成本与盈利之间的计算关系，阐述了不同运营方式所产生的费用的的不同情况并对不同的校车种类和运营方法之间的异同进行比较，做出了简单评价最后针对综合结果基于以上分析计算后的最佳建议。本次建模以完成接送每个学生上学放学为要求，以盈利最大化为最终约束，并依据校车种类不同，费用不同，载客能力不同提出了两个主要运营方案模型。首先，我们通过对每个学生家

2、庭住址的研究，我们利用网络地图对他们的地址进行了精确的经纬度定位。之后我们充分利用AUTOCAD等工具将所有的地址信息抽象成118个点，画出了目标对象住址的点状分布图。再然后我们做出大胆的分析与化简，将距离较近的点合理分区，利用EXCELL统计该分区数据信息，将不同分区的所有点经纬度坐标求和取平均值，获得了每个分区的重心点，这样一来我们获得了以重心点作为简化点位置并依据人数多少确定简化点权重的简并点。采用上述一系列分析处理和简化后 ，我们获得了包括学校在内的二十一个点。然后我们采用图论的方法进行一系列复杂的计算，并最终获得了最佳的校车路线。最后我们可以分别计算其成本与收益，进而评价校车运营经济

3、上的可行性。关键词校车路径、非线性规划、成本、最短距离、最优化1 问题的重述校车是很多学校为学生提供的人性化服务，北京市某中学打算给一年级新生开行校车。题目中向我们提供了一年级新生的所有的住址信息，要求我们综合考虑学校的上下学时间，以及该时间相关道路的交通状况及校车站点与学生家庭住址之间的距离，以及校车开行的成本、收费等问题，给出校车的开行方案。题目中要求收费方案中应当包括所需校车数量、校车运行路径、收费标准这三个内容。另外，学校并不打算为开行校车提供资助，所以在模型设计中应注意校车购买、运行费用应与收费相抵。2 问题分析本文就校车路径规划的问题，要求我们综合考虑学校的上下学时间，以及该时间相

4、关道路的交通状况及校车站点与学生家庭住址之间的距离，以及校车开行的成本、收费等问题，给出校车的开行方案。我们首先应当查阅相关学校的上学放学时间，充分调研各个学生的家庭住址和北京市交通情况，综合考虑校车运营方式和盈利方法，对实际的校车运营问题进行分析。本题所给的点数量较大，我们在采用了图论的方法时，很难对大量点进行研究，因此我们需要对其进行简化。简化的过程即是确定站点位置的过程。简化后 ，我们获得了包括学校在内的数量较少的点。然后我们采用图论的方法进行一系列复杂的计算，通过考量各站点之间距离和各道路交通状况可最终获得了最佳的校车路线。最后我们可以分别计算其成本与收益，进而评价校车运营经济上的可行

5、性。3 模型的假设与符号说明3.1模型的假设（1）对于学生的家庭住址，极为特殊的的点我们做省略处理（2）对于学校的上学放学时间，我们随机调研了北京几所中学的情况并取其平均时间节点作为本题学校的校车运行时间点。（3）为简化模型，站点与站点间我们直接简化为两点之间的距离，而不考虑北京市实际曲折路线图。（4）上学的去程和放学的回程我们看做是原路去和回，距离相同。3.2符号说明 购置校车的费用开行校车平均每个月的成本（固定成本购车费在中，这里不包含） 表示第个停靠站点为从站到站的距离每个月付给司机的工资以及校车护理费，唯一固定值4 模型准备首先我们将题目附件中所给的地址转化为坐标点（见附录），然后利用

6、AUTOCAD将题中所给的有效点描绘如下在本题中，由于所给的点数量较大，我们在设计校车路线时，不可能到每个家庭住址停靠，所以很难对大量点进行研究，因此我们需要对其进行简化。首先我们简要计算经纬度与距离间的对应关系。假设地球直径为，那么每一度之间所夹的距离为我们在对密集的点进行分区时，选取原则为：各点间的最大经纬度只差不超过，即距离为这被认为是步行可以接受的距离。分区图：经过上述方法简化后，我们得到了了简化点图接下来，我们可以利用最优化和图论方面的相关知识解决该问题。5 模型的建立与求解由于校方是并不打算为校车的开行提供资助的，那么学校开行校车就完全得靠学生交钱来达到收支平衡，而作为每个学生成员

7、来说，每次坐校车所花的钱是越少越好，这样我们就尽可能使开行校车的总花费越少越好。根据市场的调查，我们发现作为中学的校车的基本上都是由客车充当的或者改造的。经过市场价格的比较，我们挑选出了两种比较常见适合作为校车的客车，型号参数分别如下：（1） 宇通客车ZK6119H2Y 满载人数60 价格38万 每百公里油耗21升（下面简称A型校车）（2） 宇通客车ZK6892D 满载人数40 价格14万 每百公里油耗15升（下面简称B型校车）由于我们需要接送118个学生，所以我们为了尽可能达到满员，而避免空间的浪费，下面有两种采购方案，即：方案（1），采购两辆A型校车；方案（2），采购三辆B型校车。我们先讨

8、论方案（1）经过分析，我们根据118个学生的住宅分布情况分析，最后选取了20个校车停靠站点，方便校车的接送，如图所示，分别标记为到。其中，为了适应画图工具的精度限制，各点的坐标做了处理。首先将各个坐标扩大100倍，然后将（3900,11600）规定在原来原点的位置。故得上图各坐标点。这样我们的目标函数即为约束条件为（1）校车容量限制：每辆车的乘客数不超过其载客量；（2） 乘客乘车限制：每位乘客只能乘坐一辆校车；（3） 校车经过站点的限制： 表示任意站点一辆校车只能通过一次表示任意站点至少有一辆校车通过。（4） 实际情况限制：早上去学校的每辆校车的终点站必须是学校（下午返程可看做是原路返回，故不

9、考虑下午回程），总共20个站点，我们将学校看成这20个站点之后的站点，算做第21个，这样有：即每辆车最后必须到达学校校车到达学校后即停止运营。综合上面的陈述，我们的模型简化为下面的最优化问题：根据上面的目标函数以及约束条件，可以知道这是一项非常复杂数据庞大的优化问题，我们考虑将算法简化，但依然能够满足上述的条件。由图论所学相关知识，我们采用以下的试探算法。算法：1)输入校车的容量，2)输入校车的总数3)在给定校车数下，首先确定出距离学校最远的个站点，利用这些站点与学校分别作直线，确定出条线段，定义为条初始线路，记最长线路的长度为；4)对每条初始线路进行站点补充：在剩余的站点中，把离自己最近(即

10、点到直线距离最小)的站点并入该路线中，若此时新的线路长度依然小于最长初始线路的长度，则继续重复补充站点；否则停止补充转(5)；5)若所有站点已考虑，则转(6)否则从初始线路出发，首先将离最长初始线路最近的点加入到该线路中，计算其长度记为，令，转(4)；6)在站点补充完毕后，计算每条线路上乘客的人数，安排校车，若校车的载客量满足均衡要求，则停止，否则对相邻线路上距离最近的站点上的乘客进行互补交换，直到满足要求由于之前我们建立了平面直角坐标系，而且每个点的坐标已标出，这样我们可以算出每个点之间的最短线段距离，由于数据量比较大，我们用matlab变成得到每两点之间的距离（程序见附录），并用表格形式呈

11、现（从上到下依次是到，从左到右是到和最后一列是点代表学校） 0 2.3800 5.4341 2.7906 1.8738 4.0628 1.7084 0 0 6.8520 5.0279 3.6184 4.4770 2.2000 0 0 0 3.5700 3.5606 3.0250 4.6528 0 0 0 0 1.7123 4.0317 3.2803 0 0 0 0 0 2.6753 1.6179 0 0 0 0 0 0 2.5442 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

12、 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.7514 4.5943 15.8425 8.1345 6.7620 10.8836 13.0303 1.2162 2.5230 13.4892 9.2459 4.4397 8.5742 11.7341 5.6358 7.4712 19.4725 2.8002 10.9418 14.9362 11.7659 4.0289 6.7824 18.5014 6.3532

13、9.4672 13.6014 13.8107 2.4857 5.1100 16.9612 6.2715 8.0139 12.1376 12.3107 3.3522 4.5210 16.4657 4.8747 8.1214 12.0130 9.7837 0.9849 3.5032 15.3576 7.1070 6.4661 10.5705 11.3523 0 2.8736 14.4918 8.0517 5.5300 9.6519 11.4380 0 0 12.0325 9.3122 3.7054 7.4921 9.4192 0 0 0 20.9866 9.0898 5.0629 14.7308

14、0 0 0 0 12.9733 16.7673 11.1399 0 0 0 0 0 4.1346 11.6054 0 0 0 0 0 0 12.9552 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18.6183 17.2963 13.6338 4.7630 6.5340 11.5403 1.1323 17.3404 18.2579 14.9063 7.1418 8.7247 13.6465 3.3634 16.8290 11.9173 8.2

15、016 5.1835 8.4811 13.0406 4.4558 19.2317 15.3606 11.4513 2.5181 5.3835 10.3118 1.6807 17.8057 15.4332 11.7614 4.2101 6.8207 11.8306 1.0240 15.2060 13.7835 10.5399 6.4740 9.3916 14.3435 3.6396 16.9291 16.1953 12.7465 5.7021 7.9825 13.0178 1.9052 17.0448 17.1016 13.7045 6.3189 8.2838 13.2915 2.4490 14

16、.9923 17.8336 14.9163 9.1636 11.1148 16.0912 5.2972 17.9860 28.4450 26.2962 20.5878 21.5368 25.9043 16.8509 15.6397 9.1622 5.6710 7.6593 10.9659 15.2030 7.2169 16.8611 21.5294 18.6040 11.4983 12.6091 17.2456 7.7978 17.4706 24.9153 22.3015 15.5952 16.4740 20.8809 11.9305 5.6114 15.1192 14.4710 16.250

17、0 19.1290 24.1167 13.1111 0 16.8709 17.5621 21.6054 24.5964 29.5369 18.6473 0 0 4.2319 16.0826 19.1715 22.4166 16.3680 0 0 0 11.9459 14.9750 18.1981 12.6251 0 0 0 0 3.3141 7.9581 3.8711 0 0 0 0 0 5.0359 6.0981 0 0 0 0 0 0 11.1334按照上述算法得到两条路线：分别计算第一条和第二条线路的总长度为:然后同样按照上述方式讨论方案（2），即购置3辆B型客车。得到类似的模型：同样按

18、照方案（1）中的算法，只是把输入客车容量和客车辆数改为得到三条路线：分别计算三条路线的总长度：增设变量Y，Y表示对每个学生的年收费。经过市场调研，得数据，每位司机每月工资及每辆客车护理费总计4000元,每年每人保险以200元记,每升油价按照7.5元记,每个月按照20天上学日计算，每天接送四次。对于A，对于，由于学校不打算提供资助，为保证费用相抵，对于可得方程：最终算得元对于可得方程：最终算得综合比较，选用第二种方案。6 模型的评价与优化由于校车的路径规划受制于多方面的影响，学校上课时间，交通状况，实际线路的可通行性，甚至节假日的一些特殊情况，有些因素是完全无法量化考虑的，即使量化了其复杂程度也

19、不可能在这里呈现出来。我们组做了大胆的假设与简化，首先乘车的学生有上百多人，于是我们参照实际情况，既竟可能的让校车停靠的点少，又确保每个学生都能方便上车，所以我们简化出了20个停靠站点，并建立适当的平面直角坐标系中显示这些点，然后我们以最短路径为目标函数，列出了一系列的约束条件，建立非线性规划问题。我们想到图论里面求最短路的Floyd算法，然而由于这里还要考虑学生上车后不能超载的安全问题，于是我们再受到图论里求最小树的算法，从最小的距离开始试探，最后求出一条满足所有约束条件的路径，这是整个模型的亮点所在。最后求出最短路径之后，我们把油价，购车费，护理费等等考虑进去之后，得出成本。最后制定合理的

20、收费方案。但是模型的不足也比较明显。主要是少了时间限制这个比较切实的限制条件，一般中学上课时间为8点，为体现人性化，我们的校车最好早上6：30从第一站出发，然后争取7:50之前到达学校，所以我们不可能让校车慢慢悠悠走过所有站点把学生全部接到位。这样我们就需要查到校车的行驶速度，同时这样北京市每天的交通状况又是影响时间和速度的一个重要因素。所以在优化模型这一点上，依然有许多工作要做。我们需要查找我们设计好的路线都通过哪些主干道和支路，以及每天进行上学和放学的高峰段实地检测客流量和汽车的平均速度，或者通过相关部门网站利用已有数据进行一个估算，然后可以预测到整体的一个交通状况对汽车速度的影响是波动的

21、，同时又是周期性的，我们可以根据估算或者测定数据来把交通状况对速度的影响做一个含三角函数的曲线，或者是一个含正态分布因子的式子来模拟速度随时间与不同天数的变化。最后我们再根据速度和路径经过的实际距离，来算出整个校车接送学生到达学校的时间满足我们设定的时间作为限制条件即可。但考虑我们的有限数据量，以及这个优化后的复杂程度，我们的模型不可能面面俱到，精确无比。但我们的模型能够对整体的校车路径规划和大体制定收费方案是绰绰有余的。附录学生编号学生家庭住址经纬度1北京市北京丰台梅市口路12号路39.892,116.2722北京丰台东大街东营里5号院39.85629,116.298563太平路甲34号43

22、9.90065,116.293824北京市丰台区京铁家园2区39.8981,116.2825北京市海淀区复兴路40号院39.90584,116.256146玉泉西路甲3号39.91216,116.245417京铁家园三区5楼39.8950,116.27958北京市海淀区复兴路40号院39.90584,116.256149北京市丰台区靛厂村39.8876,116.288910北京市大兴区富强东里院40号楼39.7408,116.340611北京市市辖区海淀区太平路46号院39.89784,116.2644412海淀区复兴路20号院39.91123,116.3174013北京市市辖区丰台区京铁家园

23、3区6号39.8948,116.279214永定路西里7号楼39.90544,116.2630715北京市海淀区玉泉路68院新1楼39.90286,116.2529916北京市海淀区永定路西里39.90566,116.2630317北京市丰台区莲怡园1号院2楼39.8897,116.297818北京市海淀区太平路22号院39.9095,116.25819北京市海淀区玉泉路68号12楼39.89892,116.2533920北京市丰台区兴景路229号院省略21丰台区周庄子39.8687,116.287622北京市海淀区永定路西里5号楼39.90547,116.2629923北京市石景山区鲁谷路远

24、洋山水7号楼39.9029,116.239524北京市市辖区大兴区西红门宏盛家园39.7975,116.340025北京市海淀区北太平路18号39.90416,116.2589126丰台区东大街6号院22号楼39.86223,116.2988627机械三处宿舍239.9426,116.32828北京市海淀区西黄新村北里11号楼39.9381,116.205029丰台区青塔东里2439.8971,116.269030丰台区程庄路16号院39.85894,116.2662031丰台区莲路十号院2号楼39.8961,116.271132北京市丰台区岳各庄西府颐园畅和园1号楼39.88315,16.2

25、682433北京市市辖区海淀区复兴路40号68楼39.90753,116.2557534北京市丰台区长云路2号院18号楼省略35北京市丰台区望园东里7楼39.8684,116.288736北京市石景山区玉泉西里远洋沁山水三期15号楼39.9045，116.235837北京市石景山区远洋山水22号楼39.9030,116.239338模式口中里22栋39.9358,116.163439张仪村路4号院39.88667,116.2316640太平路46号20楼39.89920,116.2603741北京市海淀区沙窝村南西郊苗圃平房39.9655,116.631642复兴路号9楼39.90766,11

26、6.2808243北京市海淀区金沟河路5号828楼39.91828, 116.2686744北京市海淀区西翠路5号今日家园6号楼39.90200, 116.2789545西翠六今日家园号楼39.90195, 116.2791246太平路34号239.90037, 116.2729447北京市石景山区何家坟39.9099, 116.245648北京市丰台区青塔小区秀园1139.89151, 116.2609349北京市海淀区万寿路40号39.9100, 116.295650安徽省安徽省金寨县双河镇省略51北京市石景山区鲁谷路7439.90421, 116.2450952北京市海淀区玉泉路68号院

27、30楼39.89894, 116.2533153北京市丰台区太平路34号院2号楼39.90035, 116.2729254北京丰台区大成里蔚园3号楼39.9003, 116.26455沙窝南苗圃小2楼39.9018, 116.28156复兴路32号院7楼39.90633, 116.2700257大成里秀园号楼39.8927, 116.262158北京市海淀区玉泉路68号院31楼39.89887, 116.2533959太平路27号院33楼39.97168, 116.3690760京铁家园一区三号楼39.9005, 116.27961丰台区小屯路博龙家园5楼39.9003, 116.25562玉

28、泉路65号院8号楼39.90052, 116.2526663复兴路26号院73楼39.90771, 116.2808664北京市市辖区丰台区大成路13号院3号楼39.89300, 116.2650065北京市市辖区海淀区太平路24号23楼39.90067, 116.2735666北京市海淀区复兴路40号西院39.90746, 116.2559567北京市市辖区丰台区丰台区朱家坟三里7楼39.8092, 116.190968北京市市辖区海淀区复兴路40号10号楼39.90750, 116.2557869北京市市辖区石景山区五芳园2639.89983, 116.2271770北京市市辖区海淀区采石

29、路13号院18楼39.89894, 116.2599071北京市市辖区丰台区大成里小区秀园19楼39.8964, 116.263372北京市海淀区复兴路46号3号楼39.90641, 116.2542773北京市市辖区海淀区北京市海淀区玉海园二里7号楼39.9261, 116.25374北京市市辖区海淀区太平路22号18号楼39.90055, 116.2867475北京市市辖区海淀区复兴路40号院78楼39.9060, 116.256176石景山区玉泉西里二区1439.9042, 116.238477北京市市辖区丰台区双林苑3号楼39.8756, 116.256578北京市市辖区丰台区北京市丰

30、台区302医院新楼39.8918, 116.27679北京市石景山区八角南路17楼39.91118, 116.2003780北京市市辖区石景山区石景山区重聚园639.8958, 116.227281北京市市辖区海淀区北京市海淀区复兴路83号院39.90789, 116.2582482北京市市辖区海淀区复兴路4039.90786, 116.2558483北京市市辖区丰台区小屯路兆丰园小区939.8958, 116.248484北京市市辖区海淀区复兴路34号建一楼39.90738, 116.2691985北京市市辖区海淀区永定路派出所*复兴路40号18楼39.90742, 116.2560386北

31、京市海淀区太平路甲20号39.90063, 116.2939587北京市市辖区门头沟区滨河西区皓月园3号楼39.93406, 116.1127688北京市市辖区海淀区太平路24号院23号楼39.90057, 116.2844689北京市海淀区西翠路5号今日家园6号楼39.90208, 116.2788690北京市丰台区靛厂路26号院5楼39.88983, 116.2851591北京市石景山区衙门口市运八场宿舍39.8906, 116.211392北京市市辖区丰台区青塔东里大理石厂15楼39.8983, 116.270793北京市复兴路26号院23楼39.90768, 116.2809594北京

32、市市辖区海淀区复兴路32#院1号塔39.9086, 116.266995北京市市辖区房山区长阳碧桂园A区739.76110, 116.1619896太平路24号2楼39.90067, 116.2844697北京市市辖区海淀区太平路22号院39.9103, 116.25898北京市石景山鲁谷小区39.9037, 116.222699瑞海家园A1939.7866, 116.328100海淀区复兴路32号院39.9121, 116.267101北京市永定路98号院39.9092, 116.266102北京市丰台区东大街西里3号楼39.86266, 116.29225103北京市丰台区小屯路东里1号3#39.8934, 116.2566104复兴路32 号院239.90628, 116.26987105丰台区东大街20号院39.8650, 116.294106北京市海淀区复兴路J36号39.90735, 116.26663107北京市市辖区海淀区定慧寺39.9228, 116.2749108北京市市辖区丰台区北京市丰台区大屯村39.8818, 116.2612109北京市海淀区永定路127号教工楼39.90271, 116.26436110北京市市辖区丰台区丰台区怡海花园富泽园5号楼39.8369, 116.29881