校车安排问题(论文)

1校车安排问题摘要我们对老校区乘车点选址问题进行研究，根据校区内教师与员工的分布，提出了最佳乘车点的选取办法，建立了满意度与区域到乘车点距离的函数关系，并根据获得数据模拟了乘车点选址的最优化的模型，得到如下结果：问题1：根据77组给定数据，首先建立了动态规划模型，用Dijkstra算法（Matlab软件实现)求解任意两个区域之间最小路程并检验，得到了任意两点间的最短距离矩阵。再建立选址规划模型，求解使各区域人员到最近乘车点5050D×距离最小得个乘车点的位置。最后求得当=2时，选取18和31点最佳，总最nn短距离为24492m；当=3时，选取15、21和31点最佳，总距离为19660m。n问题2：我们用归一法定义满意度与距离的函数关系，根据问题1中的任意两点间的最短距离矩阵，得到满意度矩阵。根据每个区域的人数，5050D×5050M×得出考虑人数的满意度矩阵。再建立选址规划模型，求解使教师和工作5050RM×人员满意度最大的个乘车点的位置。结果：当=2时，选取19和32点为乘车nn点最佳，总最大满意度为1945.877；当=3时，选取15、21和32点最佳，总最n大满意度为2066.743。问题3：这是一个双目标规划问题，考虑运行成本和满意度两个目标函数，建立双目标非线性规划模型。当各乘车点人数平均分配的时候，运行成本最低，定义为三个乘车点人数的方差，为总满意度，因此要尽量使最小，1k2k1k2k最大。由此可利用的最大值求得使教师和工作人员尽量满意并降低运行成2121kkαα本的3个乘车点位置,其中，、为运行成本和满意度的权重。最后求得设1α2α立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中的任意两点间的最短距离矩阵，得到满意度矩阵。根据每个区域的人数，5050D×5050M×得出考虑人数的满意度矩阵。再建立选址规划模型，求解各区域到个5050RM×n乘车点的总满意度的最大值，再分别求出设置2个和3个乘车点时的结果。针对问题3，考虑运行成本和满意度两个目标函数，建立双目标非线性规划模型。当各乘车点人数平均分配的时候，运行成本最低，定义为三个乘车点人数的方1k符号含义5050D×任意两点之间的最小距离矩阵5050W×表示弧的长度矩阵ij（，）5050M×满意度矩阵5050RM×考虑人数的满意度矩阵501R×每个区的人员数矩阵n设立乘车点的个数irj表示第个乘车点的乘客总数iRJ三个乘车点的平均乘客数、1k2k分别为三个乘车点人数的方差和总体满意度、1α2α分别为运行成本和满意度的权重4差，为总满意度，因此要尽量使最小，最大。由此可用的最大值2k1k2k2121kkαα求最优解,其中，、为运行成本和满意度的权重。最后求出最优解。针对问1α2α题4：对解决问题四采取的方法是把问题三推广到n个乘车点的情况。根据前3问的方法求出更多的数据进行对比分析。考虑满意度，运行成本，乘车点数目三个目标函数，建立多目标规划模型。分析出最佳乘车点数目，进而根据第3问的模型给出最大满意度和需要车辆数。给出合理建议。分析确立动态规划模型画出50个区域分布路线得到各点最小距离矩阵确定满意度函数求的各点最小距离Matlab实现验证考虑满意度影响因素建立选址规划模型求得乘车点位置考虑多个目标函数选用Dijkstra算法分析所得数据提出建议LINGO实现优化模型模型建立：问题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个区任意两点距离的50×50的矩阵（部分5050D×见表2）和最短路径（部分见附录一表1）。表2：部分任意两点最短距离矩阵（前10×10）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）的距离区域12345678距离11547541114514360480160330区域910111213141516距离520460610750950490300130区域1718192021242526距离2700204344524350180650价格2747距离510874各区域到所选乘车点（区域31）的距离区域2223282930313233距离7104004501902400230420区域3435363738394041距离630370260530570440400540区域4243444546484950距离3704505506609008901090210总距离各区域到所选两乘车点（18、31)的总最短距离：24492m各区域到所选乘车点（区域15）的距离区域56789101112距离655625455285340160310450区域1314151617182526距离6501900170250300480380区域27距离490各区域到所选乘车点（区域21）的距离区域123419202122距离63023010805303201800300区域23244445464748499问题二我们对于问题二首先采取的办法是建立满意度和乘客到乘车点距离的函数关系式。我们采用归一法定义的满意度矩阵：5050M×