财经研究 校车路径规划问题分析 吕腾捷 摘要：随着教育资源的集中和交通运输方式的不断改进，学生上下学大多采用长距离公共交通工具如公交车、出租车等，近 年来，学生交通安全事故频发，引起了大众的高度关注，本文在充分考虑了上下学时间、交通状况、校车站点与学生家庭住址之间 距离、校车开行成本、收费数额等问题的基础上，通过合理的抽象假设，建立了校车安排方案的最优模型，并对此进行了模型推广， 使之能够适用于其他相似的社会情境中，从而指导实践。 关键词：最优路径 成本分析 Ｐｒｉｍ算法 一、问题重述 （一）校车路径规划问题概述 校车路径规划是一个综合性的复杂问题，需要考虑很多因 素，因此如何做到有效安排车辆、提高学生的满意度，在方便 同学的同时尽量压缩成本成为路径规划中必须注意的问题，本 文通过数学建模的方法，综合分析１２１户学生的住址分布，切 实做到从所需校车数量、校车运行路径、收费标准等方面制定 有效合理的开行方案。 （二）模型建立与具体问题分析 本文通过运用统计学、社会学、经济学、程序设计等相关 学科知识，一方面，我们对１２１户学生住址进行坐标定位，并 分析出最优站点位置，从而进一步通过Ｐｒｉｍ算法完成最优路径 的规划：另一方面，我们从实际出发，通过经济学方法对成本 收益及可能出现的堵车等情况进行了综合分析，提出最优收费 标准。此外，为了响应资源节约型、环保友好型社会的号召， 我们提出了使用节能燃料的想法，从而在优化经济效益的同时 降低社会成本，更好地保护环境。 二、基本假设和符号说明 （一）基本假设 １、假设所有乘车点设立在各小区或交通站点，不设立在路 上。 ２、假设校车只在各个点上载人，行驶途中不载人。 ３、假设校车保持匀速行驶，且在途中不会出现突然耗尽燃 料或轮胎报废等意外情况。 ４、假设学生对校车的满意度只与时间有关，而忽略其他因 素的影响。 ５、假设区域中的标明的点可以直接连接，而未标明的站点 必须间接到达。 （二）符号说明 为了便于计算，特设变量如下表所示： 字母 变量 字母 变量 表示 表示 ＸｉＹｉ 家庭住址横、纵 。坐标 ＮＰＶ 净现值 ｘ Ｙ 站点横、纵坐标 Ｒ 听视率 ｎ 样本总数 Ａ 堵车对时间的影响度 Ｔ 最小生成树的形 Ｂ 时间对学生乘车数量 态 ● 的影响度 Ｘ。Ｙ 坐标点集 ｍ 总影响度 Ｉｔ 未来收益总现值 ａ 每位学生收费金额 Ｏｔ 投资成本 三、模型建立 首先，为了更好地确定最优站点，我们对１２１户学生的住 址进行了坐标定位，并建立数学模型完成最优站点位置，通过 Ｐｒｉｍ算法分析出最优路径的规划，而在考虑实际经济问题时， 我们通过经济学方法对成本收益问题分析建立数学模型，提出 最优收费标准。此外，为了响应资源节约型、环保友好型社会 的号召，我们提出使用节能燃料的想法，并通过天然气、汽油 等燃料能耗对比给出最优选择，模型建立如下： （一）最优站点选择 首先对样本进行整理分析，并进行坐标拾取，然后利用散 点分析法剔除较为分散的孤立点数据，并对剩下的散点进行分 类处理，确定出散点集中的区域，对每一类散点利用查找重心 法找出理论上到各个点距离最近的点： ：銎 ：望 ｎ ∞ （二）最优路径选择 首先根据道路的距离以及路况拥堵信息、是否为高速等情 况，综合分析出站点与学校之间的权值，然后利用Ｐｒｉｍ算法求 出最小生成树。下文将详细给出Ｐｒｉｍ算法的计算方法，具体运 算方式见附录中程序： １、初始化：ｘ＝｛ｘ。｝，Ｔ＝｛ｆ）。此步骤设立一个只有结点Ｘｏ 的结点集Ｘ和一个空的边集Ｔ作为最小生成树的初始形态，在 随后的算法执行中，这个形态会不断的发生变化，直到得到最 小生成树为止。 ２、在所有ｘ∈Ｘ，ｙ∈Ｙ—ｘ的边（ｘ，Ｙ）∈Ｔ中，找一条权 最小的边（Ｘ。，Ｙｏ），将此边加进集合Ｔ中，并将此边的非ｘ中 顶点加入ｘ中。此步骤的功能是在边集Ｅ中找一条边，要求这 条边满足以下条件：首先边的两个项点要分别在顶点集合ｘ和 Ｙ—ｘ中，其次边的权要最小。找到这条边以后，把这条边放到 边集Ｔ中，并把这条边上不在ｘ中的那个顶点加入到ｘ中。这 一步骤在算法中应执行多次，每执行一次，集合Ｔ和ｘ都将发 生变化，分别增加一条边和一个顶点。 ３、如果Ｘ＝Ｙ，则结束；否则重复上一步骤。我们可以算出 当Ｘ＝Ｙ时，共执行了ｎ一１次，Ｔ中也增加了ｎ一１条边，这ｎ 一１条边就是需要求出的最小生成树的边。 （三）成本效益分析 由以上模型理论可以得到几条由于其他选择的路径，而在 这几条路径的选择过程中面临着高速与耗油量大的两难选择， 而直接影响到收费标准。因此，必须通过成本收益分析运用数 学模型进行成本收益分析，建立模型如下： 本模型基本公式采用净现值法，即用未来收益的总现值减 去投资成本，即： ＮＰＶ一 一 ｃ＇ｔ 一１５． 新经济２０１４年８月（中） 度，０．８＝１—０．２为道路畅通情况。 由此，我们选择３辆校车，第一辆校车首发时间为６：ＯＯ， 而后每隔５分钟发一次车，最后一辆校车将在６：３０到达。 由于校车运行时间间隔较短，故折现率的影响基本忽略不 计，故以上公式可写为： Ｎ 一ＥＩｔ Ｅ ｃ》ｔ． 以下说明Ｉｔ和０ｔ的计算方法： １、未来收益Ｉｔ的确定： 在确定每个学生收费价格为Ｐ之后，Ｉｔ的值与学生数量多 少相关，而据网络已有的数据资料可得，学生对校车尤其是等 （三）成本收益分析及收费标准 对投资成本的分析方面，校车的耗气量和司机工资构成投 资成本，假定每个司机收取学生的费用为１元／次，则每辆车一 次总收取费用为３２元，由此可确定司机工资为２０元／次，在确 待时间的满意度直接决定着学生选择校车的人数多少。由模型 得出结论可得，堵车率对时间影响度为Ａ，而时间对学生乘 车数量的影响度为Ｂ，由此可得到堵车时段即路径对收益率的 影响程度为一个可得的数量常数为ｍ。由此可得出随着堵车率 一定了司机工资之后，主要考虑耗气量对投资成本的影响，四种 路线分别需要消耗天然气成本费用如下： 路径一：（３．１＋３．５＋３．２＊２＋２．２）／１００．１４．８４＊２．５＝５．６元 变化而减少的未来收益数为ｍａ。 ２、投资成本０ｔ的确定： 校车的耗油量和司机工资构成投资成本，而在工资作为定 路径二：（３．ｉ＋３．５＋４．６．２＋ｉ．７）／１００．１４．８４＊２．５＝６．５元 路径三：（３．１＋６．５＋４．６＋ｉ．７）／１００．１４．８４＊２．５＝５．９元 路径四：（３．１＋６．５＋３．２＋２．２）／１００．１４．８４＊２．５＝５．６元 由成本收益分析可得四种线路的净现值收益分别为： 路径一：ＮＰＶ＝９３ａ一２０＊３—５．６＊３ 值时，主要考虑耗油量对投资成本的影响，为保证高速运行， 会增加耗气量为ｋ立方米，故共增加耗气成本为２．５ｋ。 ３、ＮＰＶ的比较 设共有ｎ人在时间满意时乘车，设正常行驶成本为Ｑ，则 路径二：ＮＰＶ＝９６ａ一２０＊３—６．５＊３ 路径三：ＮＰＶ＝８７ａ一２０＊３—５．９＊３ 路径四：ＮＰＶ＝８１ａ一２０＊３—５．６＊３ 有： 路径一：ＮＰＶ＝ｎａ一２．５ｋ—Ｑ 路径二：ＮＰＶ＝（ｎ－ｍ）ａ—Ｑ 对比四种线路的净现值收益易得，四种路线中路线二利润 值最大，故选择此条线路。 此时我们可以计算出本次校车运行总时间为： ［（３．１＋３．５）／７０＋（４．６．２＋１．７）／５０］＊６０＋３．ｉ＊０．１＋３．５＊０．１＋４ ６＊０．１．２＋１．７＊０．３＝２０．８分 即对比ＮＰＶ即２．５ｋ与ｎａ的数值大小： 当２．５ｋ＞ｍａ时，选择路径二； 当２，５ｋ＜ｍａ时，选择路径一。 四、问题分析 （一）站点确定及最优路径选择 １、站点位置的确定 首先我们利用坐标拾取系统对这１２１名在校学生进行坐标 散点分析，排除了几个特殊点之后，将剩下的学生的家庭住址 进行三个区的分类。 ．由于学校并不提供运营成本，因此校车必须是盈利项目， 另外，鉴于我们是试运营，我们使用租车的模式，１辆校车ｌ 天租金为５００元。包括每日不可预支花销５０元，由此我们可以 计算出一天下来学校的盈利情况： ９６ａ．２—５００＊３—２０＊３＊２—６．５＊３＊２—５０＞０ 可得ａ＞８．９元 因此，学生的收费标准为：１Ｏ元／次，即６００元／月。学校 每月盈利为： （９６．ｉ０．２—５００＊３—２０＊３＊２—６．５＊３＊２—５０）＊３０＝６３３０元 然后，我们利用程序计算出距离每个区内到达各个学生距 离最近的站点坐标及位置，为了符合实际情况，我们将这些校 车站点选在距离理论坐标最近的公交汽车站点处： 区域 站点地址 站点坐标 根据数学建模结论及数据分析可得，我们通过坐标模型建 立和重心法提取出了三个最佳站点，并通过Ｐｒｉｍ算法确定出了 四种最优路径，在对最优路径的选择过程中，我们使用了成本 丰台区 海淀区 梅市口路东口 五～小学东门 １ １６．２７７０００，３９．８８４３００ ｌ １６．２７２０００，３９．９０９８００ 收益分析法，对由于堵车因素影响的学生乘车数量和由耗气量 影响的耗油成本进行了综合分析和计算，得出了四种路径的净 现值收益，并由此确定了最优路径的选择，同时，我们依据以 上分析和计算，确定出了每位学生一次乘车的费用和司机工资， 最终完成了对整个问题的分析研究，此外，我们还提出用天然 气代替汽油的想法并加以研究实践，为构建资源节约型、环境 友好型社会做出了自己的贡献，并为其他的相似问题的分析提 供了借鉴的经验和理论。 石景山区 焦家坟路口西 １１６．２３６０００，３９．９ｌ１５００ ２、最优路径选择 首先我们将路程的各种情况进行权重分配，其中：距离占 ６０％，拥堵情况占３０％，高速占１０％。得到每两点之间的权值之 后，利用Ｐｒｉｍ算法得到以下较优路径： Ｉ、太平路中学一３．１ｋｍ一梅市口路东口一３．５ｋｍ一五一小学 东门一３．２ｌ‘ＩＩ１一焦家坟路口西一３．２ｋｍ～五一小学东门一２．２ｋｍ 太平路中学 一２、太平路中学一３．１ｋｍ—梅市口路东口一３．５ｋｍ一五一小学 东门一４．６ｋｍ一焦家坟路口西一４．６ｋｍ～五一小学东门一１．７ｋｍ 参考文献： 【１］王海英黄强等．图论算法及其ｍａｔ ｌａｂ实现．北京航空 航天大学出版社．２Ｏｌ０年２月． 【２］龚劬．图论与网络最优化算法．重庆大学出版社．２００９ 年１ ０月． 太平路中学 ３、太平路中学一３．１ｋＴｒｒ～梅市口路东口一６．５ｋＩｒｒ一焦家坟路 【３］李得宜李明．数学建模．科学出版社。２００９年５月。 口西一４．６ｋＩｒｒ＿＿五～小学东门一１．７ｋＩＩｒ一太平路中学 ’ ４、太平路中学一３．１ｋＩｒｒ一梅市口路东口一６．５ｋＩｒｒ焦家坟路 口西一３．２ｋＩｒｒ五～小学东门一２．２ｋＩＩｒ。太平路中学 （二）校车数量及时间安排 根据上述４种路径可以粗略算出一辆校车的运行时间为： ｔ＝１５／（６０＊０．８）＝０．３１３ｈ＝２Ｏｍｉｎ 作者简介： 与社会科学学院经济系学生。 ． 吕腾捷 （１９９３一），女，河南上蔡人，北京理工大学人文 （作者单位’北京理工大学北京市１０００８１） 其中：１５ｋｍ为４种方案平均总路程，６０ｋｍ／ｈ为校车平均速 １６． ．
