校车安排问的题论文.doc

校车安排问题09财管一班汤路路200910330230一、 问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新 校区由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆根据 附录表一、二的数据，合理、冇效的设置乘车点，安排车辆让教师和工作人员 尽量满意问题如要建立〃个乘车点，为使各区人员到最近乘车点的距离最小，该将 校车乘车点应建立在哪72个点建立一般模型，并给出72 = 2,3吋的结果问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将 校车乘车点应建立在哪〃个点建立一般模型，并给出n = 2,3时的结果问题3：若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排 多少辆车？给出每个乘车点的位置和车辆数设每辆车最多载客47人（假定车 只在起始站点载人）问题4：关于校车安排问题，你还有什么好的建议和考虑可以提高乘车人 员的满意度，又可节省运行成本二、 基本假设1. 假设未给出距离的两个区可以通过其他区间接到达2. 每位教师及工作人员均选择最短路径乘车3. 乘车点均建在各区内，不考虑区与区之间4. 教师及工作人员到各站点乘车的满意度与到该站点的距离有关系，距离近则 满意度高，距离远则满意度低。

5. 假设任意时刻任意站点均有车，不考虑教师及工作人员的等车时间6. 在乘车点区内的人员乘车距离为零7. 根据实际情况，我们假设所设置的乘车点数不大于50假设所有人员均乘车三、符号的说明符号表示意义第i个区域匸1,2,3,...50Vi第i个区域匸1,2,3,...50dij第i区与第j区的最短距离 匸1,2,3,...50 j=1,2,3,…50D任意两区的最短距离矩阵「a含义是从y到Vj的最短路要经过点号为乡的点.符号表示意义R任意两区最短距离路径矩阵St表不t区教师和工作人员到最近乘车点的距离Pt表示t区的乘车人数，Bt表示山乘车点应安排的车辆数t=1,2,3Wt表示t区人数Pt乘以距离St四、问题分析许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新 校区由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆因此 有必要合理设置乘车点并安排各站点的车辆数目，以便最大程度上满足教师及工 作人员的需要我们假设教师和工作人员去乘车时都去最近的乘车点这样，他们走的路程 越短，就越满意在我们设置好乘车点后，每个人走的路程和加所得的和最小时, 教师和工作人员乘车的总体满意度就最高。

若考虑各区人数的差界，则在前一问题的基础上给路程Z和乘以各区人数， 所得值越小则满意程度越高五、模型建立与求解问题一模型的建立及求解：第一步:用Floyd算法求出距离矩阵D二(dij)欣『・1. 算法的基本思想直接在图的带权邻接矩阵中用插入顶点的方法依次构造出)/个矩阵D⑴、D⑵、・・・、D(v),使最后得到的矩阵成为图的距离矩阵，同时也求出 插入点矩阵以便得到两点间的最短路径.2. 算法原理(1) 求距离矩阵的方法D(0) _ z 1 (0) \一® )"根据题口所给各区距离表列出D⑹二(d『))50X50距离矩阵① D（1）=（好））旳，其中好）=mina『,d『）+£（；）｝ 船' 是从Vi到Vj的只允许以仏作为中间点的路径中最短路的长度.② D⑵二（妒）“，其中 d『）=mm｛d.. \d-2 + d男｝r（2）dij是从Vi到Vj的只允许以Vi、也作为中间点的路径中最短路的长度.© D⑵二⑷"））旳,其中畤）=min同厂）,巒+犷）｝是从Vi到Vj的只允许以 a、…乂作为中间点的路径中最短路的长度.即是从Vi到％中间可插入任何顶点的路径中最短路的长，因此X即是距离矩阵.（2）求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R，R二（©）也，厂力的含义 是Vi到Vj的最短路耍经过点号为77/的点.每求得一个D"时，按下列方式产生相应的新的R（k）⑹ k 若犷）＞妒）+犷）i ~］川-1）即当Vk被插入任何两点间的最短路径时，被记录在R"中，依次求 时求得R（v,可由R v来查找任何点对之间最短路的路径.（3）查找最短路径的方法川）—n若© 一 Pi,则点0/是点,到点丿的最短路的中间点.然后用同样的 方法再分头查找.若：(v) (v} (y}(1 )向点 i 追朔得：ripx = Pl , rip2 = P3,…，ripk = Pk (v) (v\ (v) •(2)向点丿追朔得：\j = Q\, rq]j = q2,…，rqJ = j则由点，到丿的最短路的路径为：A厲，…,卩2，卩1,创，％，•••，％，)3. 算法步骤12345610400450700910114024000850300510740345085006008101040470030060002104403910510810210023061140740104044023007111071010104102003208128088011805803703409148010801380780570540481110710156010101220145049131091017601210142016505()151011101875127514851620789484950111012801480111013101510710880108071091011101010118013801560176018754105807801010121012752003705701220142014853203405401450165016200170370116413641300170020013341534147037020001534173416401164133415340200110013641534173420001300130014701640110013000Floyd算法：求任意两点间的最短路 D(i,j)： 2•到丿的距离.R(i, j)： i到丿之间的插入点. 输入：带权邻接矩阵w(if j)(1 )赋初值：对所有 i, j, d(i, j)jw(i, j), r(i, j)lj, k—(2)更新 d(i, j), r(i, j)对所有 Z Z 若 d(i, k)+d(k, j)〈d(i, j),则 d(i, j)jd(i, k)+d(k, j), r(if j)lk⑶若A=V ,停止.否则klk+1,转(2 ).用Mat lab编程得D(50)= (dsj) 50x50，其中dj即为两点最短距离,同时可求出路 径矩阵错误！未找到引用源。

