配送業や卸業のように、複数の目的地に複数の車両で時間通りに荷物を届けたり、回収したりするには、最適なルートと車両編成をする必要があります。
配送ルートの最適化は経路の最適化だけではなく、積載量の問題や車両の数、時間内に届けられるかなど要素が多く単純な計算やツールでは解決が難しい問題として有名でした。
今回はこの問題に対してGCPのRouteOptimizationAPIでアプローチしたので、その過程を共有します。
| No | 車両 | 積載量 | 稼働可能時間 | 最低休憩時間 |
|---|---|---|---|---|
| 1 | A 🚗 | 40 | 9:00-20:00(11時間) | 1時間(11:00-14:00) |
| 2 | B 🚐 | 50 | 11:00-18:00(7時間) | 1時間(11:00-14:00) |
| 3 | C 🚌 | 60 | 10:00-19:00(8時間) | 1時間(11:00-14:00) |
| No | 場所 | 荷物の個数 | 緯度,経度 |
|---|---|---|---|
| 1 | 浅草寺 | 3 | 35.7131015,139.7938395 |
| 2 | 東京スカイツリー | 8 | 35.7100627,139.8081255 |
| 3 | 江戸東京博物館 | 7 | 35.6965972,139.7931587 |
| 4 | サンシャイン水族館 | 9 | 35.7294975,139.7161562 |
| 5 | 上野アメ横商店街 | 8 | 35.7092967,139.7721934 |
| 6 | 三鷹の森ジブリ美術館 | 10 | 35.696238,139.5678568 |
| 7 | サンリオピューロランド | 11 | 35.624512,139.4267181 |
| 8 | 東京国立博物館 | 7 | 35.7188351,139.7739466 |
| 9 | 東京駅 | 3 | 35.6811081,139.764516 |
| 10 | 皇居 | 2 | 35.6834493,139.7465805 |
| 11 | 歌舞伎座 | 4 | 35.6693303,139.7652126 |
| 12 | お台場海浜公園 | 7 | 35.6300488,139.7731163 |
| 13 | イマーシブ・フォート東京 | 12 | 35.6250127,139.7773411 |
| 14 | 豊洲市場 | 4 | 35.6436265,139.7788524 |
| 15 | 羽田空港 | 4 | 35.5476821,139.7581887 |
| 16 | 六本木ヒルズ | 6 | 35.6602205,139.7270445 |
| 17 | 国会議事堂 | 5 | 35.6748919,139.7423358 |
| 18 | MIYASHITA PARK | 13 | 35.6618024,139.6991718 |
| 19 | 明治神宮 | 4 | 35.6727305,139.6892223 |
| 20 | 東急歌舞伎町タワー | 8 | 35.6957513,139.6980145 |
出発地点の東京タワーは赤ピン、目的地は青ピン
<aside> 🗺️
</aside>