找到
1
篇与
TSP问题医疗应用案例
相关的结果
-
Python+蚁群算法实战：医院科室智能调度等待时间优化系统开发（附完整开源代码） 本文针对三甲医院多科室体检排队效率痛点，基于生物启发算法提出创新解决方案。通过将7大检查科室建模为动态TSP问题，利用Python构建多线程优先队列仿真系统，结合蚁群算法的信息素动态更新机制，实现科室访问路径智能优化。实验数据显示，该方案较传统随机排队模式减少患者总等待时长22.6%，科室间转移效率提升35%，算法在50次迭代内快速收敛。文中完整公开含多服务台调度、Matplotlib热力图可视化等核心模块的代码实现，为医疗资源优化、智能医院建设提供可直接复用的开源解决方案，特别适合AI医疗、运筹优化等领域的开发者参考学习。 在现代医院门诊流程中，患者往往需要在多个检查科室之间来回奔波，面临长时间的排队等待。以某医院为例，患者通常需要完成7项检查：抽血室（5分钟，2个服务台）、B超室（20分钟）、眼科（5分钟）、内科（10分钟）、外科（15分钟）、心电图（10分钟）和身高体重测量（5分钟）。每位患者平均每2分钟到达医院（即30人/小时），在科室间转移还需额外花费2分钟时间。 这种复杂的排队系统导致患者总等待时间过长，不仅影响就医体验，也降低了医院运营效率。传统的人工调度或随机排队方式难以实现最优的资源配置，因此需要一种智能化的解决方案来优化患者的科室访问顺序，从而显著减少总等待时间。 解决思路 针对这一复杂的排队优化问题，我们采用了受自然界蚂蚁觅食行为启发的蚁群算法。该算法的核心思想是通过模拟蚂蚁群体在寻找食物过程中释放信息素的行为，逐步发现最优的路径选择策略。 具体实施中，我们将每位患者视为一个需要完成所有检查的"旅行者"，各科室则是必须访问的"城市"。算法通过以下机制实现优化： 信息素引导：记录历史优质解决方案中科室间的转移偏好 启发式信息：考虑各科室的平均检查时间（时间越短优先级越高） 概率选择：平衡已知最优路径探索与新路径开发 动态更新：根据解决方案质量调整信息素浓度 系统特别考虑了不同科室服务台数量的差异（如抽血室有2个服务台），使用优先队列（最小堆）精确模拟多服务台排队场景，确保等待时间计算的准确性。 验证方法 为验证算法的有效性，我们设计了科学的对比实验： 基准测试：采用完全随机的科室访问顺序作为对比基准 评价指标：计算所有患者的总等待时间，包括： 在各科室外的排队等待时间 科室间转移的固定时间（2分钟/次） 优化率计算：(随机方案耗时-优化方案耗时)/随机方案耗时×100% 实践代码 由于使用了一些外部库，需要使用下面的命令进行安装： pip install matplotlib seaborn numpy 当然在国内可以使用更快的清华镜像源： pip install matplotlib seaborn numpy -i https://mirrors.tuna.tsinghua.edu.cn/pypi/web/simple以下是完整的代码： import random import heapq import matplotlib.pyplot as plt import seaborn as sns import numpy as np from matplotlib import font_manager # 设置中文字体 try: plt.rcParams['font.sans-serif'] = ['Microsoft YaHei'] # Windows系统常用 plt.rcParams['axes.unicode_minus'] = False except: try: plt.rcParams['font.sans-serif'] = ['SimHei'] # 备选方案 plt.rcParams['axes.unicode_minus'] = False except: print("无法设置中文字体，将使用默认字体") # 科室信息 departments = [ {'name': '抽血室', 'time': 5, 'servers': 2}, {'name': 'B超室', 'time': 20, 'servers': 1}, {'name': '眼科', 'time': 5, 'servers': 1}, {'name': '内科', 'time': 10, 'servers': 1}, {'name': '外科', 'time': 15, 'servers': 1}, {'name': '心电图室', 'time': 10, 'servers': 1}, {'name': '身高体重', 'time': 5, 'servers': 1}, ] dept_names = [dept['name'] for dept in departments] num_departments = len(departments) dept_times = [dept['time'] for dept in departments] eta = [1.0 / dept['time'] for dept in departments] # 启发式信息 # 算法参数 alpha = 1 # 信息素权重 beta = 2 # 启发式信息权重 rho = 0.1 # 信息素蒸发率 Q = 1000.0 # 信息素增强系数 num_ants = 10 # 蚂蚁数量 iterations = 50 # 迭代次数 num_patients = 30 # 患者数量 # 生成到达时间（每2分钟一个患者） arrival_times = [i * 2 for i in range(num_patients)] # 初始化信息素矩阵 tau = [[1.0 for _ in range(num_departments)] for _ in range(num_departments)] def roulette_wheel_selection(probabilities): """轮盘赌选择算法""" r = random.uniform(0, sum(p for _, p in probabilities)) cumulative = 0 for j, p in probabilities: cumulative += p if cumulative >= r: return j return probabilities[-1][0] def generate_path(tau, eta): """生成单个患者的科室访问路径""" path = [] unvisited = set(range(num_departments)) # 随机选择起始科室 current = random.choice(list(unvisited)) path.append(current) unvisited.remove(current) while unvisited: probabilities = [] total = 0.0 for j in unvisited: pheromone = tau[current][j] heuristic = eta[j] prob = (pheromone ** alpha) * (heuristic ** beta) probabilities.append((j, prob)) total += prob if total == 0: # 处理零概率情况 j = random.choice(list(unvisited)) else: probabilities = [(j, p / total) for j, p in probabilities] j = roulette_wheel_selection(probabilities) path.append(j) unvisited.remove(j) current = j return path def evaluate_solution(patients_paths): """评估解决方案的总等待时间""" # 初始化科室服务台（使用最小堆） queues = [] for dept in departments: servers = [0] * dept['servers'] heapq.heapify(servers) queues.append(servers.copy()) total_wait = 0 for pid in range(num_patients): path = patients_paths[pid] arrival = arrival_times[pid] current_time = arrival for i, dept in enumerate(path): # 计算到达时间 if i == 0: dept_arrival = arrival else: dept_arrival = current_time + 2 # 转移时间 # 获取服务台 queue = queues[dept] available_time = heapq.heappop(queue) # 计算等待时间 wait_time = max(0, available_time - dept_arrival) total_wait += wait_time # 更新服务台时间 start_time = max(dept_arrival, available_time) end_time = start_time + departments[dept]['time'] heapq.heappush(queue, end_time) current_time = end_time # 添加转移时间 total_wait += 2 * (len(path) - 1) return total_wait # 运行蚁群算法 best_solution = None best_cost = float('inf') best_costs_history = [] # 记录每次迭代的最佳成本 for iteration in range(iterations): solutions = [] for _ in range(num_ants): # 生成蚂蚁解决方案 paths = [generate_path(tau, eta) for _ in range(num_patients)] cost = evaluate_solution(paths) solutions.append((cost, paths)) # 更新全局最优 if cost < best_cost: best_cost = cost best_solution = paths best_costs_history.append(best_cost) print(f"迭代次数 {iteration + 1}: 当前最优等待时间 {best_cost} 分钟") # 信息素蒸发 for i in range(num_departments): for j in range(num_departments): tau[i][j] *= (1 - rho) # 信息素增强 for cost, paths in solutions: if cost == best_cost: for path in paths: for k in range(len(path) - 1): i = path[k] j = path[k + 1] tau[i][j] += Q / cost # 随机解决方案对比 random_paths = [random.sample(range(num_departments), num_departments) for _ in range(num_patients)] random_cost = evaluate_solution(random_paths) improvement = (random_cost - best_cost) / random_cost * 100 # 1. 优化过程可视化 plt.figure(figsize=(12, 5)) plt.subplot(1, 2, 1) plt.plot(range(1, iterations + 1), best_costs_history, 'b-', linewidth=2) plt.title('蚁群算法优化过程') plt.xlabel('迭代次数') plt.ylabel('总等待时间(分钟)') plt.grid(True) # 标记最优解 optimal_iter = best_costs_history.index(min(best_costs_history)) + 1 optimal_cost = min(best_costs_history) plt.scatter(optimal_iter, optimal_cost, color='red', s=100, label=f'最优解: {optimal_cost} 分钟 (第{optimal_iter}次迭代)') # 添加随机方案参考线 plt.axhline(y=random_cost, color='g', linestyle='--', label=f'随机方案: {random_cost} 分钟') plt.legend() # 2. 科室访问热力图 plt.subplot(1, 2, 2) transfer_matrix = np.zeros((num_departments, num_departments)) for path in best_solution: for k in range(len(path) - 1): i = path[k] j = path[k + 1] transfer_matrix[i][j] += 1 sns.heatmap(transfer_matrix, annot=True, fmt='.0f', cmap='YlOrRd', xticklabels=dept_names, yticklabels=dept_names) plt.title('科室间转移频率热力图') plt.xlabel('目标科室') plt.ylabel('来源科室') plt.tight_layout() plt.show() # 打印最终结果 print("\n===== 最终优化结果 =====") print(f"随机排队总等待时间: {random_cost} 分钟") print(f"优化后总等待时间: {best_cost} 分钟") print(f"优化率: {improvement:.2f}%") if improvement >= 20: print("优化目标达成 (优化率≥20%)") else: print("优化目标未达成")关于代码的一些配置如下。首先是根据题意进行科室信息的配置： 科室信息的配置图片 然后就是算法的基本参数配置： 基本参数配置图片 代码一次运行效果如下： 运行效果图片 热力图图片 通过可视化，可以直观地展示： 算法收敛过程 最优解出现的位置 患者在不同科室间的流动模式 优化前后的对比效果 科室访问热力图的作用： 使用seaborn绘制科室间转移频率的热力图 横纵坐标标注科室名称 颜色深浅表示转移频率高低
