DataStructure_Design

华南理工大学国际校区数据结构课大作业

贡献者（排名不分先后）：

汪子楷：整体cpp项目搭建、策略及可视化

姚炜博：整体python项目搭建、策略及可视化、视频制作

李喆葳：项目报告撰写、可视化、PPT制作

甄理：deprecated/try_2.py，PPT制作

肖翔云： deprecated/try_1.py，强化学习算法

项目简介

本项目为园区自动充电机器人调度模拟。假设你是一个工业园区的管理人员，园区内有一批自动充电机器人，它们可以自行充满电（或携带有电的电池）后，移动到园区任意位置为停在园区内的车辆充电。你的任务是如何安排这些充电机器人以最大化其利用率。

---

基本要求

1. 车辆模拟
   需要模拟车辆到达园区的时间、地点、剩余电量、离开时间、离开时需要的电量，参数可在合理范围内随机生成。

2. 充电速度
   充电速度不固定，电量越多充电速度越慢。

3. 机器人能量管理
   机器人自己缺电时需要回去充电或换电，不能抛锚。

4. 换电管理
   换电需要考虑电池的数量。

5. 调度策略
   至少完成两种不同的调度策略，如最近任务优先、最大任务优先等。

6. 规模模拟
   至少模拟三种以上不同大小规模的问题。

7. 进阶算法（加分项）
   可尝试强化学习、超启发式、元启发式、多智能体等进阶算法求解。

8. 图形界面（加分项）
   图形界面展示可获得额外加分。

---

作业说明

• 小组作业，每组三至五人，编程语言不限，题目二选一。
• 最终成果包括：一个展示视频、一份项目报告和一份源代码。

评分标准（总分120，超过100按100计）

• 完成分（50）：模拟的合理性及功能全面性
• 难度分（40）：环境复杂度、数据结构与算法的合理性
• 主观分（10）：结果展示形式及评分人员主观满意度
• 附加分（20）：额外实现的算法或图形界面

---

项目目录结构

DataStructure_Design/
├── main.py # 主程序入口
├── README.md
├── requirements.txt # 环境依赖
├── environment.yml # 环境依赖
├── config/
│   ├── charging_curve.py # 充电功率验证
│   └── q_table/
│       └── ...（Q表相关文件）
├── deprecated/ # 已废弃
│   ├── try_1.py
│   └── try_2.py
├── docs/
│   └── 大作业要求.txt
├── models/ # 
│   ├── battery_station.py
│   ├── battery.py
│   ├── car.py
│   └── robot.py
├── modules/
│   ├── envs.py
│   ├── qlearning_agent.py
│   ├── strategy.py
│   └── visualization.py
├── optimization_results/ # 运行时产生
│   └── ...（遗传算法训练文件）
├── utils/
│   ├── GeneticTrainer.py # 遗传算法训练
│   ├── RL_test.py
│   ├── run.py # RL训练
│   └── val_multithread.py # 算法对比及可视化
└── video/
    ├── 归档.zip
    ├── cpp_demo.mkv
    └── ...

---

场景介绍

需充电的车

1. 电池架构分为400V和800V两种，两者充电速率不同

2. 电池大小不固定，取市面常规65-115kWh，满足(90, 10)的正态分布

3. 离开时间在40min到100min内随机，满足(60, 10)的正态分布

4. 所需电量在65-100%内随机，满足(80, 10)的正态分布

5. 电池大小不固定，取市面常规65-115kWh，满足TODO分布

6. 到达电量为0-64%，满足(15, 10)的正态分布

充电机器人

• 采用换电模式，电池大小固定，均为800V架构
• 换电时间2min
• 移动速度10m/s
• 自身消耗电量仅由行驶距离决定，百公里20kwh
• 实时监测剩余电量是否足够回站充电

换电站

• 坐标地图中心点
• 最低换电SOC：50%
• 环境update时按充电曲线对需要充电的电池充电

模拟参数

1. 时间步长：0.1-10s可配置

2. 仿真总时长：设置为8小时

3. 规模：

• small：100x100 米方格，4 台机器人，10 辆车，3 块电池，车辆生成概率 0.003056（每小时约 11 辆）
• medium：200x200 米方格，16 台机器人，40 辆车，10 块电池，车辆生成概率 0.011667（每小时约 42 辆）
• large：500x500 米方格，40 台机器人，100 辆车，24 块电池，车辆生成概率 0.029167（每小时约 105 辆）

4. 调度策略 本项目支持多种调度策略，适用于不同规模和复杂度的仿真场景：

• nearest_task（最近任务优先）
  采用匈牙利算法，为所有空闲机器人分配距离最近的“需充电”车辆，实现全局最小化机器人到车辆的总距离。

• max_demand_task（最大需求优先）
  优先为电量缺口最大的车辆分配最近的空闲机器人，提升对高需求车辆的响应速度。

• max_priority_task（最大优先级分配）
  综合考虑车辆的电量缺口和离开时间，优先为高优先级（如电量低且即将离开）的车辆分配最近的空闲机器人。

• genetic_task（遗传算法多目标优化）
  基于遗传算法优化权重，综合考虑紧急度、距离、机器人电量等多目标因素，实现更优的任务分配。

• q_table_task（强化学习分配）
  基于Q-learning等强化学习方法，利用训练好的Q表进行智能分配，动态决策机器人调度方案。

• hyper_heuristic_task（超启发式策略）
  根据当前环境状态（如待充电车辆数量、空闲机器人比例等）动态选择最合适的底层调度策略，实现自适应调度。

用户可在启动界面或配置文件中选择不同的调度策略进行仿真和对比。

运行项目

本项目基于 Python 3.10 版本开发，推荐使用虚拟环境进行依赖管理。

环境配置

1. 一键配置

   conda env create -f environment.yml

运行

1. 主程序

   python main.py

2. 算法对比程序

   python utils/val_multithread.py