浅谈校车安排问题论文.pdf

1 校车安排问题校车安排问题 摘要摘要 我们对老校区乘车点选址问题进行研究，根据校区内教师与员工的分布，提 出了最佳乘车点的选取办法，建立了满意度与区域到乘车点距离的函数关系，并 根据获得数据模拟了乘车点选址的最优化的模型，得到如下结果： 问题 1：根据 77 组给定数据，首先建立了动态规划模型，用 dijkstra 算法 （matlab 软件实现)求解任意两个区域之间最小路程并检验，得到了任意两点间 的最短距离矩阵。再建立选址规划模型，求解使各区域人员到最近乘车点 50 50 d 距离最小得个乘车点的位置。最后求得当=2 时，选取 18 和 31 点最佳，总最nn 短距离为 24492m；当=3 时，选取 15、21 和 31 点最佳，总距离为 19660m。n 问题 2：我们用归一法定义满意度与距离的函数关系，根据问题 1 中的任意 两点间的最短距离矩阵，得到满意度矩阵。根据每个区域的人数， 50 50 d 50 50 m 得出考虑人数的满意度矩阵。再建立选址规划模型，求解使教师和工作 50 50 rm 人员满意度最大的个乘车点的位置。结果：当=2 时，选取 19 和 32 点为乘车nn 点最佳，总最大满意度为 1945.877；当=3 时，选取 15、21 和 32 点最佳，总最n 大满意度为 2066.743。 问题 3：这是一个双目标规划问题，考虑运行成本和满意度两个目标函数， 建立双目标非线性规划模型。当各乘车点人数平均分配的时候，运行成本最低， 定义为三个乘车点人数的方差，为总满意度，因此要尽量使最小，1k2k1k2k 最大。由此可利用的最大值求得使教师和工作人员尽量满意并降低运行成 2 1 2 1 k k 本的 3 个乘车点位置,其中，、为运行成本和满意度的权重。最后求得设12 立3个乘车点时， 分别为15、 21和32点， 需要校车55辆；的最大值为 12.962， 2 1 2 1 k k 其中方差=2378.7，满意度=2276.025。 12 1,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 软件分别求解任意两个区域之间最小路程并检验， 得到任意两点间的最 短距离矩阵。再建立选址规划模型，求解各点到个乘车点总距离的最小值， ij dn 进而求出个乘车点的设立位置，再分别求出设置2个和3个乘车点时的结果。n 针对问题问题2：用归一法定义满意度与距离的函数关系，根据问题1中的任意 两点间的最短距离矩阵，得到满意度矩阵。根据每个区域的人数， 50 50 d 50 50 m 得出考虑人数的满意度矩阵。再建立选址规划模型，求解各区域到个 50 50 rm n 乘车点的总满意度的最大值，再分别求出设置2个和3个乘车点时的结果。针对 问题3，考虑运行成本和满意度两个目标函数，建立双目标非线性规划模型。当 各乘车点人数平均分配的时候，运行成本最低，定义为三个乘车点人数的方1k 符号含义 50 50 d 任意两点之间的最小距离矩阵 50 50 w 表示弧的长度矩阵ij（，） 50 50 m 满意度矩阵 50 50 rm 考虑人数的满意度矩阵 5 01 r 每个区的人员数矩阵 n 设立乘车点的个数 i rj 表示第 个乘车点的乘客总数i rj三个乘车点的平均乘客数 、1k2k分别为三个乘车点人数的方差和总体满意度 、12分别为运行成本和满意度的权重 4 差，为总满意度，因此要尽量使最小，最大。由此可用的最大值2k1k2k 2 1 2 1 k k 求最优解,其中，、为运行成本和满意度的权重。最后求出最优解。针对问 12 题4：对解决问题四采取的方法是把问题三推广到n个乘车点的情况。根据前3 问的方法求出更多的数据进行对比分析。考虑满意度，运行成本，乘车点数目三 个目标函数，建立多目标规划模型。分析出最佳乘车点数目，进而根据第3问的 模型给出最大满意度和需要车辆数。给出合理建议。 分析确立动态规划模型 画出50个区域分布路线 得到各点最小距离矩阵 确定满意度函数 求的各点最小距离 matlab 实现 验证 考虑满意度影响因素 建立选址规划模型 求得乘车点位置考虑多个目标函数 选用dijkstra算法 分析所得数据 提出建议 lingo 实现 优化模型 模型建立： 问题1 模型建立： 问题1 5 这是一个图论模型中的最短路问题。我们通过数据整理分析，绘出了各区域 分布位置简图，如下： 图1：老校区区域及各区域间路线分布图 根据题目所给的各区的距离，我们采用0-1规划法求解50个区任意两点间的 最小路径。 故设0-1决策变量，其意义为： ij x 0 1 ij ij x ij = 弧（，）不在最短路上 弧（，）在最短路上 表示弧的长度（路程） ，若 和没有弧连通，对于除了起 ij wij（，）ij. ij w = + 点和终点以外的任意一个顶点 ，如果，说明从 出发的所有弧中必然i 1 1 n ij j x = = i 有一条弧在最短路上，也就是说最短路经过该顶点，此时所有从其他顶点到达该 顶点的弧中必然也有一条弧在最短路上，因而必有如果说明 1 1; n ji j x = = 1 0, n ij j x = = 最短路不经过顶点 ，故必有且最短路径只有一条，两种情况可以合并i 1 0. n ji j x = = 写成 11 1,1, 2 ,., 5 0. nn ijji jj xxi = = = 6 对于起点1，则必然满足对于终点则必有 1 1 1, n j j x = = n 1 1. n jn j x = = 对于已走出起点的路径不得再返回起点，则 1 1 0. n j j x = = 对于已达终点的不再往回走，则 1 0. n n j j x = = 目标函数是最短路上的各条弧的长度之和（总路程）最小，于是最短路问题 可以用如下0-1规划来描述： 5050 11 50505050 1111 5050 150 11 50 150 11 min, , 1,1, . 0,0, 01, ijij ij ijji ijij ji ji n jj jj ij zw x xx xx s t xx x = = = = = = = = 或 我们通过lingo8.0求解得到50个区任意两点距离的5050的矩阵（部分 50 50 d 见表2）和最短路径（部分见附录一表1） 。 表2：部分任意两点最短距离矩阵（前1010） 12345678910 1040045070091011401110128014801614 2400085030051074071088010801214 3450850060081010401010118013801560 47003006000210440410580780960 59105108102100230200370570750 6114074010404402300320340540720 7111071010104102003200170370550 8128088011805803703401700200380 91480108013807805705403702000180 101614121415609607507205503801800 7 之后我们用0-1规划法求解使各区人员到最近乘车点的距离最小时个乘车n 点的位置。 故设0-1决策变量和,其意义为： ij y j p 1, 0, ij ij y ij = 区的人选择去 区乘车， 区的人不选择去 区坐车， 1, 0, j j p j = 区设立乘车点， 不设立乘车点, 表示 区到区的最小距离。对于 区的人员，50个区中他们至少且至多 ij diji 只能去其中一个区乘车，因而有且区是否设立乘车点跟是否有人前去 50 1 1, ij j y = = 乘车有关，即如果没有人前往乘车点，则表示点不设乘车点，因为如果有乘车j 点，至少自己区的人会在本区乘车；同样，如果有人前往点乘车，则点必定jj 设立了乘车点，因此有要求设立站点的总人数为，max ,1,2, ,50, jij pyi=n 故有，目标函数是50个区的人员到个乘车点的总距离最小，于是选 50 1 j j pn = = n 址0-1规划模型可以用如下0-1规划法描述： 5050 11 50 1 50 1 m in m ax,1, 2, 50, , . 1, 01, ijij ij jij j j ij j ij zdy pyi pn s t y y = = = = = = = = = 或 我们通过用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 区域2324444546474849 9 问题二问题二 我们对于问题二首先采取的办法是建立满意度和乘客到乘车点距离的函数 关系式。我们采用归一法定义的满意度矩阵： 50 50 m (max)/(maxmin), ijijijijij mdddd= 考虑每个区的人数定义考虑人数的满意度，矩阵，具体求解方 i r ijiji rmmr= 法是将的每一行乘其行所对应的， 我们用0-1规划法求解使各区人员到最 50 50 m i r 近乘车点的满意度最大时个乘车点的位置。这同样是一个选址规划模型。n 故设0-1决策变量和,其意义为： ij y j p 1, 0, ij ij y ij = 区的人选择去区乘车， 区的人不选择去区坐车， 1, 0, j j p j = 区设立乘车点， 不设立乘车点, 表示 区所有人员到区的乘车的满意度。对于 区的人员，50个区中他们 ij rmiji 至少且至多只能去其中一个区乘车， 因而有且区是否设立乘车点跟 50 1 1, ij j y = = j 是否有人前去乘车有关，即如果没有人前往点乘车。则表示点不设乘车点，jj 因为如果有乘车点，至少自己区的人会在本区乘车；同样，如果有人前往点乘j 距离270370420570760350480680 各区域到所选乘车点（区域 31）的距离各区域到所选乘车点（区域 31）的距离 区域2829303132333435 距离4501902400230420630370 区域3637383940414243 距离260530570440400540370450 区域50 距离210 总距 离 各区域到所选三个乘车点（15、21、31)的 总最短距离：19660m 10 车，则点必定设立了乘车点，因此有要求设立站点jmax,1,2,50, iij pyi= 的总人数为n，故有，目标函数是50个区的人员到个乘车点的总距 50 1 , j j pn = = n 离最小，于是选址0-1规划模型可以用如下0-1规划法描述： 5050 1 50 1 50 1 max, max,1,2,50, , .1, 01, 01, ijij ij iij j j ij j ij j rm y pyi pn s ty y p = = = = = = = = = 或 或 我们通过用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.4 11 表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.0 12 低，定义k1为三个乘车点人数的方差 222 123 123 1=()()() 3, , 3 nnn nnn krjrjrjrjrjrj rjrjrj rj + + = 其中表示第个乘车点的乘客总数。为三个乘车点的平均乘客数。 i rjirj 为总体满意度。且运行成本向最小取优，满意度向最大取优。由于两个目标2k 函数彼此矛盾，可对的最大值求最优解,即，其中，、 2 1 2 1 k k 2 1 2 max 1 k k =12 为运行成本和满意度的权重，由于与量纲不同，而的量纲为一，所以2k1k 2 1 2 1 k k 与的比值即为与量纲的比值，即,且由于211k2k 122 2 121 k k = 可得与层次分析法的得到的结果基本吻合。121+= 12 1,2, 33 = 设0-1决策变量和,其意义为： ij y j p 1, 0, ij ij y ij = 区的人选择去 区乘车， 区的人不选择去 区坐车， 1, 0, j j p j = 区设立乘车点， 不设立乘车点, 表示 区所有人员到区的乘车的满意度。对于 区的人员，50个区中他 ij rmiji 们至少且至多只能去其中一个区乘车，因而有 ， 且区是否设立乘车 50 1 1, ij j y = = j 点跟是否有人前去乘车有关， 即如果没有人前往乘车点， 则表示点不设乘车点，j 因为如果有乘车点，至少自己区的人会在本区乘车；同样，如果有人前往点乘j 车，则点必定设立了乘车点，因此有要求设立站点jmax,1,2,50, jij pyi= 的总人数为n，故有，50个区的人员到个乘车点的总满意度 50 1 3 j j p = = n 13 ，各乘车点的乘客数为 5050 11 2 ijij ij krm y = = 50 1 , jiij i rjr y = = 2 5050 3 11 1 222 3 123 50 1 50 1 max ()()()3 max,1,2,50, 3 .1, 01 01 ijij ij rm y nnn jij j j ij j ij j z rjrjrjrjrjrj pyi p s ty y p = = = = + = = = = = 或 ， 或 ， 我们通过matlab求解得：的最大值为12.962，其中方差 2 1 2 1 k k 12 1,2, 33 = =2378.7， 满 意 度=2276.025；，1k2k115n=221n=31n= ；三乘车点的车的数量分别为17，18，20，共需55 123 790,810,902 nnn rjrjrj= 辆车。如表5： 表5：设立三个乘车点时选址方案及各乘车点车辆数 问题四问题四 我们对问题四采取的方法是把问题三推广到n个乘车点的情况。由于运算量 乘车点数满意度乘车点位置 去往乘车点 的总人数 各站点需要 的车辆数 32276.025 1579017 2181018 3290220 14 较大，在此我们给出n=1，2，3，4，5时的数据，如表6和图2所示： 表6：乘车点数目不同情况下考虑满意度及车辆数部分数据统计表 乘车点数满意度乘车点位置 去往乘车点 的总人数 各站点需要 的车辆数 各站点需要 的车辆总数 12091.5291925025454 22148.946 19151433 55 3298822 32276.025 1579017 552181018 3290220 42325.966 24179 55 1580018 3268915 4459613 52364.084 23257 55 113648 1859213 223889 3283318 15 图2：最大满意度与乘车点数的关系 由表中数据可以看出，仅当一点的时候运营费用最小，只需54辆校车。而在 建立三个乘车点的前提下，校车需要数量只有三种情况：54辆，55辆，56量。54 辆无疑为最理想情况，但由于各地区人数复杂不易统计，2、3、4、5点均需要55 辆校车，因此我们考虑取55辆校车为可接受数量。此时考虑下一个目标，满意度 的问题。由图2可以看出，当乘车点数在1到5变化时，随着乘车点数目增加，满 意度递增，但满意度增加速率逐渐变缓，根据实际情况，我们可以推测出当乘车 点数达到某一值时，满意度会达到最大点。但根据已知数据和计算软件，我们无 法求出最佳乘车点数目。 五、 算法的设计和实现五、 算法的设计和实现 根据题目所给的各区的距离，我们采用0-1规划法求解50个区任意两点间的 最小路径。 故设0-1决策变量，其意义为： ij x 0 1 ij ij x ij = 弧（，）不在最短路上 弧（，）在最短路上 表示弧的长度（路程） ，若 和没有弧连通，对于除了起 ij wij（，）ij. ij w= + 16 点和终点以外的任意一个顶点 ，如果，说明从 出发的所有弧中必然i 1 1 n ij j x = = i 有一条弧在最短路上，也就是说最短路经过该顶点，此时所有从其他顶点到达该 顶点的弧中必然也有一条弧在最短路上，因而必有如果说明 1 1; n ji j x = = 1 0, n ij j x = = 最短路不经过顶点 ，故必有且最短路径只有一条，两种情况可以合并i 1 0. n ji j x = = 写成 11 1,1, 2 ,., 5 0. nn ijji jj xxi = = = 对于起点1，则必然满足对于终点则必有 1 1 1, n j j x = = n 1 1. n jn j x = = 对于已走出起点的路径不得再返回起点，则 1 1 0. n j j x = = 对于已达终点的不再往回走，则 1 0. n n j j x = = 目标函数是最短路上的各条弧的长度之和（总路程）最小，于是最短路问题 可以用如下0-1规划来描述： 5050 11 50505050 1111 5050 150 11 50 150 11 min, , 1,1, . 0,0, 01, ijij ij ijji ijij ji ji n jj jj ij zw x xx xx s t xx x = = = = = = = = 或 通过lingo8.0求解后的得到数据（见附录一表3） 。lingo求解程序如附录。 此外，我们对于满意度和运行成本这两个目标的处理方法也比较特别。建立 了两者之间的关系然后用穷 (max)/(maxmin) ijijijijij mdddd=。 举法找到满意度最大情况下站点的位置。 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个。这样既能满足教师和工作人员的满意 度大，又能最有效的进行车辆安排，节省运行成本。 七、模型优缺点七、模型优缺点 优点： 1.优化模型较为典型，模型建立思想成熟、清晰，假设合理，约束分析有条理， 表达公示较为综合，简单易懂，易于计算和推广。 2. 本文首先根据题中所给数据量绘制一张无向图（见附录二图 1）,并利用 dijkstra算法求出我们所需要的各区域之间的最短路径矩阵,从而建( , )d i j 立选址模型。 3.用归一法定义满意度与距离的函数，讲问题合理的简化。 4.模型中大量采用的矩阵思想、物流中心选址问题模型，多目标规划模型，使 问题处理较为简便，思想上的可借鉴性较强。 5.采用多种方法验证结果的准确性，活用lingo和matlab软件。 6.注意根据实际情况分析问题，将数学思想与现实紧密结合，并能较好的用获 得的数据进行分析总结。 缺点： 1.满意度关于距离的函数关系式不够完整，虽然已尽量贴近实际，由于我们计 算能力不足，不能够进行过于复杂化得分段函数满意度问题，没有精益求精。 图3：距离满意度完整函数 19 其中f（ui）为距离满意度，li为分段函数分界点，li之前表示可接受距离内， 满意度变化几乎为零。 2.约束考虑较为简单，与实际情况有一定的差异度，难于直接应用于实践，无 法完全解决多目标规划问题。 八、模型的推广八、模型的推广 本问题建立的选址模型，满意度与距离的函数关系，运用多目标规划模型， 具有较强的准确性和实用性，可以对大量数据和多个目标函数进行计算分析，得 到有效的方案。 对于不同的约束条件，可能的方案将会有不同的类型，如果只考虑单一距离 因素，则可建立选址模型，求出最佳乘车点的设立，而不需要考虑满意度、成本 等其他因素；否则，就需要建立多目标规划模型，同时考虑不同的目标函数对乘 车点设立的影响，如，考虑满意度与距离和拥挤程度有关，则需要建立更完整的 模型，建立多个目标函数，最终得出合理的方案。最后一问，则需要联系实际从 多方面因素考虑。从以上描述，我们看出对于不同的约束条件，可能存在不同的 解决策略，我们可以进行理论上的推理论证，也可以利用计算机程序搜索求解。 但需要更多的结合实际情况和数据，进行细致的分析。 九、参考文献九、参考文献 1肖华勇，实用数学建模与软件应用，西北工业大学出版社，2008，9。 2袁新生，邵大宏，郁时炼，lingo和excel在数学建模中的应用，科学 出版社，2006.3。 3常巍， 谢光军， 黄朝峰，matlabr2007基础与提高， 电子工业出版社，2007，8 4阳明盛，罗长童，最优化原理、方法及求解软件，科学出版社，2006，6。 5曹勇，周晓光，李宗元，应用运筹学，经济管理出版社，2008.3。 6徐根玖，规划理论及模型，西北工业大学教务处，2005，3。 8王力工，图论模型，西北工业大学教务处，2005，3 7叶正麟，怎样撰写数学建模竞赛答卷，西北工业大学教务处，2005，3。 8马云峰，张敏，杨珺，物流设施选址中时间满意度函数的定义及应用，物 流技术，2005年第5期。 9张福浩,刘纪平,李青元,基于dijkstra算法的一种最短路径优化算法,中国测 绘科学研究院,2004.2。 20 附录一：附录一： 表 1：任意两个区域间的最短路径（只列出起点为 1 的情况） 区域路径总距离 11-10 21-2400 31-2-3450 41-2-4700 51-2-4-5910 61-2-4-5-61140 71-2-4-5-71110 81-2-4-5-7-81280 91-2-4-5-7-8-91480 101-2-21-20-19-18-16-15-101614 111-2-21-20-19-18-16-15-10-111764 121-2-21-20-19-18-16-15-10-11-121904 131-2-21-20-19-18-6-15-10-11-12-132104 141-2-21-20-19-18-16-15-141644 151-2-21-20-19-18-16-151454 161-2-21-20-19-18-161284 171-2-21-20-19-18-16-171424 181-2-21-20-19-181154 191-2-21-20-19950 201-2-21-20810 211-2-21630 221-2-21-22930 231-2-21-23900 241-2-21-20-241000 251-2-21-20-24-251170 261-2-21-20-24-28-27-261460 271-2-21-20-24-28-271320 21 表 2：任意两区域之间的最短距离 281-2-21-20-24-281130 291-2-21-23-291110 301-2-21-23-301190 311-2-21-23-29-311300 321-2-21-23-29-31-321530 331-2-21-23-29-31-32-331720 341-2-21-20-24-28-27-26-341780 351-2-21-23-29-31-32-351670 361-2-21-23-29-31-361560 371-2-21-23-29-31-32-35-371830 381-2-21-23-29-31-36-39-381870 391-2-21-23-29-31-36-39，1740 401-2-21-23-29-31-50-401700 411-2-21-23-29-31-50-40-411840 421-2-21-23-30-421320 431-2-21-23-44-431310 441-2-21-23-441050 451-2-21-22-451200 461-2-21-22-48-461390 471-2-47540 481-2-21-22-481110 491-2-21-22-48-491310 501-2-21-23-29-31-501510 22 各点之间的最短距离各点之间的最短距离(110) 12345678910 1040045070091011401110128014801614 2400085030051074071088010801214 3450850060081010401010118013801560 47003006000210440410580780960 59105108102100230200370570750 6114074010404402300320340540720 7111071010104102003200170370550 8128088011805803703401700200380 91480108013807805705403702000180 101614121415609607507205503801800 111764136417101110900870700530330150 12190415041850125010401010840670470290 132104170420501450124012101040870670490 141644124416041004845815645475460280 15145410541414814655625455285340160 1612848841244644490610290455510330 17142410241384784630750430535590410 1811547541114514360480160330530460 19950550910310520684364534734664 208104101050450660824504674874804 2163023010805307409706848541054984 22930530138083010401270984115413541284 239005001325725935107075092011201050 2410006001085485695830510680880810 2511707701255655540660340510710640 2614601060154594510101005810665650470 2713209201405805870990670775790610 2811307301215615825960640810980800 291110710147587510851220900107012401060 30119079016151015122513601040121014101340 31130090016651065127514101090126014301250 321530113018951295150516401320138513701190 331720132020751475154015351340119511801000 341780138018651265133013251130985970790 351670127020351435164517801460152515101330 361560116019251325153516701350152016101430 371830143021951595180519401620168516701490 381870147022351635184519801660182018051625 391740134021051505171518501530170017901610 401700130020651465167518101490166018001620 411840144022051605181519501630180019401760 42132092017451145135514901170134015401470 43131091017351135134514801160133015301460 441050650147587510851220900107012701200 45120080016501100131015401254142416241554 46139099018401290150017301444161418141744 47540140990440650880850102012201334 48111071015601010122014501164133415341464 49131091017601210142016501364153417341664 501510111018751275148516201300147016401460 23 附录二：附录二： 图 1：老校区区域及各区域间路线分布图 主要程序： lingo 求任意间的两点最短距离： model: sets: qyh/150/:fl; roads(qyh,qyh)/1,2 1,3 2,4 2,21 2,47 3,4 4,5 4,19 5,6 5,7 6,7 6,8 7,8 7,18 8,9 8,15 9,10 10,11 10,15 11,12 11,1412,1313,3414,1514,2615,1615,1716,17 16,18 17,27 18,1918,2519,2019,2420,2120,2421,2221,23 21,47 22,44 22,4522,4823,2423,2923,3023,4424,2524,28 26,27 26,34 27,2828,2929,3130,3130,4230,4331,3231,36 31,50 32,33 24 32,3532,3633,3435,3736,3936,4037,3838,39 39,41 40,41 40,50 42,50 43,44 43,45 45,46 46,48 48,49 2,1 3,1 4,2 21,2 47,2 4,3 5,4 19,4 6,5 7,5 7,6 8,6 8,7 18,7 9,8 15,8 10,9 11,10 15,10 12,11 14,1113,1234