数学建模2019-B题河北工程大学新校区公交线路规划与站点设置

B题公交车调度
公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。

下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。

该条公交线路上行方向共14站，下行方向共13站，第3-4页给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。

公交公司配给该线路同一型号的大客车，每辆标准载客100 人，据统计客车在该线路上运行的平均速度为20公里/小时。

运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过120%，一般也不要低于50%。

试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。

如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法；根据实际问题的要求，如果要设计更好的调度方案，应如何采集运营数据。

公交线路中寻求最优路线的模型与算法摘要本文对公交线路查询问题进行了研究。

根据查询者的各种不同需求，以换乘车次最少为约束条件，分别以出行耗时和出行费用为目标函数，建立多目标规划模型，运用公交换乘搜索算法可得到合理的出行路线。

针对问题一，在仅考虑公汽线路时，用520条公汽线路构建公共交通矩阵。

以此矩阵作为搜索对象，运用基于广度优先的公交换乘搜索算法，找出符合“换乘次数最少”的可行解。

分别以出行耗时和出行费用为目标建立规划模型。

然后，对有限个可行解采用枚举法，将其出行耗时和出行费用一一求出，通过比较得到规划模型的最优解，结果见正文第6页表3。

同时，在换乘次数和是否穿过地铁站等方面对结果作了清晰评价。

公汽线路。

重新构建共公交通矩阵。

在考虑地铁站与公汽站点相互连通的情况下，运用问题一的解法求得规划模型的最优解，结果见正文第7页表4。

针对问题三，当已知所有站点之间的步行时间时，在模型二的基础上对公交换乘搜索算法改进，相邻近的两站点间乘客可以通过步行到达，并对整个乘车过程中步行次数和步行时间进行约束得出了问题三的模型。

关键词：公共交通矩阵公交换乘搜索算法目标规划相邻站点第29届奥林匹克运动会将于2008年8月在首都北京举行，这是我国第一次成功的申办奥运会，极大的鼓舞了全国人民。

经过近六年筹备，各大奥运会场馆相继竣工。

作为奥运会的重要交通工具，举办城市的公共交通系统也有了很大发展。

现在北京市的公汽线路已达800以上，较好的满足了到现场观看奥运比赛的国内外观众的交通需求，使公众的出行更加通畅、便利，与此同时人们也面临着多条线路的选择问题。

因此，根据市场需求，某公司准备研制开发一个解决公汽线路选择问题的自主查询计算机系统，系统核心是线路选择的模型与算法。

设计该系统要从实际情况出发考虑，满足查询者的各种不同需求，现有三个问题需要解决：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型和算法。

利用此模型与算法，求出以下6对起始站到终到站之间的最佳路线，并给出清晰的评价说明。

2023年全国大学生数学建模竞赛题目B：题目背景在综合交通运输系统中，公共交通是一个重要的组成部分。

为了提高城市的交通效率和减少交通拥堵，许多城市采用了公共交通优先的策略。

在线调度算法是实现公共交通优先的一种重要方法。

题目描述某城市的公共交通系统包含多条公交线路和多个公交车站。

现在，你被要求设计一个在线调度算法来优化城市的公共交通系统并减少等待时间。

具体来说，给定每一条公交线路的发车时间间隔和通过每个车站所需的时间，你需要设计一个算法，使得乘坐公交车的乘客的等待时间最小。

你需要完成以下任务：1.根据给定的公交线路信息，计算每个车站的累计等待时间，即从第一趟公交车到达该车站到当前时间的总等待时间。

2.根据计算得到的累计等待时间，为每个车站分配一个优先级，并找到最高优先级的车站。

3.制定一个在线调度算法，在最高优先级车站的公交车上按照车站的优先级顺序依次上下乘客。

4.分析并讨论你设计的在线调度算法的优点和缺点，并提出改进的意见。

请使用Markdown文本描述你的算法设计，包括算法的步骤、算法的时间复杂度和空间复杂度，并给出算法的改进方向。

算法设计步骤一：计算累计等待时间1.初始化各个车站的累计等待时间为02.对每一趟公交车，从第一个车站开始，计算当前车站的累计等待时间，累计等待时间等于前一个车站的累计等待时间加上通过当前车站所需的时间。

步骤二：分配优先级1.根据计算得到的累计等待时间，为每个车站计算优先级，优先级等于累计等待时间的倒数。

步骤三：找到最高优先级车站1.遍历所有车站，找到优先级最高的车站。

步骤四：在线调度算法1.根据最高优先级车站的优先级顺序，依次上下乘客。

时间复杂度和空间复杂度•步骤一的时间复杂度为O(n)，其中n为车站的数量。

•步骤二的时间复杂度为O(n)，其中n为车站的数量。

