iRB-Lab/py-ga-VRPTW

何を解決するか

このプロジェクトは、時間窓付き車両経路問題（VRPTW）を解くためのPython実装を提供します。複数の車両で商品を配達する最適なルートを見つけることを目的としており、各顧客に対して特定の時間窓内に訪問すること、および車両の容量制限を超えないことを保証します。

動作方法

このプロジェクトは、遺伝的アルゴリズム（GA）を使用して、潜在的なルート解を進化させます。ルートは「個体」（染色体）として表現され、顧客の順序列で構成されます。プロセスは以下の通りです：

• デコード：車両の容量と時間制約に基づいて、顧客の順序列を実際のサブルートに変換します。
• 評価：輸送コスト、車両起動コスト、早すぎる到着（待機コスト）や遅すぎる到着（遅延コスト）に対するペナルティに基づいて、解の適応度を計算します。
• 選択：ルーレットホイール選択を使用して、次世代に進む個体を選択します。
• 交叉：部分一致交叉（PMX）を適用して、2つの親解の特徴を組み合わせます。
• 突然変異：逆転操作を使用して、ルートのランダムなセグメントを逆転させ、遺伝的多様性を維持します。

対象ユーザー

物流工学、オペレーションズリサーチに興味がある人、または遺伝的アルゴリズムと組合せ最適化問題への応用を学ぶ学生向けに設計されています。

特徴

• ベンチマーク対応：ソロモンのVRPTWベンチマーク問題（ランダム、クラスタ型、混合型）をサポートしています。
• 柔軟なデータ入力：テキスト形式とJSON形式の問題インスタンスをサポートしており、相互変換用のユーティリティも提供しています。
• カスタムインスタンス対応：ユーザーが独自のルートデータを定義し、アルゴリズムを実行できます。
• 詳細なGA実装：選択、交叉、突然変異、適応度評価といったGAの主要コンポーネントを明確に実装しています。