Timefoldの配車ルート計画デモ

UMEZO

Timefold の配車ルート計画 (Vehicle Routing) デモを使って、最適化とはどういうものかを御覧いただきたいと思います。（ちょっと長いです…すみません）
このTimefoldの配車ルート計画 は、大型家電や家具のように、送達した先で時間を掛けて設置するような配送を想定しています。そのため、配達先での稼働時間が含まれます。


デモのデータ

まず、配達エリアを設定しています。エリアは左上（北東）と右下（南西）の緯度経度を指定し、そのスクエアな領域内に、配送拠点と配達先を作成します。配達拠点と配達先の緯度経度、配達先の名前、配達先で必要とする設置時間、配達希望時間（午前か午後）は、このデモではランダムに作成されます。

デモのオリジナルはフィレンツェ(FIRENZE)ですが、東京にしてみます。
北東を足立区役所 (35.77546944376798, 139.8047508362819)
南西を多摩境駅 (35.603620660477524, 139.3677672250726)
とし、四角で囲まれた範囲を配達地域としています。

（注意　リアルに使いたい時は、配送拠点や配送先を登録したデータを準備して読み込ませます）

距離は道のりではなく、緯度経度から算出する直線距離で算出しています。また、配達先間に掛かる時間は、フィレンツェは時速50km/h で計算されています。 public static final int AVERAGE_SPEED_KMPH = 50; 
これを東京の平均時速 30km/h に修正しています。

訪問先や配送車の数、時間、荷物の容量、積載量などを定義します。
訪問先数: 110
車の数: 6
稼働開始時刻: 7:30
配達先の最小の荷物の容量 1
配達先の最大の荷物の容量 2
車載可能な荷物量の最小値 20
車載可能な荷物量の最大値 40
設置する時間 (10分〜40分、10分刻みでランダム）
午前中の受取 8:00- 12:00
午後の受取 13:00-20:00

デモの制約

デモの制約としては下記の3つとしています。

Hard制約

Hard制約とは、「必ず守って欲しい」という、強制力の強い制約の場合に使います。

vehicleCapacity()
需要の合計が車両の積載量を超える場合、ハードスコアとして「需要の合計 - 車両の積載量」の値を与える

serviceFinishedAfterMaxEndTime()
お客様へのサービス提供の終了時間が稼働時間以外だった場合、ハードスコアとして「オーバーした時間(分)」の値を与える

Soft制約

Soft制約とは、「なるべく守ってね」という、Hardよりも弱い制約です。

minimizeTravelTime()
移動時間が最小となるよう、全ての車両の移動時間の和(秒)を、ソフトスコアとして与える

解の探索

それでは解を探索してみましょう。
Vehicle routing のアプリを立ち上げて、webブラウザでアクセスするとこのような画面が出てきます。

起動直後の画面

（注意　この画面はあくまでもデモ目的で作られています。実際に利用される時は適切なライセンスに基づくミドルウェア等を利用してください！）

地図上にある青縁の薄い青のマークが配達先、赤や緑等のマークが配送拠点です。赤の配送拠点が西調布、緑色の配送地点が練馬区の環状八号線のあたり、黄色の配送拠点が荻窪と阿佐ヶ谷の中間にあることがわかるかと思います。

初期状態ではTotal Driving Time が0時間である通り、まだ計画は作成されていません。右上にある「Solve」という緑のアイコンをクリックすると、計画作成が始まります。

Sloveボタンを押して直ぐに一旦止めてみました。

初期解作成後
初期解作成後のスコア

Scoreに注目してみてください。 -1140 hard / -99588 soft とあります。これは、Hard制約に引っかかったものの合計スコアが1140、Soft制約に引っかかった合計スコアが-99,588ですよ　と言っています。「制約違反している」ので、スコアは「ネガティブスコア」(-) になっています。0に近くなると良いスコアであるということになります。

solution summary と回てある隣の”i” マークをクリックしてみましょう。

スコアの内訳

上から2つ目、vehicleCapacity にて、Vehicle 5 が重量オーバーして-6点が付けられていることが判ります。過積載、絶対ダメ。また、稼働時間内・希望時間内に作業を完了できないものが20ケースあることが判ります。

このツールの良いところは、なぜその計画なのかの理由がわかるところです。AIにも、理由のわかるAIと理由がわからないAIがあります。理由のわからないAIを使うのにはかなりの勇気が要るのではないでしょうか。

By Visit というアイコンをクリックしてみると、こんなグラフが見えます。

配達先別の計画

Flo Liさん宅にお届け・設置するのが14時過ぎからと、希望の午前中からずれてしまっています。

過積載はいけませんし、お届け希望時間を大きく外れるのもよくありません。Solveボタンを押して、もう少し良い解が無いか、探索してみましょう。Timefoldの仕組みとして、制約の種類(Hard / Soft)ごとに1件あたりのスコアの高いものから解消して制約をもっと満たすように探索を続けます。

さらに10分ほど動かした結果がこちらです。

10分後の解

開始して直ぐ止めた時のScoreが--1140 hard / -99588 soft であったことからすると、 -319hard / -40238 soft と、スコアが改善していることが判ります。また、Total driving timeも 11時間11分と、27時間40分から大きく改善されていることが判ります。
しかしながら、Hard制約が解消していません。 Solution summary の隣の “i” ボタンを押してみましょう。

10分最適化後のスコア詳細

Vehicle Capacityの過積載は解消されているようですが、稼働時間・お届け希望時間に届けられていないものが9件、まだ残っていることになります。

By Vehicle ボタンを押してみます。

最適化後の配送車ごとの配送先順序計画

赤の部分が配送希望時間から外れているところで、お昼の時間帯の配送を行うことで全ての配達先に行けていることがわかりますが、何名かの配達員さん、お昼ご飯を食べる時間がありません...

良い解に向けて

ここからさらに探索を進めてもよいのですが、このケースの場合、組み合わせの数（探索領域）は4.712642 × 10^187　通りもあります。総なめするには数億年掛かるかもしれません。従って、下記のようなチャレンジを試みます。

アプリケーションの設定変更

  • 初期解を作成するアルゴリズムの変更

    • より良い入れ替え解を得るには、初期解の品質を向上させる必要があります。アルゴリズムは複数用意されており、どれが最適なのかはやってみないとわかりません。さらにそのアルゴリズムには調整パラメータなどもあります。なので、異なるアルゴリズムやパラメータを持った「シナリオ」を用意し、同時に走らせてどのアルゴリズムが最適かの見極めを行います。

  • 入れ替え解を作成するアルゴリズムの変更

    • 初期解が出たあと、何かと何かを入れ替えすることでより良い解が無いかを探すのですが、ここにも探索アルゴリズムが複数用意されています。初期解の時と同じように、複数のシナリオを同時に走らせて、どのアルゴリズムのどのようなパラメータが良いかの見極めを行います。

  • 探索領域の調整

    • 例えば町田市の配送を行う時は、実は横浜市から行ったほうが効率が良かったりします。（私の実家も町田市ですが、”神奈川県町田市”でも届いたり...笑)　配送地域の区分を変えたりすることで、より良い解になることもあります。

  • 制約の追加・削除

    • 現場のナレッジを制約として入れることで、より現実的な解に近づきます。例えば、配送物が建物の裏口からしか搬入できない場合、裏口に駐車するまでの経路を追加する（もしくは準備時間を取る）等です。ただし、制約が多すぎる場合は適切な解になるまでに時間が掛かる傾向にありますので、繰り返し実行しながら適切に追加・削除します。

    • 当然ですが、データ化されていないものに制約は付けられません。もし投入時にデータとして保有していなければ、データも合わせて投入する必要があります。

  • スコアの付け方の調整

    • 制約違反のスコアの付け方を見直します。制約の強制度に合わせて、Hard, Midium, Soft と３段階にする、より解消したい制約に高いスコアを与える等です。