•步骤三的时间复杂度为O(n)，其中n为车站的数量。

•步骤四的时间复杂度为O(n)，其中n为车站的数量。

•算法的空间复杂度为O(n)，其中n为车站的数量。

2007B题：乘公交，看奥运（数据有变化）我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。

这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。

针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。

为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。

请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。

并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。

(1)、S3769→S2857 (2)、S1557→S0481 (3)、S1879→S2322(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。

3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。

【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：6分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：5分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：8分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。

【附录2】公交线路及相关信息（见公汽线路信息，对原数据文件B2007data.rar 有少量更改）城市公交线路选择优化模型摘要本文针对城市公交线路选择问题建立了两个模型，一个是基于集合寻线算法模型，另一个是图论模型。

新校区班车线路（2013年8月版）一号线：7:10狮子林桥（狮子林大街与金纬路交口金纬桥下）——7:13工人医院——7:15沃尔玛（新开路李公楼公交站茶城对面）——7:25十四经路——7:35大桥道（财富豪为大酒店对面大桥道边公交站）——7:39津塘路广宁路新村大楼公交站二号线：7:05中北镇(中北大道物美对过水语花城公交站)——7:15华城宾馆(家易网吧对过王顶堤立交桥公交站)——7:20阳光100(阳光100小区左侧公交站)三号线：7：00佳园里(辰昌路634路公交车总站对面)——7:10洪湖里(纪念馆路洪湖里公交车站)——7:15水木天城(原站点对面628公交车站)——7:25杨庄子(西青道中学对面)四号线：7:00勤俭道(中环线勤俭道公交站)——早7:05白庙(中环线白庙公交站)——7:08仓联庄（中环线仓联庄公交站）——7:18建昌道（中环线建昌道公交站）——7:20增产道（中环线增产道公交站）五号线： 7:10万权道（兰州道垃圾站对面）——7:15复康路萨市道交口华润公交站——7:25利民道与围堤道交口——7:35南楼（大沽南路天津日报公交站）——7:45复兴门（复兴门地铁站旁公交站）六号线：7：00莱茵小镇——7:02钢珠厂——7:04世纪新苑——7:06西青分局——7:08杨柳青四中——7:10国家电网七号线：7:15西北角（大丰路先春园公交站）——7:20麦德龙（中环线邵公庄小学门前）——7:40快速路黑牛城道口公交站——7:50快速路曙光里八号线：7:00中环线洪湖里公交站——7:05中环线西青道麦德龙对过西青道公交站——7:10中环线小西关公交站——7:15中环线长虹公园公交站——7:25中环线天拖大楼公交站——8:00复兴门地铁站旁公交站九号线：7:23中环线卫国道公交站——7:28东风立交桥下公交站。

交巡警服务平台的设置与调度优化分析摘要本文以实现警察的刑事执法、治安管理、交通管理、服务群众四大职能为宗旨，利用有限的警务资源，根据城市的实际情况与需求合理地设置了交巡警服务平台、分配各平台的管辖范围及调度警务资源。

并分别对题目的各问，作了合理的解答。

问题一：（1）、根据题目所给数据，确定各节点之间的相邻关系和距离，利用Floyd 算法及 matlab 编程求出两点之间的最短距离，使其尽量满足能在 3 分钟内有交巡警平台警力到达案发结点的原则，节点去选择平台，把节点分配给离节点距离最近的平台管辖，据此，我们得到了平台的管辖区域划分。

（2）、我们对进出该区的 13 条交通要道实现快速全封锁的问题，我们认定在所有调度方案中，某种方案中耗时最长的的围堵时间最短即最佳方案，利用 0-1 变量确定平台的去向，并利用线性规划知识来求解指派问题，求得了最优的调度方案。

（3）、在确定增添平台的个数和具体位置的问题中，我们将尽量保证每个节点都有一个平台可以在三分钟内到达作为主要原则来求解。

我们先找出到达每个平台的时间都超过三分钟的节点，并尝试在这些节点中选取若干个作为新的平台，求出合理的添加方案。

问题二：（1）、按照设置交巡警服务平台的原则和任务，分析现有的服务平台的设置是否合理，我们以各区覆盖率作为服务平台分布合不合理的评价标准，得到C、 D、 E、F区域平台设置不合理。

并尝试一些新的设置方案使得设置更为合理，最后以覆盖率最低的E 区为例，使用一种修改方案得到一个比原方案更合理的交巡警服务平台的设置方案。

（2）、追捕问题要求在最快的时间内抓到围堵罪犯，在罪犯和警察的行动速度一致的前提假设下，我们先设定一个具体较小的时间，编写程序检验在这个时间内是否可以成功抓捕罪犯，不行则以微小时间间隔增加时间，当第一次成功围堵时，这个时间即为最佳围堵方案。

关健字： MATLAB软件， 0-1 规划，最短路， Floyd 算法，指派问题一、问题重述“有困难找警察” ，是家喻户晓的一句流行语。

装订线摘要研究在老校区设置校车停靠点的问题。

由于教职员工分布在许多不同的生活区域中，为了使其能够方便的乘坐校车，须要根据教职员工的分布设立多个校车停靠点。

现根据已有生活区域的分布，在使教职员工到校车停靠点的距离最小的前提下，尽可能安排最少的校车数量。

运用了Floyd算法、0-1整形规划、增加人数权重距离、概率分布与统计、状态转移图，对不同方案进行满意度比较，建立数学规划模型，得出优化方案，进行方案检验。

对于校车停靠点的设立，以题目给出的相关数据，假设没有给出数据的区域间没有直达路径，必须通过其余区域转达。

通过Floyd算法得到任意两区域之间的最短距离。

之后引入0-1状态变量，设定若某区域被选为校车停靠点则状态值为1，否则状态值为C n种方案，在确定校车停靠点的基0。

利用穷举法得到n个校车停靠点的设置分布的50础上，编程求出各个区域到离自己最近校车停靠点的距离之和。

根据题目要求，距离之最短的停靠点设置方案即为最优方案，此时得到2个停车点时设在区域18和区域31，3个停车点时设在区域15，区域21和区域31。

再考虑人数的时候，我们在第一问的基础上，对每个区域间的距离改为人数权值距离。

此时转化成与第一问相同的算法。

得到2个停车点时设在区域19和区域32，3个停车点时设在区域15，区域21和区域32。

研究校车数量的过程中，在增添校车和人员转移的取舍中，我们设定了增添校车的条件标准，从而计算出由人员转移距离和校车数量决定的满意度。

在此基础上，我们结合实际，分时段、分工种进行动态状态分析，不同工种的考虑增加了运送批数，缓解乘车高峰压力。

考虑课时的情况，则部分校车可以在时间允许范围内空车返回老校区接送下一批员工，此举增加了校车的流动性，从而减少了所需的校车数，在此考虑下，车辆数由最大需要量的54辆骤减到现如今27辆。

关键字：Floyd算法、0-1整形规划、人数权重距离、概率统计、状态转移图1.问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。

2019年河北工程大学数学建模竞赛题目（请先阅读“河北工程大学数学建模竞赛论文格式规范”）A题河北工程大学新校区通勤班车调度问题河北工程大学新校区一期建设即将完工，学校的整体搬迁工作已提上日程.在新校区职工家属区未能使用之前，妥善解决教职工上下班问题是学校需要考虑的问题之一.有人建议学校安排通勤班车方便教职工上下班较为妥当.考虑到学校相当一部分教职工不在学校家属院居住、通勤班车工作时间处在上下班的高峰期等方面的情况，如何设置通勤班车的站点及规划行车路线，尽量降低教职工换乘资金成本和等车、步行的时间成本，同时兼顾班车的服务成本，更有效地提高班车的运营效率与服务质量是学校安排通勤班车时亟待解决的问题.如果学校在新校区与老校区（主校区、中华南校区、丛台校区）之间安排通勤班车，需要解决租赁的车辆数目、通勤站点的位置以及班车的行车路线规划等问题.请根据上述资料和要求，试讨论下列问题：（1）考虑到学校相当一部分教职工没能在学校家属院居住，要根据教职工的居住位置设置相应的通勤站点.为方便更多的教职工上下班乘坐，在综合考虑班车的服务质量（主要是指满足尽可能多的教职工方便快捷地乘车上下班）和服务成本的前提下，给出通勤站点位置并规划班车的行车路线；（2）假设我校租赁的是标准载客量为60人的大客车，根据我校的作息时间表，在满足需求且考虑运行成本的前提下，设计全天的班车调度方案，包括发车时刻表和需要的车辆数目（温馨提示：班车不能超员）；（3）为提高通勤班车的载客率，进一步降低通勤班车的运行成本，学校拟租赁若干种不同型号的客车（仅标准载客量不同）.考虑不同发车时间应选用何种型号的客车及被选客车的数量，在满足教职工出行要求的情况下，给出新的班车调度方案；（4）考虑到新校区与老校区距离较远，如何改进河北工程大学的作息时间表，以有效降低广大教职工的路途成本，请给出您的改进方案；（5）根据实际问题的需要，如果要优化通勤站点、班车运行路线及班车调度方案，还应采集哪些数据，采集的这些数据在改进模型时将发挥怎样的作用.附件1河北工程大学职工居住情况统计表；附件2邯郸市现有公交线路运行图；附件3河北工程大学作息时间表；附件4河北工程大学新校区效果图.。