计量地理学-102-最短路径与选址问题

最短路径与选址问题P＝{vi1，ei1，vi2，ei2，…，eik-1，vik}路径是顶点与边的交替序列集合在地理网络中，给定一个起始点，指定一个终止点，在从起点至终点的所有路径中，找到一条最短的路径，是为最短路径分析。含义？距离最短？时间最少？经济成本最节省？指定障碍点？指定中途点？……最优路径分析“纯距离”意义上的最短路径最短路径的含义“经济距离”意义上的最短路径需要运送一批物资从一个城市到另一个城市，选择什么样的运输路线距离最短？某公司在10大港口C1，C2，…，C10设有货栈，从Ci到Cj之间的直接航运价格，是由市场动态决定的。如果两个港口之间无直接通航路线，则通过第三个港口转运。那么，各个港口之间最廉价的货运线路是什么？“时间”意义上的最短路径某家经营公司有一批货物急需从一个城市运往另一个城市，那么，在由公路、铁路、河流航运、航空运输等4种运输方式和各个运输线路所构成的交通网络中，究竟选择怎样的运输路线最节省时间？赋权图上的最短路径问题空间距离经济成本时间成本权重值连接边地理网络赋权图最短路径分析找出网络中不经过障碍点且权值总和最小的路径找出网络中权值总和最小的路径指定障碍点找出网络中经过中途点且权值总和最小的路径指定中途点最短路径分析算法1959年E.W.Dijkstar提出的标号法是最短路径问题最基础也是应用最广泛的分析求解方法。标号法优点①不仅可以求出起点到终点的最短路径及其长度；②而且可以求出起点到其他任何一个顶点的最短路径及其长度；③同时适用于求解有向图或无向图上的最短路径问题。标号法的基本思想设G是一个赋权有向图，即对于图中的每一条边，都赋予了一个权值。在图G中指定两个顶点，确定为起点和终点，不妨设v1为起点，vk为终点。找到从v1至vk的权值最小路径最短路径分析算法每次有一个顶点的标号由T至P，那么最多经过k-1步，就可以求得到从起点v1到每一个顶点的最短路径及其长度。首先从起点v1开始，给每个顶点标一个符号与数字，称为标号。这些标号又进一步区分为T标号和P标号两种类型。其中，每一个顶点的T标号为临时标号，其数字表示从起点v1到该点的最短路径长度的上界(最大值)；每一个顶点的P标号为固定标号(当前顶点已找到最短路径)，其数字表示从v1到该点的最短路长度。标号法的基本思想在最短路径计算过程中，对于已经得到P标号的顶点，不再改变其标号；对于凡是没有标上P标号的顶点，先给它一个T标号；算法的每一步就是把顶点的T标号逐步修改，将其变为P标号。（即依次修改顶点由临时标号T转换为固定标号P）如何确定顶点由T至P？最短路径分析算法标号法具体计算步骤：初始化，先给v1标上P标号P(v1)＝0，其余各点标上T标号T(vj)＝+∞(j≠1)。①如果刚刚得到P标号的点是vi，那么，找出下列集合包括的所有这样的顶点：标号的标号是而且TvEvvvjjij,,至v1的最短路径已找到)(min)(0jjvTvT0jv0jv②若图G中没有T标号，则停止。否则，把拥有最小T值的顶点的T标号修改为P标号，然后再转入①。其中，满足从vi出发可达的其它临时T标号的顶点并且将其T标号修改为：min[T(vj),P(vi)+wij]vj原最短路径长度与通过vi再至vj的路径长度进行比较取较小值从刚修改完标号数值的所有顶点vj中，将其数值最小的vj0的T标号修改为P标号初始化：P(v1)＝0,T(vj)＝+∞对于最近得到P标号的点vi：找出它直达的所有其它T标号的顶点标号的标号是而且TvEvvvjjij,,更新各顶点vj的权值：min[T(vj),P(vi)+wij]更新最小权值的T标号顶点为P标号当前网络图中已没有T标号顶点停止，最短路径已找到YESNODijkstar标号法算法流程：例1：在下凸所示的赋权有向图中，每一个顶点vi（i=1，2，…，n）代表一个城镇；每一条边代表相应两个城镇之间的交通线，其长度用边旁的数字表示。试求城镇v1到v7之间的最短路径。赋权有向交通阿网络图解：初始化：首先给v1标上P标号P(v1)=0，表示从v1到v1的最短路径为零；其他点(v2，v3，…，v7)标上T标号T(vj)＝+∞（j＝2，3，…，7）。P0T+∞T+∞T+∞T+∞T+∞T+∞第1步：①v1是刚得到P标号的点。因为(v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T标号，所以修改这3个点的T标号数值为：T(v2)＝min[T(v2)，P(v1)+w12]＝min[+∞，0+2]＝2T(v3)＝min[T(v3)，P(v1)+w13]＝min[+∞，0+5]＝5T(v4)＝min[T(v4)，P(v1)+w14]＝min[+∞，0+3]＝3P0T+∞T+∞T+∞②在所有T标号中，T(v2)＝2最小，于是令P(v2)＝2。T2T5T3P2第2步：①v2是刚得到P标号的点。因为(v2，v3)，(v2，v6)∈E，而且v3,v6是T标号，故修改v3和v6的T标号为：T(v3)＝min[T(v3)，P(v2)+w23]＝min[5，2+2]＝4T(v6)＝min[T(v6)，P(v2)+w26]＝min[+∞，2+7]＝9②在所有的T标号中，T(v4)＝3最小，于是令P(v4)＝3。P0T+∞T+∞T+∞T5T3P2T9T4P3第3步：①v4是刚得到P标号的点。因为(v4，v5)∈E，而且v5是T标号，故修改v5的T标号为T(v5)＝min[T(v5)，P(v4)+w45]＝min[+∞，3+5]＝8②在所有的T标号中，T(v3)＝4最小，故令P(v3)＝4。P0T+∞T+∞P2T9T4P3T8P4第4步：①v3是刚得到P标号的点。因为(v3，v5)，(v3，v6)∈E，而且v5和v6为T标号，故修改v5和v6的T标号为：T(v5)＝min[T(v5)，P(v3)+w35]＝min[8，4+3]＝7T(v6)＝min[T(v6)，P(v3)+w36]＝min［9，4+5]＝9P0T+∞P2T9P3T8P4②在所有的T标号中，T(v5)＝7最小，故令P(v5)＝7。T7T9P7第5步：①v5是刚得到P标号的点。因为(v5，v6)，(v5，v7)∈E，而且v6和v7都是T标号，故修改它们的T标号为：T(v6)＝min[T(v6)，P(v5)+w56]＝min[9，7+1]=8T(v7)＝min[T(v7)，P(v5)+w57]＝min[+∞，7+7]=14②在所有T标号中，T(v6)＝8最小，于是令：P(v6)＝8。P0T+∞P2P3P4T9P7T8T14P8第6步：①v6是刚得到P标号的点。因为(v6，v7)∈E，而且v7为T标号，故修改它的T标号为T(v7)＝min[T(v7)，P(v6)+w67]＝min[14，8+5]=13②目前只有v7是T标号，故令：P(v7)＝13。P0P2P3P4P7T14P8T13P13从v1到v7之间的最短路径为(v1，v2，v3，v5，v6，v7)，最短路径长度为13。？标号法另一种解答表现形式：0标号权值V1P0V2T∞V3T∞V4T∞V5T∞V6T∞V7T∞1标号权值P0P2T5T3T∞T∞T∞(注：黄色表示顶点标号顺序；绿色表示顶点权值更新内容)2标号权值P0P2T4P3T∞T9T∞3标号权值P0P2P4P3T8T9T∞4标号权值P0P2P4P3P7T9T∞5标号权值P0P2P4P3P7P8T146标号权值P0P2P4P3P7P8P13标号顺序：V1V2V4V3V5V6V7优先连接顺序：V2V3V5V5V6V7选址问题对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题。在路径的优选计算问题中，最常见的是最短路径分析；而在顶点的优选计算问题中，最为常见的是中心点和中位点选址问题。选址问题的数学模型取决于两个方面的条件：可供选址的范围、条件；怎样判定选址的质量。本节讨论仅限于选址的范围是一个地理网络，而且选址位置位于网络图的某一个或几个顶点上。对这样的选址问题，根据其选址的质量判据，可以将其归纳为求网络图的中心点与中位点两类问题。中心点选址问题中心点选址问题的质量判据：中心点选址问题适宜于医院、消防站点等一类服务设施的布局，所谓中心点选址，即从地理网络图中找到最佳选址位置使得所在顶点的最大服务距离为最小。中心点选址问题的数学描述设G＝(V,E)是一个无向简单连通赋权图，连接两个顶点的边的权值代表它们之间的距离，对于某个顶点vi，它与其它各顶点之间的最短路径长度为di1，di2，…，din。这些最短路径长度距离中的最大数称为顶点vi的最大服务距离，记为e(vi)。那么，中心点选址问题，就是求网络图G的中心点vi0，使得其满足：)(min)(0iiiveve例：假设某县下属的6个乡镇及其之间公路联系如下图所示。每一顶点代表一个乡镇；每一条边代表连接两个乡镇之间的公路，每一条边旁的数字代表该条公路的长度。现在要设立一个消防站，为全县的6个乡镇服务。试问该消防站应该设在哪一个乡镇（顶点）？为何消防站的选址要倾向于中心点，即最大服务距离最小？027474205256750343423036754303463630666564636261565554535251464544434241363534333231262524232221161514131211ddddddddddddddddddddddddddddddddddddD解：第1步：用标号法求出每一个顶点vi至其他各个顶点vj的最短路径长度dij(I,j＝1,2,…,6)，并将它们写成如下的最短路径长度距离矩阵:最短路径长度距离矩阵是上下三角对称矩阵？第2步：求每一个顶点的最大服务距离。显然，它们分别是矩阵D中各行或各列的最大值，即：027474205256750343423036754303463630666564636261565554535251464544434241363534333231262524232221161514131211ddddddddddddddddddddddddddddddddddddDe(v1)＝6，e(v2)＝7，e(v3)＝6，e(v4)＝7，e(v5)＝6，e(v6)＝7Max第3步：判定。因为e(v1)＝e(v3)＝e(v5)＝min{e(vi)}＝6，所以v1,v3,v5都是中心点。也就是说，消防站设在v1,v3,v5中任何一个顶点上都是可行的。中位点选址问题中位点选址问题的质量判据：所谓中位点选址，即从地理网络图中找到最佳选址位置使得所在顶点到其他各个顶点的最短路径距离的总和达到最小（或者以各个顶点的载荷加权求和）。中位点选址问题的数学描述设G＝(V,E)是一个无向简单连通赋权图，连接两个顶点的边的权值代表它们之间的距离，对于某个顶点vi，有一个正的负荷a(vi)，它与其它各顶点之间的最短路径长度为di1，di2，…，din。那么，中位点选址问题，就是求图G的中位点vi0，使得：njijjiiiidvavSvS10)(min)(min)(例3：某县下属7个乡镇，各乡镇所拥有的人口数a(vi)(i=1,2,…,7)，以及各乡镇之间的距离wij(i,j=1,2,…,7)。如图所示。现在需要设立一个中心邮局，为全县所辖的7个乡镇共同服务。问该中心邮局应该设在哪一个乡镇（顶点）？为何邮局的选址要倾向于中位点，即最短路径长度加权总和最小？解：第1步：用标号法求出每一个顶点vi至其他各个顶点vj的最短路径长度dij(i,j＝1,2,…,7)，并将其写成如下最短路径长度距离矩阵：777675747372716766656463626157565554535251