数学建模---车辆调度问题论文

2012年西南财经大学数学建模竞赛论文题目车辆调度问题姓名学号专业联系方式任磊4100423310级金融学13550114147张耀城4092504110级金融服务与管理实验班15881002071张英博4102107510级金融工程130328166091车辆调度问题【摘要】面临日益拥堵的交通现状，如何更合理的安排校车的调度，对于方便广大师生的学习和生活、保证教学活动的顺利进行具有重要意义。本文通过收集相关资料，处理题中所给数据，并建立相关数学规划模型解决题中所给的六个问题。首先，对于如何合理安排多车型的车辆调度问题使得联合运输的费用最小的问题,我们通过建立整数规划模型，利用lingo软件求解出最省的租车费用为13000元。然后根据题目条件，在既定最低租车费用为13000元的情况下，利用C++程序定步长全局模拟出所有的可行解，得到112种租车方案。其次，我们将最佳行驶路线定义为车辆运行时间最短的路线，将图论中经典的Dijstra算法进行改进，以结点之间的时间作为权数，得到最佳路径。利用matlab编程求解得到最短运行时间为35分钟，路程总长为36.2km。然后，我们依据附录3对A、B校区师生乘车需求人数进行了描述性统计，从乘车人数的均值、方差、峰度以及正态性四个角度对样本进行检测，特别发现教师乘车需求在某些时段较为集中，从而利用SPSS软件对数据进行聚类分析，找到相关的分布规律与结论，即教师每日在各时段中的乘车人数分布相似。随后，我们以anova方差检验、组内与组间均值比较以及标准误差分析为手段，进一步验证了所得结论的准确性，使之能够可靠的用来推测未来每天乘车的教师人数的依据，为以后的分析和建模做好准备。再次，面对第四题中不考虑运营成本的较为理想化的整数规划模型，我们采用类似贪婪算法，将全局约束以发车时间划分为几个高峰时段，用lingo软件在各高峰时段约束中寻找局部最优，并将各个局部最优解对比淘汰，得到全局最优解。即满足所有约束的最小购车成本为257.2564万，具体购车方案为买2辆Ⅰ车、4辆Ⅱ车、1辆Ⅲ车和1辆Ⅵ车。随后，根据附录4与第二问所求得的最短运行时间，我们仍然建立较为复杂的数学规划模型，在定步长搜索与深度优先算法的基础上，利用matlab与C++编程，最终求解出满足教师乘车需求条件下的最优调度方案，并达到每天的最小运营成本1659.96元最后，我们根据以上求解的答案与题目提供的材料，对学校是否应该组建校车队进行实际讨论，我们从经济成本、时间成本、能否满足正常教学活动及教师舒适度等角度考虑，利用层次分析法，在多种可选方案中得出决策：学校应该组建校车队，以满足教师和同学们的乘车需求。紧接着，我们利用第三问所得数据规律来确定各发车时刻点的需求人数，建立较为复杂的规划模型，利用matlab与C++软件，采用定步长搜索，找出组建校车队的各种可行解及其最低成本，最后在所有最低成本中选取全局最优解，得出最佳的购车方案与调车安排，并最终预测出组建校车队平均每天所需的成本2787元，预估平均每天获利1460元。此外，在分析了上面所建立模型的优缺点后，我们认为该模型设计较为理想，但也忽略了一些现实因素。因此在此基础上我们进一步收集关于学生乘车需求的信息并提出模型的修正方向。【关键词】数学规划汽车调配Dijstra算法深度优先算法定步长搜索层次分析法2一、问题重述1.1问题背景随着我国政府对教育的大力推广，校车运输在交通运输行业里开始扮演越来越重要的角色。校园间交通日益成为城市交通的重要组成部分。面对各个校区之间师生的乘车需求，以及日益严重的交通道路拥堵现状，设计合理的校车交通运行机制对于方便师生、节约广大师生时间，保证教师正常的教学工作与学生的生活学习具有重要作用。同时也可以使运输公司提供更好的交通服务，提高运输公司的经济和社会效益。1.2问题提出某校有A、B两个校区，因为工作、学习、生活的需要，师生在两校区之间有乘车需求。在某次会议上，学校租车往返接送参会人员从A校区到B校区。已知参会人员数量、车辆类型及费用等，要求建立数学模型，求出最省的租车费用，并写出在最省费用下有多少中乘车方式。根据已有的两校区交通网络图及车辆运行速度，确定两校区车辆的最佳行驶路线（用时最短的路线）和平均行驶时间。根据已有的交通车队的运行数据，通过分析运行数据之间的存在的规律，为运输公司确定教师在工作日每个班次的乘车人数，以供运输公司在制定以后数月调度方案时使用。学校面对教师和学生的乘车需求，决定根据已有的数据组织交通车队，试求如何使总购价成本最低。并确定最佳的调度方案，在求在满足教师乘车需求的基础上使得车队运营成本最低。最后，在更为一般化的条件下，讨论建立交通车队以满足教师两校区间的交通需求的实际要素，收集数据，建立合理决策模型，估算合理的解决方案。二、问题分析车辆调度问题是一个数学规划问题,即在满足调度限制的解空间内,寻找使调度选择中提出的目标函数都满意的优化解。校车优化调度是在掌握了大量学生和教师乘车需求数据并总结出规律之后,通过把多种不同型号的车辆组织在规定的最优线路上,按照客流的数量、方向、时间等因素，从而制定有序的、周而复始的行车计划。同时，由于运输公司存在可持续运营的问题，需要考虑一定的成本与收益的关系，要综合考虑教师学生的乘车需求和运输公司的盈利情况。首先通过建立简单的整数规划模型，通过lingo求解出最低成本下的租车方案；进而通过图论中经典的关于最短路的Dijstra算法求出最优路线与最短时间。我们通过一些合理的假设以及对附录数据的分析和处理,针对车辆调度问题建立了一般的规划模型，从而求解出最优构成方案和最佳调度方案。基于前面做的努力，我们可以得出在更为一般的条件下，学校最佳的组建方案中组建校车队所耗用的成本与获得的利润。可以对上述问题作以下描述:有A、B两个校区，从第i个校区的教师乘车需求量为iG(i=1,2),需将所有教师运往另一个校区,由运输公司派出车型3为r(r=1,2…n)、载重量为nG(r=1,2,,n,且假设q1q2……qn)的客车来承运,已知iGnG(非满载),求满足乘车需求的最短行车线路，与最佳车辆配置。三、问题假设1、假定路线不存在堵塞现象，不考虑路段拥挤、堵塞或车辆本身故障情况；2、假定车辆在公路上行驶速度处处相等，车辆之间依次行进,不存在超车现象，都等于题目中给出的平均速度；3、假定汽车租赁期间只考虑租赁费用，且汽车可以随意调用，不计成本；4、假定从A校区到B校区单程只需要35分钟，不考虑教师和学生上下车的时间；5、假定耗油量为每百公里的耗油量；6、校车所用汽油为93#汽油，油价采用去年平均价格7.23元/升；7、假定一年有365天；8、假定车辆购置税为10%9、假定校车都是准点发车，不存在延误现象；10、假定校车的使用年限为10年；11、题目中所给数据真实可靠；四、符号表示1、,ijX：表示第j类型车在第i个半天的需求量（i=1,2;j=1、2、3、4）；2、,ijC：表示第j类型车在第i个半天的成本（i=1,2;j=1、2、3、4）；3、(,)wij：表示在最短时间下从道路点i到道路点j之间的距离；4、lv()：表示从顶点0u到v的经过一条路所用时间的权；5、zv()：表示最佳的路线，v的父亲点；6、iX：表示第i辆车的购置数量；7、iC：表示第i辆车的成本；8、i：表示第i辆车可以乘坐的人数；9、:id表示第i时间点需要乘车的人数（i=1,2...k）；410、1iP：表示第i车的油耗花费，可以刻画为10/100iiPSlP（），其中油价为0P，il耗油量为每百公里的耗油量；11、2:iP表示第i车驾驶员费用；12、,CiP：表示每天车费实际的分摊成本；13、,DiP：表示第i车校车的折旧费用；14、:iP：表示i车每运行一次的花费；15、P：表示车辆运行的所有的费用；16、,ijN：表示第j个发车时点的调运i辆车；17、,:ijn表示第i类车购买j辆（i=1,2，3;j=1..8）；五、模型建立与求解问题一：5.1.1问题分析根据题意，我们可知每种可以租用上半天和租用下半天，而且两辆车分别租用上半天和下半天其成本和效用同租一整天同类车是相同的。此外，我们还可知租车的成本只考虑租赁费用，同时在租用期间，汽车可以随意调用，且不计成本。主席团人员可以与其他人员共同乘坐一辆车（Ⅰ、Ⅱ类型车）。5.1.2规划模型的建立首先，由于租用半天的费用正好是租用一整天费用的一半，所以，从成本最小的角度出发，我们暂不考虑租用全天汽车的情况，即将全天利用两个半天代替。建立如下模型：决策变量：设,ijX表示第i类型车在第j个半天的需求量（i=1,2;j=1、2、3、4）。引入“0—1”变量12yy与，分别为当Ⅰ、Ⅱ类型车大于等于3辆时取值为1；当Ⅰ、Ⅱ类型车小于3辆时取值为0。即：11,30,y当Ⅰ型车辆时其他，21,30,y当Ⅱ型车辆时其他目标函数：5设租车的总的成本为Z,租车的成本为,ijC，顾4,,11,2ijijijZCX约束条件：1、保证主席团人员上午乘坐Ⅰ、Ⅱ类型车，即11213627XX2、保证所有人员在上午的乘车要求，即11213141363346222XXXX3、保证下午参加会议的主席团人员的车位，即1222367XX4、保证下午参加会议的人员（包括主席团人员）的乘车情况，即12223242363346180XXXX5、考虑Ⅰ、Ⅱ类型车大于等于3辆时打折情况，即1112121222(0.5()3)0(0.5()3)0XXyXXy非负约束：,0ijX综上可得：4,,11,21121112131411222122232421112121222,max3627363346222367..363346180(0.5()3)0(0.5()3)00ijijijijZCXXXXXXXXXstXXXXXXyXXyX5.1.3模型求解根据lingo软件，可编制程序求解，见附件9.2.1，得出最省的租车费用为13000元5.1.4模型进一步讨论通过第一个程序，可以求得全局最优解，又由于租用半天的费用正好是租用一整天费用的一半，所以对于其他的最优解，只可以通过替换同等价位的车型，进而改变车型配置以使解不同。（之所以是等价位车型间的替换，因为若高价替换，且满足约束条件，则目标函数会变大，目标函数不再是最优；若是用低价替换，又满足约束条件，则目标函数会变小，于是与原目标函数是最优矛盾。因此只能是等价位不同车型替换。）而在所有车型中，等价位车型，只有打折后的二类车和未打折的一类车价6格是一样的，因此只能是这两种车型的替换。这种结果可以根据具体数据分析：在第一个最优解中，共租用5辆上午的二类车型，共可载30名主席团成员，而实际主席团成员只有27人，因此有3个空座。因为一辆二类车型和一辆以类车型的座位差为3个（6-3=3），恰好等于3个空座。而且在第二个解中，二类车也已满足打折的条件，而一类车没有打折，以一类车和二类车价格是一样的，因此满足替换条件，进而通过替换求出其他最优解。以上解都是不考虑全天租车问题的，即完全用上半天和下半天的租车方式代替全天的租车方式（因为假设5，俩类可以替代）当考虑全天时候，我们可以通过，以一个上半天和一个下半天的同一类车来更换为一个全天的同类车，以求得其他最优解。基于以上几种替换原理，我们利用C++程序全真模拟出共112种最优解。由于表格内容繁杂，因此租车方案见附录9.2.2；程序见9.2.3问题二：5.2.1最佳行驶路线模型的建立两点间的最佳路径可能需要考虑的并非仅仅是空间距离的最短,有时候人们往往会考虑到通行时间的问题。本文就此问题,对最短时间路径做了讨论，因此我们将两个校区车辆最佳行驶路线定义为：在所用时间最短的前提下，所经过的道路点。为了求出最短时间下各个点的之间的距离，我们使用了路径问题中Dijstra算法求解。根据所