D 叫(dij) 50X50矩阵如下:第二步：设置n个乘车点时的取点情况算法思路：我们假设教师和工作人员去乘车时都去最近的乘车点这样，他们走 的路程越短，就越满意在我们设置好乘车点后，由于不考虑每个区的乘车人数, 每个区人员到最近乘车点乘车，乘车所走最短距离相加所得的总和最小吋，教师 和工作人员乘车的总体满意度就最高步骤如下:dit表示t区到i区的最短距离,当N=2时，以m,他区为乘车点时，s’表示t区教师和工作人员到最近乘车点的距离,即 min{dnit , dn2t} <>S总错误!未找到引用源{dnlt, dn2t},因为有50个区，这样就冇错误！未找到引用源种选择乘车点位置的方法，S 总共有错误！未找到引用源个，用C语言编程选出最小值的S总，此吋S总 值对应的lb值即为乘车点应选择的区当N=3时，以n 1, n2, n3区为乘车点时，S’表示t区教师和工作人员到最近乘车 点的距离，即 min{dnlt , dn2t , dn3t} oS总错误!未找到引用源o {dnlt, dn2t, d„3t},因为有50个区，这样就有错误！未找到引用源种选择乘车点位置的方法，S 总共有错误！未找到引用源。

个，用C语言编程选出最小值的S总，此时S总 值对应的m, n2,①值即为乘车点应选择的区当N〈=50时，以山，“2, rh… m区为乘车点时，St表示t区教师和丄作人员 到最近乘车点的距离，即min{dnll , d n2t, dn3l cLJS总二错误！未找到引用源d“，心・・也）,因为有50个区，这样就有错误！未找到引用源种选择乘车点位置的方法，S 总共有错误！未找到引用源个，用C语言编程选出最小值的S总，此时S总 值对应的n2, n3…m值即为乘车点应选择的区问题二模型的建立及求解算法思路：我们假设教师和工作人员去乘车时都去最近的乘车点这样，他们走 的路程越短，就越满意在我们设置好乘车点后，考虑到每个区的人数不同这 样，每个人到最近乘车点乘车，乘车所走最短距离相加所得的总和最小时，教师 和工作人员乘车的总体满意度就最高步骤如下:Pt表示t区的乘车人数，du表示i区与j区的最短路径值，当N=2时，以m,他区为乘车点吋，s’表示t区教师和工作人员到最近乘车点的距离,即 min{dnit , dn2t） o我们以t区人数Pt乘以距离s作为肌值，即Wt=Pt*St= Pt*min{dnH , dn2t}W总二错误！未找到引用源。

二错误！未找到引用源W总值可作为所有教师和工作人员乘车满意度H的衡量标准，即当W总越小，满 意度II越高w总越大，满意度II越低因为有50个区，这样就冇错误！未找到引用源种选择乘车点位置的方法，即 有错误！未找到引用源个W总值用C语言编程选出垠小值的W总值，此时W 总值对应的m,匕值即为乘车点应选择的区当N=3时，以n 1, n2, n3区为乘车点时，S’表示t区教师和工作人员到最近乘车 点的距离，即 min {doit , dn2t , dn3t} □我们以t区人数Pt乘以距离S作为M值，即肚二Pt*St二 Pt*min{dnlt , dn2l, dn3l}W总二错误！未找到引用源二错误！未找到引用源W总值可作为所有教师和工作人员乘车满意度II的衡量标准，即当W总越小，满 意度H越高W总越大，满意度H越低因为冇50个区，这样就冇错误！未找到引用源种选择乘车点位置的方法，即 有错误！未找到引用源个W总值用C语言编程选出最小值的W总值，此时W 总值对应的nb n2, m值即为乘车点应选择的区以此类推，当N二n时，以m, n2, m・・・.・ m区为乘车点时，s’表示t区教师和工作人员到最近乘车点的距离，即min{dnlt , dn2l, dn3t。