経営的判断

これ以上配送先が増えると配送しきれなくなりますので、トラックとドライバーを新たに雇用するという判断もあるかと思います。その際には過去の配送先を参考データとしてシミュレーションすることをおすすめします。
リソースを増やすという観点だと、下記の観点が考えられます。

  • 積載量を多いトラックに変える

  • トラックを増車する（ドライバーも）

  • 配送拠点を増やす

積載量の多いトラックに変えるというのも一つの案ですが、このデモの内容からすると、積載量を増やしてもハードウェア制約の解消には結びつかないと思われます。
そこでトラック(とドライバー)を増やしてみましょう。
7台に増やしてみた結果です。
（注意　このデモでは台数が増えるとともに配送拠点も増えています）

1台増車後のスコア

先ほどの配車数6台の時よりもDriving time は4分増加していますが、配送車別のスケジュールを見てみると、

1台増車後（計7台）

時間内のお届けができているだけではなく、なんと全員、時間の長短はあれども、お昼の休憩時間ができています！ブラック企業から脱出できそうですね！

まとめ

計画の最適化は、いきなり100点満点を目指すものではありません。それは諦めてください。「明日は今日よりは人・モノ・環境に優しい計画を立てる」という、日々の改善活動の一環を支援するソリューションとお考えください。

現場のナレッジをロジックとして実装していくことで、より正確でより良い解が導き出せるようになります。現場のナレッジは日々増えていきますので、どんどん頭（知識）を良くしていくことで、今日よりも少しだけ良い計画が、明日は立てられると思います。

いかがでしたでしょうか。
経営側が働き方改革だ！DXだ！と声高々に叫んでも、人間の考えられる物事には限界があります。このようにデータとデータ、ロジックの組み合わせをAIの力を使って解いてみることで、明日使えるAIで新しい未来に向き合いませんか？

いいなと思ったら応援しよう！