data_structure_project

数据结构小组作业，主要内容为图网络上的新能源物流车队协同调度系统。项目使用图结构生成城市道路网络，并在动态任务、车辆电量/载重限制、充电站排队压力下进行车辆调度与路径规划。

组员分工

• 地图生成：李俊德、葛子轩
• 调度策略：罗祯祥
• 任务信息生产：王浩源

项目亮点

• 使用全连通带权无向图模拟城市道路网络。
• 使用 Dijkstra 最短路径算法进行车辆路径规划，并加入路径缓存提升效率。
• 模拟有限车辆、电量上限、载重上限、动态任务生成、收益评分和超时扣分。
• 考虑充电站排队和负载压力，车辆电量不足时会选择综合路程和等待时间更优的充电站。
• 支持多车协同完成大重量任务。
• 实现两种在线动态调度策略：
  • 最近任务优先 nearest
  • 最大重量优先 max_weight
• 实现一种进阶算法：
  • 遗传算法 genetic，用于任务已知条件下的离线近似全局优化，并与在线策略进行对比。
• 支持小、中、大三种规模的问题模拟。
• 提供图形化调度驾驶舱，展示地图、车辆、任务、充电站负载、收益指标和策略对比结果。
• 已生成 Word 项目报告：新能源物流车队调度项目报告.docx。

运行方式

建议使用 Python 3.11 或以上版本。

安装依赖：

pip install flask

如果需要运行 Graph.py 中的静态 Matplotlib 绘图演示，再安装：

pip install matplotlib

启动 Web 调度驾驶舱：

python app.py

然后在浏览器打开：

http://127.0.0.1:5000

前端功能

驾驶舱界面包含三块区域：

• 左侧：仿真控制、固定随机种子开关、模拟计时器、核心指标和事件日志。
• 中间：地图可视化，显示仓库、充电站、任务点、车辆位置和道路连接。
• 右侧：待处理任务、车辆状态、调度详情折叠面板，以及三种调度方案结果生成按钮。

说明：

• “使用固定随机种子”开启时，同一规模下地图和任务实验可复现。
• 关闭固定随机种子后，重置会生成新的随机地图。
• 页面刷新按“模拟时间 1 秒”进行，而不是现实时间 1 秒；当前仿真加速后约每 0.167 秒刷新一次。

核心文件说明

文件	作用
Graph.py	生成全连通带权无向图，设置仓库、充电站，并维护充电站队列
Vehicle.py	定义车辆电量、载重、行驶耗电和充电时间
Task.py	定义任务对象，记录产生时间、目标节点、坐标、重量、状态和评分
Task_Manager.py	动态生成任务，或按预设任务列表释放任务
Fleet_Controller.py	在线车辆调度核心，包含最短路缓存、任务分配、充电、返仓、评分
simulation_config.py	小、中、大三种规模配置
simulation_core.py	可重置、可启动/暂停/单步推进的仿真引擎
genetic_optimizer.py	遗传算法离线优化器
experiment_runner.py	运行 nearest、max_weight、genetic 三种方案的实验对比
app.py	Flask 后端接口
templates/index.html	Web 调度驾驶舱界面
generate_report.py	生成 Word 项目报告

算法设计

图生成与寻路

地图使用随机节点生成，并通过类似 Prim 的贪心过程保证整张图全连通。之后为每个节点补充若干近邻边，使网络更接近现实道路网。车辆寻路使用 Dijkstra 算法，并使用 ShortestPathCache 缓存起终点路径，减少重复计算。

在线动态调度策略

在线策略只知道当前已经出现的任务：

• 最近任务优先：优先选择当前车辆到目标点距离最短的任务。
• 最大重量优先：优先选择重量最大的任务，并用距离作为次级排序。

当车辆不在仓库时，会先返仓取货；当电量不足以到达目标或安全点时，会寻找充电站补能。

遗传算法离线优化

遗传算法用于“上帝视角”的离线对比：假设某段时间内的任务全部已知，优化任务配送顺序和车辆分配。

• 染色体：任务配送单元顺序 + 每个配送单元的车辆编号。
• 初始种群：随机解 + 按任务出现时间、距离、重量构造的启发式解。
• 选择：锦标赛选择。
• 交叉：任务顺序采用顺序交叉，车辆分配采用均匀交叉。
• 变异：随机交换任务顺序或调整车辆分配。
• 适应度：综合总收益、完成任务数、超时罚分、累计里程和充电等待。

API 接口

接口	方法	说明
/api/map	GET	获取地图节点、边、仓库和充电站
/api/status	GET	获取实时车辆、任务、指标、日志和充电站负载
/api/start	POST	启动仿真，可传入规模、策略、多车协同、固定种子
/api/pause	POST	暂停仿真
/api/reset	POST	按当前配置重置仿真
/api/step	POST	单步推进一个模拟秒
/api/experiments	GET	生成三种规模下 nearest、max_weight、genetic 的实验结果

三种规模

规模	节点数	车辆数	充电站数	仿真时长
小规模	25	8	4	300s
中规模	40	15	6	450s
大规模	70	25	10	600s

项目报告

项目报告文件为：

新能源物流车队调度项目报告.docx

报告内容包括题目要求对照、系统总体设计、数据结构、调度策略、遗传算法、实验结果、前端展示说明和总结。