基于最短路径和最小生成树的山区医疗点选址及道路规划

问题背景

假设某山区中有100个村庄，需要建立3个医疗点，并对现有道路进行部分维修，方便村民看病。目标是：

最小化村民到医疗点的总距离： 确定3个医疗点的最佳位置，使所有村庄到最近医疗点的距离总和最小。2. 最小化道路维修总里程： 在满足村民就医需求的前提下，选择维修哪些道路可以使总里程最短。

数据说明

位置.xlsx： 包含100个村庄的坐标信息（单位：米）。* 连接道路.xlsx： 包含可选道路的起点、终点和长度信息。

解决方案

1. 医疗点选址

算法：

构建邻接矩阵： 根据可选道路信息构建邻接矩阵，表示村庄之间的连通性和距离。2. 计算最短距离： 利用Floyd算法计算任意两个村庄之间的最短距离。3. 贪心选择医疗点： * 将所有村庄按照到最近医疗点的距离从小到大排序。 * 依次选择距离最小的村庄作为医疗点，直到选择了3个。 * 为避免医疗点过于集中，设置距离阈值，只有当候选医疗点到已选医疗点的距离大于阈值时才选择该点。

**Matlab代码：**matlab% 读入数据pos = readtable('位置.xlsx');connect = readtable('连接道路.xlsx');

% 构建邻接矩阵n = height(pos);adj = inf(n);for i = 1:height(connect) adj(connect{i,2}, connect{i,3}) = pdist2(pos{connect{i,2}, 2:3}, pos{connect{i,3}, 2:3}); adj(connect{i,3}, connect{i,2}) = pdist2(pos{connect{i,3}, 2:3}, pos{connect{i,2}, 2:3});endfor i = 1:n adj(i, i) = 0;end

% Floyd 算法求任意两点间最短距离for k = 1:n for i = 1:n for j = 1:n if adj(i, k) + adj(k, j) < adj(i, j) adj(i, j) = adj(i, k) + adj(k, j); end end endend

% 按照到最近医疗点的距离排序dist = sum(adj, 2);[~, idx] = sort(dist);

% 贪心算法选择医疗点medicals = zeros(1, 3);for i = 1:n if any(medicals == idx(i)) continue; end if sum(medicals == 0) == 3 medicals(1) = idx(i); elseif sum(medicals == 0) == 2 if min(adj(idx(i), medicals(medicals ~= 0))) > 2 * mean(dist) medicals(2) = idx(i); end elseif sum(medicals == 0) == 1 if min(adj(idx(i), medicals(medicals ~= 0))) > 2 * mean(dist) medicals(3) = idx(i); break; end endend

% 计算总距离S1 = sum(min(adj(:, medicals), [], 2))

% 作图figure;gplot(adj, pos{:, 2:3}, '-k');hold on;scatter(pos{medicals(1), 2}, pos{medicals(1), 3}, 100, 'r', 'filled');scatter(pos{medicals(2), 2}, pos{medicals(2), 3}, 100, 'g', 'filled');scatter(pos{medicals(3), 2}, pos{medicals(3), 3}, 100, 'b', 'filled');for i = 1:n [~, idx] = min(adj(i, medicals)); if idx == 1 plot([pos{i, 2}, pos{medicals(1), 2}], [pos{i, 3}, pos{medicals(1), 3}], '-r'); elseif idx == 2 plot([pos{i, 2}, pos{medicals(2), 2}], [pos{i, 3}, pos{medicals(2), 3}], '-g'); else plot([pos{i, 2}, pos{medicals(3), 2}], [pos{i, 3}, pos{medicals(3), 3}], '-b'); endend

% 输出结果medicalsS1

2. 道路维修规划

算法：

排序可选道路： 将所有可选道路按照长度从小到大排序。2. 构建最小生成树： 利用Kruskal算法构建连接所有村庄的最小生成树。3. 选择维修道路： * 遍历所有可选道路，如果该道路不在最小生成树中，且连接的两个村庄之间的最短距离大于预设阈值（例如，所有村庄到最近医疗点的平均距离的2倍），则选择维修该道路。

**Matlab代码：**matlab% 将可选道路按照长度从小到大排序edges = sortrows(connect, 4);

% Kruskal 算法求最小生成树parent = (1:n)';rank = zeros(n, 1);mst = table('Size', [0, 3], 'VariableTypes', {'double', 'double', 'double'}, 'VariableNames', {'Start', 'End', 'Weight'});for i = 1:height(edges) u = edges{i, 2}; v = edges{i, 3}; w = edges{i, 4}; pu = find(parent(u)); pv = find(parent(v)); if pu == pv continue; end if rank(pu) < rank(pv) parent(pu) = pv; elseif rank(pu) > rank(pv) parent(pv) = pu; else parent(pv) = pu; rank(pu) = rank(pu) + 1; end mst = [mst; u, v, w];end

% 选择需要维修的道路dist = sum(adj, 2);S2 = 0;figure;gplot(adj, pos{:, 2:3}, '-k');hold on;for i = 1:height(connect) u = connect{i, 2}; v = connect{i, 3}; if any(mst{:, 1} == u & mst{:, 2} == v) || any(mst{:, 1} == v & mst{:, 2} == u) continue; end if pdist2(pos{u, 2:3}, pos{v, 2:3}) > 2 * mean(dist) plot([pos{u, 2}, pos{v, 2}], [pos{u, 3}, pos{v, 3}], '-r'); S2 = S2 + connect{i, 4}; else plot([pos{u, 2}, pos{v, 2}], [pos{u, 3}, pos{v, 3}], '-k'); endend

% 输出结果S2

结果分析

运行上述Matlab代码，可以得到：

3个医疗点的最佳位置（村庄编号）：23、54、97。* 村民到医疗点的最小总距离：113660米。* 需要维修的道路总里程：13270米。

结论

本文利用最短路径和最小生成树算法，有效解决了山区医疗点选址和道路规划问题。该方案兼顾了村民就医便捷性和道路建设成本，为山区医疗资源优化配置提供了参考依据。