211service.com
パッケージをドアに届けるますます複雑なアルゴリズムの内部
氏。技術
50個のパッケージを手渡しする必要がある場合、最適なルートをどのように計画しますか？
これは、数学者やコンピューターサイエンティストが長い間悩んできた理論上の問題であり、巡回セールスマン問題に精通しているかもしれません。簡単に言えば、場所のリストとそれらすべての間の距離を考えると、各場所を一度訪れて原点に戻る最短ルートはどれですか？明らかに、この問題を解決することは、商品を配達するeコマースビジネスにとって魅力的な提案です。これは、燃料費の削減とドライバーの削減を意味するためです。
しかし、問題があります。問題は非常に困難になり、非常に迅速になります。バンクーバーを拠点とするルート最適化スタートアップのCEO、マーク・クオ氏は、1人のドライバーが57ストップに行かなければならない場合、すでに4倍の組み合わせが可能だと説明しています。 ルーティフィック 。これは75個のゼロがあるものです。既存のコンピュータシステムは、考えられるすべてのルートを評価するのに数日または数週間かかります。したがって、企業は完璧を求めるのではなく、ルートを可能な限り改善するための賢明なアプローチを見つける必要があります。
最大の配信プレーヤーは、このトピックについて話すことに熱心ではありません。 UPSもDHLもインタビューの要求に応じませんでした。 FedExは、1週間以上前に通知したとしても、それについて話す時間をスケジュールすることができませんでした。また、Amazonの広報担当者は、同社は、Amazonに代わって配信するためにハイエンドテクノロジーを使用するさまざまな配信サービスプロバイダーと協力しているとだけ言っています。それを超えて、それは共有するものが何もありませんでした。
幸いなことに、一部の小規模な組織はあまりケージがないので、私たちは彼らと話をしました。
現実の世界で配達を最適化することは、いくつかのレベルで巡回セールスマン問題よりも厄介です。まず、場所間の距離を計算する必要があります。Googleマップを使用したことのある人なら誰でも知っているように、旅をする方法は常に複数あります。ウィルソルター、マネージングディレクター パラゴン は、英国のスーパーマーケットの巨人であるテスコのようなクライアントに60か国でルーティングおよびスケジューリングソフトウェアを提供していると、配達計画で使用される経路探索アルゴリズムは、Googleマップアルゴリズムと比較して高度にカスタマイズされていると言います。道路状況を考慮し、1日のさまざまな時間帯に交通流を変化させます。さらに、交差点で右折することによるわずかなメリットも考慮に入れます。
次に、何百もの制約を考慮に入れる必要があります。あなたはあなたのすべての配達に当たる驚くべきルートを計算するかもしれません、しかしあなたはバンの後ろにすべてを収めることができますか？冷凍食品の荷降ろしには、ステープルよりどれくらい時間がかかりますか？燃料を節約するために、最初に重いものを降ろす価値はありますか？
しかし、世界最大のオンラインのみの食料品小売業者であるOcadoの計画および配送システムの責任者であるJames Lohr（未来のロボット食料品店はここにありますを参照）は、そのシステムは特定の地域のバンに配送をランダムに割り当てることから始まると説明しています次に、それらの配達にかかる時間を計算します。次に、2つのドロップオフの順序を切り替えることから、車両間で配達のチャンク全体を切り替えることまで、小さな変更と大きな変更を組み合わせて行います。そのたびに、それが改善であるかどうかを評価します。毎秒400万回の移動を行い、最適なソリューションを追跡しながら、見つけることができる最適なルートにゆっくりと近づきます。
大規模な組織の計画の計算量が多いこととは別に、一部の企業は中小企業を対象としたシステムも開発しています。たとえば、RoutificのKuoは、彼の会社は、ドライバーがスマートフォンを介してアクセスするクラウドベースのサービスを使用してルートプランニングパワーを提供したいと考えていると説明しています。ちょっとショッカーですが、多くのドライバーはまだペンと紙でルートを計画していると彼は言います。彼の会社のアルゴリズムもルートに段階的な変更を加えますが、小さな変更で大きな違いが生じる場合は、改善を最大化するためにそのドロップオフに注意が向けられ、アルゴリズムが次に進みます。 Routificは、そのサービスによって配達ルートの長さが40％短縮されると主張しています。
気付かずにこれらのアルゴリズムをすでに操作している可能性は十分にあります。 Paragon（Ikeaとカタログ小売業者Argosに代わって作業）とOcadoはどちらも、Webサイトで顧客に配信ウィンドウを提供するときに、分析からデータを吸い込みます。今後数日間の現在の計画によく適合するルートのみを提案します。
これは、おそらく常に存在していなかったドライバーへの礼儀です。 Paragon、Ocado、およびRoutificはすべて、経験豊富な配達ドライバーに、アルゴリズムが彼らよりもよく知っていることを納得させることに関して、文化的な問題を経験しています。ある時点で、運転手が昼食を食べた場所に行って、あなたがルートプランナーだと言った場合、あなたは自分の人生を恐れるでしょう、とOcado’sLohrは言います。もちろん、少し誇張していますが、政治的に難しい場合があります。
その間、最適化問題自体にさらに多くの難易度の層が追加され続けており、終わりが見えないように見えます。 Paragon’s Salterは、クライアントが新しい機能の追加を求め続けていると説明しています。二酸化炭素排出量を最小限に抑えるルート。たとえば、お気に入りになっています。毎年、ますます多くの制約を考慮に入れていると彼は言います。計画している[ルート]を真に最適化することは不可能だと思います。