iRB-Lab/py-ga-VRPTW

解決的問題

本專案提供一個用於求解時間窗車輛路徑問題（VRPTW）的Python實作。其目標是為一組車輛找到最優的配送路線，確保每位客戶都在指定的時間窗內被造訪，且不超過車輛的容量限制。

工作原理

本專案使用遺傳演算法（GA）來演化潛在的路徑解決方案。路徑被表示為一個「個體」（染色體），由客戶序列組成。該過程包括：

• 解碼：根據車輛容量和時間限制，將客戶序列轉換為實際的子路徑。
• 評估：根據運輸成本、車輛啟動成本，以及過早到達（等待成本）或過晚到達（延遲成本）的懲罰來計算解的適應度。
• 選擇：使用輪盤賭選擇法選擇下一代的個體。
• 交叉：應用部分匹配交叉（PMX）將兩個父代解的特徵組合起來。
• 變異：使用逆序操作隨機反轉路徑的某一段，以保持遺傳多樣性。

適用對象

本工具適用於對物流工程、作業研究感興趣的人士，或正在學習遺傳演算法及其在組合最佳化問題中應用的學生。

主要特色

• 支援基準測試：支援Solomon的VRPTW基準問題（隨機型、聚類型和混合型）。
• 彈性資料輸入：支援文字與JSON格式的問題實例，並提供兩者之間轉換的實用工具。
• 可自訂實例：允許使用者定義並執行自己的客製化路徑資料。
• 詳細的GA實作：提供選擇、交叉、變異和適應度評估等核心GA元件的清晰實作。