iRB-Lab/py-ga-VRPTW

解决的问题

本项目提供了一个用于求解带时间窗的车辆路径问题（VRPTW）的Python实现。其目标是为一组车辆找到最优的配送路线，确保每个客户都在指定的时间窗内被访问，且不超出车辆的容量限制。

工作原理

该项目使用遗传算法（GA）来演化潜在的路径解决方案。路径被表示为一个“个体”（染色体），由客户序列组成。该过程包括：

• 解码：根据车辆容量和时间约束，将客户序列转换为实际的子路径。
• 评估：基于运输成本、车辆启动成本，以及过早到达（等待成本）或过晚到达（延迟成本）的惩罚来计算解的适应度。
• 选择：使用轮盘赌选择法选择下一代的个体。
• 交叉：应用部分匹配交叉（PMX）将两个父代解的特征组合起来。
• 变异：使用逆序操作随机反转路径的某一段，以保持遗传多样性。

适用人群

本工具适用于对物流工程、运筹学感兴趣的人士，或正在学习遗传算法及其在组合优化问题中应用的学生。

主要特点

• 支持基准测试：支持Solomon的VRPTW基准问题（随机型、聚类型和混合型）。
• 灵活的数据输入：支持文本和JSON格式的问题实例，并提供在两者之间转换的实用工具。
• 可自定义实例：允许用户定义并运行自己的定制化路径数据。
• 详细的GA实现：提供了选择、交叉、变异和适应度评估等核心GA组件的清晰实现。