校车安排问题(论文).pdf
- 文档编号:14648832
- 上传时间:2023-06-25
- 格式:PDF
- 页数:25
- 大小:272.39KB
校车安排问题(论文).pdf
《校车安排问题(论文).pdf》由会员分享,可在线阅读,更多相关《校车安排问题(论文).pdf(25页珍藏版)》请在冰点文库上搜索。
1校车安排问题校车安排问题摘要摘要我们对老校区乘车点选址问题进行研究,根据校区内教师与员工的分布,提出了最佳乘车点的选取办法,建立了满意度与区域到乘车点距离的函数关系,并根据获得数据模拟了乘车点选址的最优化的模型,得到如下结果:
问题1:
根据77组给定数据,首先建立了动态规划模型,用Dijkstra算法(Matlab软件实现)求解任意两个区域之间最小路程并检验,得到了任意两点间的最短距离矩阵。
再建立选址规划模型,求解使各区域人员到最近乘车点5050D距离最小得个乘车点的位置。
最后求得当=2时,选取18和31点最佳,总最nn短距离为24492m;当=3时,选取15、21和31点最佳,总距离为19660m。
n问题2:
我们用归一法定义满意度与距离的函数关系,根据问题1中的任意两点间的最短距离矩阵,得到满意度矩阵。
根据每个区域的人数,5050D5050M得出考虑人数的满意度矩阵。
再建立选址规划模型,求解使教师和工作5050RM人员满意度最大的个乘车点的位置。
结果:
当=2时,选取19和32点为乘车nn点最佳,总最大满意度为1945.877;当=3时,选取15、21和32点最佳,总最n大满意度为2066.743。
问题3:
这是一个双目标规划问题,考虑运行成本和满意度两个目标函数,建立双目标非线性规划模型。
当各乘车点人数平均分配的时候,运行成本最低,定义为三个乘车点人数的方差,为总满意度,因此要尽量使最小,1k2k1k2k最大。
由此可利用的最大值求得使教师和工作人员尽量满意并降低运行成2121kk本的3个乘车点位置,其中,、为运行成本和满意度的权重。
最后求得设12立3个乘车点时,分别为15、21和32点,需要校车55辆;的最大值为12.962,2121kk其中方差=2378.7,满意度=2276.025。
121,2,33=1k2k问题4:
对解决问题四采取的方法是把问题三推广到n个乘车点的情况。
根据前3问的方法求出更多的数据进行对比分析。
考虑满意度,运行成本,乘车点数目三个目标函数,建立多目标规划模型。
分析出最佳乘车点数目,进而根据第3问的模型给出最大满意度和需要车辆数,给出的合理建议。
关键字关键字:
最小距离归一法0-1规划法多目标非线性规划Dijkstra算法满意度矩阵方差权重量纲分析法2一、问题的重述一、问题的重述许多学校都建有新校区,常需要将老校区的教师和工作人员用校车送到新校区。
由于每天到新校区的教师和工作人员很多,往往需要安排许多车辆。
必须让教师和工作人员尽量满意,并有效的安排车辆,节省运行费用。
因此对乘车点的设立、教师和工作人员满意度问题的研究十分重要。
我们需要解决的问题:
假设老校区的教师和工作人员分布在50个区,各区的距离见表1。
各区人员分布见表2。
1、我们需要研究一个较为简单的乘车点建立问题,根据表中的数据,建立乘车点为时的一般模型,并给出=2,3时解。
需注意的问题是老校区分为50个nn区域,每个区域人数不同,表1和表2中的数据给出了77条路线的距离和每个区域的人数,而任意两个区域间可行路径不唯一,方向不定,需要用这些数据确定任意两个区域间的最短距离。
保证数据的准确性。
然后找出合理的计算方法计算出所有区域到所选乘车点的最小距离之和,判断出最佳的乘车点设置位置。
2、我们需要在问题1的基础上,进一步考虑影响满意度的因素,使教师及工作人员满意度最大化,建立乘车点为时的一般模型,并给出=2,3时的解,nn需注意的问题是,找出与满意度相关的变量,建立合理的函数关系。
3、我们被要求在已知乘车点数量下,确立乘车点具体位置,确定各乘车点人数建立=3情况下的模型,需要考虑的约束是,教师和工作人员的满意度,安排n的车辆数。
4、我们需要在1、2、3问所得数据的基础上,综合分析,总结归纳,结合实际给出合理的建议和考虑,使教师及工作人员满意度高,运行成本降低。
二、模型的假设二、模型的假设1.题中所提供各项数据均真实合理。
2.表一提供的数据表示各个区域之间的所有相通路线。
3.把每个区域都视为一个点,乘车点建在各区域内。
4.不考虑乘车拥挤情况,满意度只与区域到乘车点距离有关。
5.每个人的满意度权重相同。
6.所有区域的老师及工作人员都会乘车。
7.同一区域内的所有老师和工作人员选择的路线相同,且为该区域到最近乘车点的最短路径3三、符号说明四、模型的建立和求解三、符号说明四、模型的建立和求解问题的分析:
问题的分析:
用校车将分布在老校区50个区的教师和工作人员送到新校区,合理地安排车辆和设置乘车点使得教师和工作人员的满意度最大。
老师的满意度与到乘车点的距离负相关。
考虑站点个数约束和校车成本,我们研究制定既使教师和工作人员满意度最大,又使校车成本最低的乘车点设置方案。
针对问题1,首先建立动态规划模型,用Dijkstra算法(Matlab软件实现)和LINGO软件分别求解任意两个区域之间最小路程并检验,得到任意两点间的最短距离矩阵。
再建立选址规划模型,求解各点到个乘车点总距离的最小值,ijdn进而求出个乘车点的设立位置,再分别求出设置2个和3个乘车点时的结果。
n针对问题问题2:
用归一法定义满意度与距离的函数关系,根据问题1中的任意两点间的最短距离矩阵,得到满意度矩阵。
根据每个区域的人数,5050D5050M得出考虑人数的满意度矩阵。
再建立选址规划模型,求解各区域到个5050RMn乘车点的总满意度的最大值,再分别求出设置2个和3个乘车点时的结果。
针对问题3,考虑运行成本和满意度两个目标函数,建立双目标非线性规划模型。
当各乘车点人数平均分配的时候,运行成本最低,定义为三个乘车点人数的方1k符号含义5050D任意两点之间的最小距离矩阵5050W表示弧的长度矩阵ij(,)5050M满意度矩阵5050RM考虑人数的满意度矩阵501R每个区的人员数矩阵n设立乘车点的个数irj表示第个乘车点的乘客总数iRJ三个乘车点的平均乘客数、1k2k分别为三个乘车点人数的方差和总体满意度、12分别为运行成本和满意度的权重4差,为总满意度,因此要尽量使最小,最大。
由此可用的最大值2k1k2k2121kk求最优解,其中,、为运行成本和满意度的权重。
最后求出最优解。
针对问12题4:
对解决问题四采取的方法是把问题三推广到n个乘车点的情况。
根据前3问的方法求出更多的数据进行对比分析。
考虑满意度,运行成本,乘车点数目三个目标函数,建立多目标规划模型。
分析出最佳乘车点数目,进而根据第3问的模型给出最大满意度和需要车辆数。
给出合理建议。
分析确立动态规划模型画出50个区域分布路线得到各点最小距离矩阵确定满意度函数求的各点最小距离Matlab实现验证考虑满意度影响因素建立选址规划模型求得乘车点位置考虑多个目标函数选用Dijkstra算法分析所得数据提出建议LINGO实现优化模型模型建立:
问题1模型建立:
问题15这是一个图论模型中的最短路问题。
我们通过数据整理分析,绘出了各区域分布位置简图,如下:
图1:
老校区区域及各区域间路线分布图根据题目所给的各区的距离,我们采用0-1规划法求解50个区任意两点间的最小路径。
故设0-1决策变量,其意义为:
ijx01ijijxij=弧(,)不在最短路上弧(,)在最短路上表示弧的长度(路程),若和没有弧连通,对于除了起ijwij(,)ij.ijw=+点和终点以外的任意一个顶点,如果,说明从出发的所有弧中必然i11nijjx=i有一条弧在最短路上,也就是说最短路经过该顶点,此时所有从其他顶点到达该顶点的弧中必然也有一条弧在最短路上,因而必有如果说明11;njijx=10,nijjx=最短路不经过顶点,故必有且最短路径只有一条,两种情况可以合并i10.njijx=写成111,1,2,.,50.nnijjijjxxi=6对于起点1,则必然满足对于终点则必有111,njjx=n11.njnjx=对于已走出起点的路径不得再返回起点,则110.njjx=对于已达终点的不再往回走,则10.nnjjx=目标函数是最短路上的各条弧的长度之和(总路程)最小,于是最短路问题可以用如下0-1规划来描述:
5050115050505011115050150115015011min,1,1,.0,0,01,ijijijijjiijijjijinjjjjijzwxxxxxstxxx=或我们通过LINGO8.0求解得到50个区任意两点距离的5050的矩阵(部分5050D见表2)和最短路径(部分见附录一表1)。
表2:
部分任意两点最短距离矩阵(前1010)123456789101040045070091011401110128014801614240008503005107407108801080121434508500600810104010101180138015604700300600021044041058078096059105108102100230200370570750611407401040440230032034054072071110710101041020032001703705508128088011805803703401700200380914801080138078057054037020001801016141214156096075072055038018007之后我们用0-1规划法求解使各区人员到最近乘车点的距离最小时个乘车n点的位置。
故设0-1决策变量和,其意义为:
ijyjp1,0,ijijyij=区的人选择去区乘车,区的人不选择去区坐车,1,0,jjpj=区设立乘车点,不设立乘车点,表示区到区的最小距离。
对于区的人员,50个区中他们至少且至多ijdiji只能去其中一个区乘车,因而有且区是否设立乘车点跟是否有人前去5011,ijjy=乘车有关,即如果没有人前往乘车点,则表示点不设乘车点,因为如果有乘车j点,至少自己区的人会在本区乘车;同样,如果有人前往点乘车,则点必定jj设立了乘车点,因此有要求设立站点的总人数为,max,1,2,50,jijpyi=n故有,目标函数是50个区的人员到个乘车点的总距离最小,于是选501jjpn=n址0-1规划模型可以用如下0-1规划法描述:
505011501501minmax,1,2,50,.1,01,ijijijjijjjijjijzdypyipnstyy=或我们通过用Matlab求解得到=2和=3时乘车点最佳设立位置。
求解结果如表1、nn表2:
8表1:
设立两个乘车点时的乘车方案表表2:
设立三个乘车点时的乘车方案表各区域到所选乘车点(区域18)的距离各区域到所选乘车点(区域18)的距离区域12345678距离11547541114514360480160330区域910111213141516距离520460610750950490300130区域1718192021242526距离2700204344524350180650价格2747距离510874各区域到所选乘车点(区域31)的距离各区域到所选乘车点(区域31)的距离区域2223282930313233距离7104004501902400230420区域3435363738394041距离630370260530570440400540区域4243444546484950距离3704505506609008901090210总距离各区域到所选两乘车点(18、31)的总最短距离:
24492m各区域到所选乘车点(区域15)的距离各区域到所选乘车点(区域15)的距离区域56789101112距离655625455285340160310450区域1314151617182526距离6501900170250300480380区域27距离490各区域到所选乘车点(区域21)的距离各区域到所选乘车点(区域21)的距离区域123419202122距离63023010805303201800300区域23244445464748499问题二问题二我们对于问题二首先采取的办法是建立满意度和乘客到乘车点距离的函数关系式。
我们采用归一法定义的满意度矩阵:
5050M(max)/(maxmin),ijijijijijmdddd=考虑每个区的人数定义考虑人数的满意度,矩阵,具体求解方iRijijirmmr=法是将的每一行乘其行所对应的,我们用0-1规划法求解使各区人员到最5050Mir近乘车点的满意度最大时个乘车点的位置。
这同样是一个选址规划模型。
n故设0-1决策变量和,其意义为:
ijyjp1,0,ijijyij=区的人选择去区乘车,区的人不选择去区坐车,1,0,jjpj=区设立乘车点,不设立乘车点,表示区所有人员到区的乘车的满意度。
对于区的人员,50个区中他们ijrmiji至少且至多只能去其中一个区乘车,因而有且区是否设立乘车点跟5011,ijjy=j是否有人前去乘车有关,即如果没有人前往点乘车。
则表示点不设乘车点,jj因为如果有乘车点,至少自己区的人会在本区乘车;同样,如果有人前往点乘j距离270370420570760350480680各区域到所选乘车点(区域31)的距离各区域到所选乘车点(区域31)的距离区域2829303132333435距离4501902400230420630370区域3637383940414243距离260530570440400540370450区域50距离210总距离各区域到所选三个乘车点(15、21、31)的总最短距离:
19660m10车,则点必定设立了乘车点,因此有要求设立站点jmax,1,2,50,iijpyi=的总人数为n,故有,目标函数是50个区的人员到个乘车点的总距501,jjpn=n离最小,于是选址0-1规划模型可以用如下0-1规划法描述:
50501501501max,max,1,2,50,.1,01,01,ijijijiijjjijjijjrmypyipnstyyp=或或我们通过用Matlab求解得到=2和=3时乘车点最佳设立位置。
求解结果如表3、nn表4:
表3:
设立两个乘车点时的乘车方案表各区域到所选乘车点(区域19)的满意度各区域到所选乘车点(区域19)的满意度区域12345678满意度40157.527.032.433.122.815.955.4区域910111214151617满意度29.516.043.128.916.461.680.410.7区域1819202122232425满意度34.34853.546.69.949.545.371.6区域2627284446474849满意度13.083.117.257.09.554.051.544.2各区域到所选乘车点(区域32)的满意度各区域到所选乘车点(区域32)的满意度区域1329303132333435满意度47.226.567.19.78668.851.764.4区域3637383940414243满意度25.376.581.843.036.548.333.354.411表4:
设立三个乘车点时的乘车方案表问题三问题三第三问是一个双目标规划模型问题,需要考虑运行成本和满意度两个目标函数,我们建立双目标非线性规划模型。
当各乘车点人数平均的时候,运行成本最区域4550满意度13.156.3最大满意度2148.9各区域到所选乘车点(区域15)的满意度各区域到所选乘车点(区域15)的满意度区域56789101112满意度30.523.615.361.536.819.758.142.5区域1314151617182526满意度53.220.67083.811.633.567.714.9区域27满意度83.3各区域到所选乘车点(区域21)的满意度各区域到所选乘车点(区域21)的满意度区域123419202122满意度53.165.322.129.545.653.14911.5区域2324444546474849满意度52.143.061.317.013.364.064.159.9各区域到所选乘车点(区域32)的满意度各区域到所选乘车点(区域32)的满意度区域2829303132333435满意度15.926.56719.78668.851.764.4区域3637383940414243满意度25.376.581.843.036.548.333.362.3区域50满意度56.3最大满意度2276.012低,定义k1为三个乘车点人数的方差2221231231=()()()3,3nnnnnnkrjRJrjRJrjRJrjrjrjRJ+=其中表示第个乘车点的乘客总数。
为三个乘车点的平均乘客数。
irjiRJ为总体满意度。
且运行成本向最小取优,满意度向最大取优。
由于两个目标2k函数彼此矛盾,可对的最大值求最优解,即,其中,、2121kk212max1kk=12为运行成本和满意度的权重,由于与量纲不同,而的量纲为一,所以2k1k2121kk与的比值即为与量纲的比值,即,且由于211k2k1222121kk=可得与层次分析法的得到的结果基本吻合。
121+=121,2,33=设0-1决策变量和,其意义为:
ijyjp1,0,ijijyij=区的人选择去区乘车,区的人不选择去区坐车,1,0,jjpj=区设立乘车点,不设立乘车点,表示区所有人员到区的乘车的满意度。
对于区的人员,50个区中他ijrmiji们至少且至多只能去其中一个区乘车,因而有,且区是否设立乘车5011,ijjy=j点跟是否有人前去乘车有关,即如果没有人前往乘车点,则表示点不设乘车点,j因为如果有乘车点,至少自己区的人会在本区乘车;同样,如果有人前往点乘j车,则点必定设立了乘车点,因此有要求设立站点jmax,1,2,50,jijpyi=的总人数为n,故有,50个区的人员到个乘车点的总满意度5013jjp=n13,各乘车点的乘客数为5050112ijijijkrmy=501,jiijirjry=2505031112223123501501max()()()3max,1,2,50,3.1,0101ijijijrmynnnjijjjijjijjzrjRJrjRJrjRJpyipstyyp=+=或,或,我们通过Matlab求解得:
的最大值为12.962,其中方差2121kk121,2,33=2378.7,满意度=2276.025;,1k2k115n=221n=31n=;三乘车点的车的数量分别为17,18,20,共需55123790,810,902nnnrjrjrj=辆车。
如表5:
表5:
设立三个乘车点时选址方案及各乘车点车辆数问题四问题四我们对问题四采取的方法是把问题三推广到n个乘车点的情况。
由于运算量乘车点数满意度乘车点位置去往乘车点的总人数各站点需要的车辆数32276.02515790172181018329022014较大,在此我们给出n=1,2,3,4,5时的数据,如表6和图2所示:
表6:
乘车点数目不同情况下考虑满意度及车辆数部分数据统计表乘车点数满意度乘车点位置去往乘车点的总人数各站点需要的车辆数各站点需要的车辆总数12091.529192502545422148.9461915143355329882232276.0251579017552181018329022042325.966241795515800183268915445961352364.08423257551136481859213223889328331815图2:
最大满意度与乘车点数的关系由表中数据可以看出,仅当一点的时候运营费用最小,只需54辆校车。
而在建立三个乘车点的前提下,校车需要数量只有三种情况:
54辆,55辆,56量。
54辆无疑为最理想情况,但由于各地区人数复杂不易统计,2、3、4、5点均需要55辆校车,因此我们考虑取55辆校车为可接受数量。
此时考虑下一个目标,满意度的问题。
由图2可以看出,当乘车点数在1到5变化时,随着乘车点数目增加,满意度递增,但满意度增加速率逐渐变缓,根据实际情况,我们可以推测出当乘车点数达到某一值时,满意度会达到最大点。
但根据已知数据和计算软件,我们无法求出最佳乘车点数目。
五、算法的设计和实现五、算法的设计和实现根据题目所给的各区的距离,我们采用0-1规划法求解50个区任意两点间的最小路径。
故设0-1决策变量,其意义为:
ijx01ijijxij=弧(,)不在最短路上弧(,)在最短路上表示弧的长度(路程),若和没有弧连通,对于除了起ijwij(,)ij.ijw=+16点和终点以外的任意一个顶点,如果,说明从出发的所有弧中必然i11nijjx=i有一条弧在最短路上,也就是说最短路经过该顶点,此时所有从其他顶点到达该顶点的弧中必然也有一条弧在最短路上,因而必有如果说明11;njijx=10,nijjx=最短路不经过顶点,故必有且最短路径只有一条,两种情况可以合并i10.njijx=写成111,1,2,.,50.nnijjijjxxi=对于起点1,则必然满足对于终点则必有111,njjx=n11.njnjx=对于已走出起点的路径不得再返回起点,则110.njjx=对于已达终点的不再往回走,则10.nnjjx=目标函数是最短路上的各条弧的长度之和(总路程)最小,于是最短路问题可以用如下0-1规划来描述:
5050115050505011115050150115015011min,1,1,.0,0,01,ijijijijjiijijjijinjjjjijzwxxxxxstxxx=或通过lingo8.0求解后的得到数据(见附录一表3)。
Lingo求解程序如附录。
此外,我们对于满意度和运行成本这两个目标的处理方法也比较特别。
建立了两者之间的关系然后用穷(max)/(maxmin)ijijijijijmdddd=。
举法找到满意度最大情况下站点的位置。
17六、结果的分析和检验六、结果的分析和检验问题问题1首先,用Matlab(Dijkstra算法)和LINGO两个软件对所得的50个区域任意两点之间的最短路径矩阵Cij进行检验,具体程序见附录。
当=2时,通过计算,n应该在18和31点建立乘车点,当=3时,应该在15、21和31点建立乘车点,其最n总短距离,分别为24492m和19660m,通过在老校区区域及各区域间路线分布图上分析,18、31、15、21、31等区都是道路相对密集的区域,且在这些区设置乘车点后各点的乘车路线不交叉,不跨区,因此比较符合距离最小的实际情况。
图1:
老校区区域及各区域间路线分布图问题问题2用归一法定义了满意度与距离的函数关系。
得到的满意度矩阵考虑了距离和乘车人数的影响,所以最优乘车点的设置可能会不同于问题1,当=2时,应选n取19和32点建立乘车点,当=3时,应选取15、21和32点建立乘车点,最大满意n度分别为2148.946和2276.025。
站点数越大,满意度越大,且各站点的位置比较合理,乘车路线不跨区,不交叉。
比较符合实际情况。
我们用了满意度与距离的线性关系进行求解。
并用满意度与距离的余弦函数关系验证,两种函数关系所求的最佳乘车点位置相同,得到检验。
问题问题3第三问是一个双目标规划模型问题,需要考虑运行成本和满意度两个目标函数。
假设每个区域的所有教师和员工会选择近的路线乘车,因此排除教师和工作人员选取远距离的乘车点或去不同乘车点的可能,求出最终结果:
三个乘车点的位置分别为15、21、32,每个乘车点的车辆数目分别为17辆、18辆、20辆,共55辆。
此时到15点乘车的总人数为709,到21点乘车的总人数为810,到32点乘车的18总人数为902。
根据模型建立中给出的满意度与运行成本之间的关系,确定结论比较符合实际情况。
问题4问题4此题我们计算了当n=1,2,3,4,5时的五组数据。
结果如表所示。
根据所得数据,归纳出满意度随乘车点数正相关,并且会在乘车点数取得某一值时,满意度达到最大值。
由于已知数据量和计算方法的限制,我们只能定性给出合理的建议。
我们建议乘车点数目设置为5或6个。
这样既能满足教师和工作人员的满意度大,又能最有效的进
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 校车 安排 问题 论文