(57)【要約】  荷物集荷及び配送のための経路計画の方法、装置、及びシステムは地理的領域における所定の場所と、前記所定の場所を結ぶ所定の経路を表すデータとを受け取ることと、前記所定の経路に沿った前記所定の場所の連続的な近さに基づいて、前記所定の経路における前記単位エリアを決定することと、前記単位エリアが第１の単位エリア及び第２の単位エリアを含み、前記第１の単位エリアにおける全ての場所が前記第２の単位エリアの訪問前に訪問されることとなるように構成されており、訪前記単位エリアのうち少なくとも１つを結ぶ経路を決定する配送パターンを生成することと、配送パターンそれぞれは当該訪問順序に関連する前記単位エリアのうちの少なくとも１つを含み、問する目標場所を含むタスクデータを受け取った場合、前記配送パターン及び目標データを用いて目標経路を決定することと、当該目標経路をモバイル装置へ送信することと、を含む、方法、装置及びシステム。
2021513132.tif 000002
【特許請求の範囲】
【請求項１】
荷物集荷及び配送用の経路計画の装置であって、
命令を記憶するメモリと、
地理的領域内の所定の場所と、当該所定の場所を接続する所定の経路を表すデータを受信する命令、
前記所定の経路に沿った前記所定の場所の連続的な近さに基づいて、前記地理的領域において単位エリアを決定する命令、当該単位エリアは、第１の単位エリアと第２の単位エリアとを含み、
前記単位エリアは、前記第１の単位エリア内の全ての場所が前記第２の単位エリアの場所を訪問する前に訪問されるように構成され、
前記単位エリアのうちの少なくとも１つを接続する経路を決定するための配送パターンを生成する命令、前記配送パターンの各々は、訪問順序に関連付けられた前記単位エリアのうちの少なくとも１つを含み、
訪問する目標場所を含むタスクデータの受信に応じて、配送パターンおよび目標データを使用して目標場所を訪問するための目標経路を決定する命令、
前記目標経路をモバイル装置へ送信する命令、
を実行するように構成された少なくとも１つのプロセッサと、
を備える装置。
【請求項２】
前記所定の経路に沿った前記所定の場所の連続的な近さに基づいて、前記地理的領域内の前記単位エリアを決定する前記命令を実行するように構成された前記少なくとも１つのプロセッサは、
地理的領域における配送場所を受け取る命令、
第１の機械学習モデルを使用して、配送可能な場所の各々について場所ベクトルを決定し、２つの場所ベクトル間の距離は、配送経路に沿った２つの場所ベクトルに対応する２つの場所の連続的な近さを示し、
配送可能な場所の各々について、配送可能な場所の場所ベクトルおよび場所属性を含む特徴ベクトルを決定する命令、及び
特徴ベクトル間の距離に基づいて配送可能な場所をグループ化することによって単位エリアを決定する命令、単位エリアにグループ化された配送可能な場所の特徴ベクトル間の距離は、所定の閾値内である
を実行するようにさらに構成されている
請求項１に記載の装置。
【請求項３】
場所特徴は、地理座標、建物の番号、エリアの名前、道路の名前、または郵便番号のうちの少なくとも１つを含む、
請求項２に記載の装置。
【請求項４】
前記第１の機械学習モデルはニューラルネットワークモデルを含み、前記少なくとも１つのプロセッサは、
所定の場所の各々の場所ベクトルを決定する命令、場所ベクトルの要素が、所定の場所の各々のアドレスの属性を含み、
ニューラルネットワークモデルに現在の場所の場所ベクトルを入力することによって、所定の場所の現在の場所に対する確率値を決定する命令、各確率値は所定の場所の１つに対応し、所定の場所の１つが現在の場所の直後に訪問される確率を示し、
所定の経路に沿った現在の場所の直後の次の場所が最高確率値に対応するかどうかを決定する命令、
次の場所が最高確率値に対応しないという決定に基づいてニューラルネットワークモデルのパラメータを更新する命令、及び
次の場所が最高確率値に対応するという決定に基づいてニューラルネットワークモデルに、次の場所の場所ベクトルを入力することによって、次の場所の確率値を決定する命令、
を実行するようにさらに構成されている
請求項２に記載の装置。
【請求項５】
前記少なくとも１つのプロセッサは、
所定の経路に沿った所定の場所の各々に続く場所が、所定の場所の各々に対するニューラルネットワークモデルによって決定された確率値の中の最高確率値に対応するという決定に基づいて、配送可能な場所の各々に対する場所ベクトルを決定するためのニューラルネットワークモデルを決定する命令を実行するようにさらに構成されている
請求項４に記載の装置。
【請求項６】
前記少なくとも１つのプロセッサは、
前記単位エリアの各々について、単位エリア内の場所のアドレスにグラフ埋め込み技法を適用することによって、単位エリアのベクトル表現を決定する命令、
所定の場所をカバーする単位エリアに対して訓練配送パターンを決定する命令、各々の訓練配送パターンは訪問順序で順序付けられた単位エリアのうちの少なくとも１つを含み、
訓練配送パターン内の単位エリアの少なくとも１つのベクトル表現を追加することによって、各々の訓練配送パターンのベクトル表現を決定する命令、
当該訓練配送パターンそれぞれのベクトル表現を第２の機械学習モデルに入力することによって、当該訓練配送パターンそれぞれのスコアを決定する命令、当該スコアは、訪問順序に沿って単位エリアのうちの少なくとも１つを訪問するための効率水準を示し、
訪問シーケンスが所定の経路と一致しないという決定に基づいて第２の機械学習モデルのパラメータを更新する命令、及び
すべての訓練配送パターンの訪問シーケンスが所定の経路と一致するという決定に基づいて配送パターンを生成するための第２の機械学習モデルを決定する命令、
を実行するようにさらに構成されている
請求項１に記載の装置。
【請求項７】
前記第２の機械学習モデルはニューラルネットワークモデルを含み、前記配送パターンを生成するように構成された前記少なくとも１つのプロセッサは、
単位エリアを使用して候補配送パターンを決定する命令、それぞれの候補配送パターンは訪問順序で順序付けられた単位エリアのうちの少なくとも１つを含み、
候補配送パターン内の少なくとも１つの単位エリアのベクトル表現を追加することによって、候補配送パターンそれぞれのベクトル表現を決定する命令、
当該候補配送パターンそれぞれのベクトル表現を第２の機械学習モデルに入力することにより、当該候補配送パターンそれぞれのスコアを決定する命令、及び
所定のしきい値よりも高いスコアを有する候補配送パターンとして配送パターンを生成する命令、
を実行するようにさらに構成されている
請求項６に記載の装置。
【請求項８】
前記少なくとも１つのプロセッサは、
訪問目標場所を含むタスクデータを受信する命令、
目標単位エリアを、目標場所をカバーする単位エリアとして決定する命令、及び
目標単位エリアをリンクする目標経路を決定する命令、
を実行するようにさらに構成されており、
当該目標単位エリアそれぞれは、目標経路に沿って１回訪問される
請求項１に記載の装置。
【請求項９】
前記第２の機械学習モデルはニューラルネットワークモデルを含み、前記目標単位エリアをリンクする前記目標経路を決定するように構成された前記少なくとも１つのプロセッサは、
目標単位エリアを結ぶ実現可能な配送パターンの少なくとも１つの集合を決定する命令、
目標単位エリアの全てを訪れるのに最短の時刻を有する実現可能な配送パターンとして目標経路を決定する命令
を実行するようにさらに構成されている
請求項８に記載の装置。
【請求項１０】
荷物集荷及び配送用の経路計画のコンピュータ実装方法であって、
地理的領域内の所定の場所と、当該所定の場所を接続する所定の経路を表すデータを受信するステップと、
少なくとも１つのプロセッサを使用して、前記所定の経路に沿った前記所定の場所の連続的な近さに基づいて、地理的領域内の単位エリアを決定するステップであって、当該単位エリアは第１の単位エリアおよび第２の単位エリアを含み、当該単位エリアは、第１の単位エリア内のすべての場所が第２の単位エリアの訪問場所より前に訪問されるように構成されるステップと、
前記少なくとも１つのプロセッサを用いて、前記単位エリアのうちの少なくとも１つを接続する経路を決定するための配送パターンを生成するステップであって、前記配送パターンそれぞれは、訪問順序に関連付けられた前記単位エリアのうちの少なくとも１つを含むステップと、
訪問する目標場所を含むタスクデータの受信に応じて、配送パターンおよび目標データを使用して目標場所を訪問するための目標経路を決定するステップと、
前記目標経路をモバイル装置へ送信するステップと、
を含むコンピュータ実装方法。
【請求項１１】
前記所定の経路に沿った前記所定の場所の連続的な近さに基づいて、前記地理的領域内の前記単位エリアを決定するコンピュータ実装方法であって、
地理的領域における配送可能な場所を受け取るステップと、
第１の機械学習モデルを使用して、配送可能な場所の各々について場所ベクトルを決定するステップであって、２つの場所ベクトル間の距離は、配送経路に沿った２つの場所ベクトルに対応する２つの場所の連続的な近さを示すステップと、
配送可能な場所の各々について、配送可能な場所の場所ベクトルおよび場所属性を含む特徴ベクトルを決定するステップと、
特徴ベクトル間の距離に基づいて配送可能な場所をグループ化することによって単位エリアを決定するステップであって、単位エリアにグループ化された配送可能な場所の特徴ベクトル間の距離は、所定の閾値内であるステップと、
を含む請求項１０に記載のコンピュータ実装方法。
【請求項１２】
場所特徴は、地理座標、建物の番号、エリアの名前、道路の名前、または郵便番号のうちの少なくとも１つを含む、
請求項１１に記載のコンピュータ実装方法。
【請求項１３】
前記第１の機械学習モデルはニューラルネットワークモデルを含むコンピュータ実装方法であって、当該方法はさらに、
所定の場所の各々に対して場所ベクトルを決定するステップであって、場所ベクトルの要素が、所定の場所の各々のアドレスの属性を含むステップと、
ニューラルネットワークモデルに現在の場所の場所ベクトルを入力することによって、所定の場所の現在の場所に対する確率値を決定するステップであって、確率値それぞれは当該所定の場所のうちの１つに対応し、当該所定の場所のうちの１つが現在の場所の直後に訪問される確率を示すステップと、
所定の経路に沿った現在の場所の直後の次の場所が最高確率値に対応するかどうかを決定するステップと、
次の場所が最高確率値に対応しないという決定に基づいてニューラルネットワークモデルのパラメータを更新するステップと、
次の場所が最高確率値に対応するという決定に基づいて、次の場所の場所ベクトルをニューラルネットワークモデルに入力することによって、次の場所の確率値を決定するステップと、
を含む請求項１１に記載のコンピュータ実装方法。
【請求項１４】
所定の経路に沿った所定の場所の各々に続く場所が、所定の場所の各々についてニューラルネットワークモデルによって決定された確率値の中で最高確率値に対応するという決定に基づいて、配送可能な場所の各々について場所ベクトルを決定するためのニューラルネットワークモデルを決定するステップをさらに含む
請求項１３に記載のコンピュータ実装方法。
【請求項１５】
単位エリアの各々について、単位エリア内の場所のアドレスにグラフ埋め込み技法を適用することによって、単位エリアのベクトル表現を決定するステップと、
所定の場所をカバーする単位エリアのための訓練配送パターンを決定するステップであって、各々の訓練配送パターンは、訪問順序で順序付けられた単位エリアのうちの少なくとも１つを含むステップと、
訓練配送パターン内の少なくとも１つの単位エリアのベクトル表現を追加することによって、訓練配送パターンそれぞれのベクトル表現を決定するステップと、
当該訓練配送パターンそれぞれのベクトル表現を第２の機械学習モデルに入力することによって訓練配送パターンそれぞれのスコアを決定するステップであって、当該スコアは、前記訪問順序に沿って前記単位エリアのうちの少なくとも１つを訪問するための効率水準を示すステップと、
訪問順序が所定の経路と一致しないという決定に基づいて第２の機械学習モデルのパラメータを更新するステップと、
訓練配送パターンのすべての訪問順序が所定の経路と一致するという決定に基づいて配送パターンを生成するための第２の機械学習モデルを決定するステップと、
をさらに含む請求項１０に記載のコンピュータ実装方法。
【請求項１６】
訓練配送パターンそれぞれは、多くとも３つの単位エリアを含む
請求項１５に記載のコンピュータ実装方法。
【請求項１７】
前記第２の機械学習モデルはニューラルネットワークモデルを含み、前記配送パターンを生成するコンピュータ実装方法であって、
前記単位エリアを用いて候補配送パターンを決定するステップであって、それぞれの候補配送パターンは、訪問順に順序付けられた前記単位エリアのうちの少なくとも１つを含むステップと、
候補配送パターン内の少なくとも１つの単位エリアのベクトル表現を追加することによって、候補配送パターンそれぞれのベクトル表現を決定するステップと、
当該候補配送パターンそれぞれのベクトル表現を第２の機械学習モデルに入力することによって、当該候補配送パターンそれぞれのスコアを決定するステップと、
所定のしきい値よりも高いスコアを有する候補配送パターンとして配送パターンを生成するステップと、
を含む請求項１５に記載のコンピュータ実装方法。
【請求項１８】
訪問する目標場所を含むタスクデータを受け取るステップと、
目標単位エリアを、目標場所をカバーする単位エリアとして決定するステップと、
目標単位エリアをリンクする目標経路を決定するステップと、
をさらに含み、
目標単位エリアそれぞれは、目標経路に沿って１回訪問される
請求項１１に記載のコンピュータ実装方法。
【請求項１９】
前記目標単位エリアをリンクする前記目標経路を決定するコンピュータ実装方法であって、
目標単位エリアを結ぶ実現可能な配送パターンのうち少なくとも１つの集合を決定するステップと、
目標単位エリアのすべてを訪れるのに最短の時間を有する実現可能な配送パターンとして目標経路を決定するステップと、
を含む請求項１８に記載のコンピュータ実装方法。
【請求項２０】
少なくとも１つのモバイル装置と経路計画コンピュータシステムとを備える、荷物集荷および配送用の経路計画のシステムであって、
前記少なくとも１つのモバイル装置は、
命令を記憶するメモリと、
モバイル装置の場所を示す場所データを決定する命令、
場所データを前記経路計画コンピュータシステムへ送信する命令、
を実行するように構成された少なくとも１つのプロセッサと、
を備え、
経路計画コンピュータシステムは、ネットワークを使用して少なくとも１つのモバイル装置に接続されており、
命令を記憶するメモリと、
少なくとも１つのモバイル装置から場所データを受け取る命令、
場所データから、地理領域内のテンプレートの場所と、テンプレートの場所を接続するテンプレート経路を表すデータを選択する命令、
テンプレート経路に沿ったテンプレート場所の連続的な近さに基づいて地理的領域内の単位エリアを決定する命令、当該単位エリアは第１の単位エリアおよび第２の単位エリアを含み、当該単位エリアは、第１の単位エリア内のすべての場所が第２の単位エリアの場所を訪れる前に訪れるように構成されており、
前記単位エリアのうちの少なくとも１つを接続する経路を決定するための配送パターンを生成する命令、前記配送パターンそれぞれは、訪問順序に関連付けられた前記単位エリアのうちの少なくとも１つを含み、
少なくとも１つのモバイル装置から、訪問する目標場所を含むタスクデータを受け取る命令、
配送パターンおよび目標データを使用して目標場所を訪問するための目標経路を決定する命令、及び
前記目標経路を少なくとも１つのモバイル装置へ送信する命令、
を実行するように構成された少なくとも１つのプロセッサと、
を備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して、集荷および配送のための効率的な経路計画のためのコンピュータ化されたシステムおよび方法に関する。具体的には、本開示の実施形態が、迅速なＥコマース注文フルフィルメント用の効率的な経路計画に関する、独創的な非従来型システムに関する。
【背景技術】
【０００２】
オンラインショッピングは最近人気がある。電子商取引（または「Ｅコマース」）業者は注文が発注されてから購入者に配送される注文の荷物までの時間を最小限に抑えることによって、ユーザ体験を改善しようと努力する。フルフィルメントプロセスの１つの時間のかかる部分は「ラストマイル配送」（輸送拠点から最終目的地までの配送）である。人口密度の高い都市部では、ラストマイル配送は配送需要が高く、人件費が高く、約束配送期間が厳しく、交通規制が複雑で、道路状況が急速に変化するため、とりわけ難しい場合がある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
都市部における配送経路計画のための従来の方法は、典型的にはトラックドライバーのような経験豊富な配送作業員に依存する。運転者は効率的な経路を発見するために、３〜５年間同じ経路を運転しなければならない場合がある。経路計画のための従来のバックエンド・コンピュータシステムは、経路計画におけるそのような経験を内部化するには不十分な能力しか有していない。また、そのような発見された経路は一般に「柔軟性がない」ものであり、すなわち、従来のバックエンドシステムは、変化する配送状態に応じてそれらを調整することが難しく、ロードバランス問題につながる可能性がある。例えば、発見された経路のいくつかの目的地がいつかの日に異常に高い需要を有する場合、その経路の運転手は過負荷になることがあり、他の経路の運転手は十分に利用されないことがある。しかしながら、従来のバックエンドシステムは、この問題を処理するためにドライバの割り当てを適応的に再配置する際に最適化することができない。
【０００４】
配送経路計画における別の課題は修復、すなわち、空間利用を最適化するために搬送車において荷物を分類することである。通常、宛先を訪れる順序は、復元に影響を及ぼす。例えば、配送または集荷のための荷物は、それらを記憶する逆順でドロップオフされる。それは、それらの場所および配置を調整することが困難である。復旧問題は、従来のバックエンドシステムが適応性で扱いにくい配送経路計画問題と相関がある。
【０００５】
いくつかの配送経路計画方法は巡回セールスマン問題（ＴＳＰ）として問題を扱い、それに対する近似解を求めることを試みる。ＴＳＰを解決する目的は、配送作業員（「巡回セールスマン」と同様）がすべての目的地を訪れるまでの期間を最小限に抑えることである。しかしながら、従来のバックエンドシステムは、右折が左折よりも容易であること、駐車スポットの駐車困難レベル、近隣の運転アクセシビリティ、Ｕターンのための運転時間等のような、ＴＳＰソリューションへの荷物配送又は集荷におけるいくつかのタスク特性又は状態を要因とするように最適化されていない。
【０００６】
したがって、電子商取引の実行のための効率的で動的な経路計画が必要とされている。
【課題を解決するための手段】
【０００７】
本発明の一態様は、荷物集荷および配送用の経路計画のコンピュータ実装方法を対象とする。このコンピュータ実装方法は少なくとも１つのプロセッサを介して、地理的領域内の所定の場所と、当該所定の場所を接続する所定の経路を表すデータとを受け取るステップと、少なくとも１つのプロセッサを使用して、所定の経路に沿った所定の場所の連続的な近さに基づいて、地理的領域内の単位エリアを決定するステップであって、単位エリアは第１の単位エリアおよび第２の単位エリアを含み、単位エリアは第１の単位エリア内のすべての場所が第２の単位エリアの訪問前に訪問されるように構成されるステップと、少なくとも１つのプロセッサを使用して、単位エリアのうちの少なくとも１つを接続する経路を決定するための配送パターンを生成するステップであって、配送パターンそれぞれが訪問順序に関連する単位エリアのうちの少なくとも１つを含むステップと、訪問する目標場所を含むタスクデータを受信することに応じて、配送パターンおよび目標データを使用して目標場所を訪問するための目標経路を決定するステップと、目標経路をモバイル装置へ送信するステップとを含む。
【０００８】
本発明の別の態様は、荷物の集荷および配送のための経路計画の装置を対象とする。この装置は、メモリと、少なくとも１つのプロセッサとを含む。メモリは命令を記憶し、少なくとも１つのプロセッサは、地理的領域内の所定の場所と、当該所定の場所を接続する所定の経路を表すデータとを受信し、所定の経路に沿った所定の場所の連続的な近さに基づいて地理的領域内の単位エリアを決定し、単位エリアは第１の単位エリア内のすべての場所が第２の単位エリアの訪問場所の前に訪問されるように構成され、単位エリアのうちの少なくとも１つを接続する経路を決定するための配送パターンを生成し、配送パターンそれぞれは訪問シーケンスに関連付けられた単位エリアのうちの少なくとも１つを含み、訪問する目標場所を含むタスクデータを受信することに応じて、配送パターンおよび目標データを使用して目標場所を訪問するための目標経路を決定し、目標経路をモバイル装置へ送信する命令を実行するように構成されている。
【０００９】
本発明のさらに別の態様は、集荷および配送のための経路計画のシステムに関する。このシステムは少なくとも１つのモバイル装置と、ネットワークを使用して前記少なくとも１つのモバイル装置に接続された経路計画コンピュータシステムとを含み、前記少なくとも１つのモバイル装置は命令を記憶するメモリと、前記モバイル装置の場所を示す場所データを決定し、前記場所データを前記経路計画コンピュータシステムへ送信する命令を実行するように構成された少なくとも１つのプロセッサと、を含む。前記経路計画コンピュータシステムは命令を記憶するメモリと、前記少なくとも１つのモバイル装置から、前記場所データを受け取る命令、当該場所データから、地理的領域内のテンプレート場所、および前記テンプレート場所を接続するテンプレート経路を表すデータを選択する命令、前記テンプレート経路に沿った前記テンプレート場所の連続した近さに基づいて当該地理的領域内の単位エリアを決定する命令、当該単位エリアは第１の単位エリアと第２の単位エリアとを含み、当該単位エリアは当該第２の単位エリアの訪問場所の前に当該第１の単位エリア内のすべての場所が訪問されるように構成されており、当該単位エリアのうちの少なくとも１つを決定するための配送パターンを生成する命令、配送パターンそれぞれは訪問シーケンスに関連する当該単位エリアのうちの少なくとも１つを含み、訪問する目標場所を含むタスクデータを少なくとも１つのモバイル装置から受け取る命令、当該配送パターンおよび当該目標データを使用して目標場所を訪問する用の目標経路を決定する命令、当該目標経路を当該少なくとも一つのモバイル装置のうちの一つへ送信する命令、を実行するように構成された少なくとも１つのプロセッサと、を備える。
【００１０】
他のシステム、方法、およびコンピュータ可読媒体も、本明細書で説明される。
【図面の簡単な説明】
【００１１】
【図１Ａ】図１Ａは、開示された実施形態と一致する、出荷、輸送、および物流オペレーションを可能にする通信のためのコンピュータ化されたシステムを備えるネットワークの例示的な実施形態を示す概略ブロック図である。
【図１Ｂ】図１Ｂは、サンプル検索結果を示す： 開示された実施形態と矛盾しない、インタラクティブなユーザインタフェース要素と共に、検索要求を満たす１つ以上の検索結果を含むページ（ＳＲＰ）を示す。
【図１Ｃ】図１Ｃは、開示された実施形態と一致する、対話型ユーザインターフェース要素と共に製品および製品に関する情報を含む例示的な単一ディスプレイページ（ＳＤＰ）を示す。
【図１Ｄ】図１Ｄは、開示された実施形態と一致する、対話型ユーザインターフェース要素と共に仮想ショッピングカート内のアイテムを含むサンプルカートページを示す。
【図１Ｅ】図１Ｅは開示された実施形態に一致する、仮想ショッピングカートからのアイテムを、購入および出荷に関する情報とともに、対話型ユーザインターフェース要素とともに含むサンプル注文ページを示す。
【図２】図２は、開示された実施形態と一致する、開示されたコンピュータ化されたシステムを利用するように構成された例示的なフルフィルメントセンタの概略図である。
【図３】図３は、開示された実施形態に一致する、集荷および配送のための経路計画の例示的な系の概略図である。
【図４】図４は、開示された実施形態に一致する、集荷および配送のための経路計画の例示的な処理の流れ図である。
【図５】図５は、開示された実施形態に一致する、例示的な単位エリアおよび例示的な配送模様を示す図である。
【図６】図６は、開示された実施形態と一致する、経路生成のための機械学習モデルを訓練する例示的プロセスのフローチャートである。
【図７】図７は、開示された実施形態に一致する、荷物集荷および配送のための経路生成の例示的な処理の流れ図である。
【発明を実施するための形態】
【００１２】
以下の詳細な説明は、添付の図面を参照する。可能な限り、図面および以下の説明では、同一または類似の部分を参照するために、同一の参照番号が使用される。いくつかの例示的な実施形態が本明細書に記載されているが、修正、適応、および他の実施形態が可能である。例えば、置換、追加、または修正が図面に示された構成要素およびステップに行われてもよく、本明細書に記載された例示的な方法は、開示された方法にステップを置換、並べ替え、除去、または追加することによって修正されてもよい。したがって、以下の詳細な説明は、開示された実施形態および実施例に限定されない。むしろ、本発明の適切な範囲は、添付の特許請求の範囲によって定義される。
【００１３】
本開示の実施形態は、効率的な経路計画のために構成されたシステム、装置、および方法を対象とする。本明細書で開示される実施形態によれば、システムは候補経路と候補経路に関連付けられた候補作業員との組み合わせを決定するためのヒューリスティック方法（または簡潔にするために「ヒューリスティック」）を生成するために、地理的領域内の経験配送作業員によって発見された効率的な経路を機械学習技法の入力として使用することができる。幾つかの実施例では機械学習技術が地理的領域を配送のための多数の単位エリアに分割することができ、これは発見的方法を生成するためのグラフ埋め込み方法のためのユニットとして使用され得る。
【００１４】
本明細書に開示される実施形態によれば、システムはタスクの組み合わせを生成するために、ヒューリスティックに対するいくつかの利用可能な配送作業員およびいくつかの宛先場所を含む配送タスクデータを受信することができる。いくつかの実施形態では、利用可能な作業員が装置によって集荷されたそれらの動作状態データによって決定されてもよい。いくつかの実施形態では、ヒューリスティックが候補経路にサブ経路を追加または削除することによって、または異なる複雑さの候補経路をそれぞれのタスク組合せにおける異なる分類の候補作業員に関連付けることによってなど、ロード不均衡を低減するタスク組合せを生成することができる。いくつかの実施形態では、ヒューリスティックが候補経路に沿った宛先場所の順序を決定することなどによって、復元問題も共緩和するタスク組合せを生成することができる。
【００１５】
いくつかの実施形態では、システムが改良または最適化技法を使用して、対象作業員および目標経路を含む対象組合せを決定することができる。標的作業員は、標的組合せのための候補作業員から選択される。目標経路は、目標組合せの候補経路から選択される。タスクの組合せごとに、候補タスク持続時間は、候補作業員が目標経路の場所を訪れて配送および／または集荷タスクを完了するために推定される持続時間として決定することができる。最適化技法の結果として、対象タスク組合せに関連するタスク持続時間は、すべての候補タスク組合せの候補タスク持続時間の中で最も短いものとすることができる。言い換えれば、対象タスクの組み合わせは、トラベリングセールスマン問題（ＴＳＰ）に対するヒューリスティック解であってもよい。発見的解は経験的配送作業員により発見された能率経路を用いて発見的手法を生成することにより、タスク特性に要因を与えることができる。
【００１６】
図１Ａを参照すると、出荷、輸送、および物流動作を可能にする通信のためのコンピュータ化されたシステムを含むシステムの例示的な実施形態を示す概略ブロック図１００が示されている。図１Ａに示すように、システム１００は様々なシステムを含むことができ、その各々は、１つまたは複数のネットワークを介して互いに接続することができる。システムはまた、例えばケーブルを使用して、直接接続を介して互いに接続されてもよい。図示のシステムは、出荷権限技術（ＳＡＴ）システム１０１、外部フロントエンドシステム１０３、内部フロントエンドシステム１０５、輸送システム１０７、モバイルデバイス１０７Ａ、１０７Ｂ、１０７Ｃ、売り手ポータル１０９、出荷および注文追跡（ＳＯＴ）システム１１１、フルフィルメント(履行)最適化（ＦＯ）システム１１３、フルフィルメントメッセージングゲートウェイ（ＦＭＧ）１１５、サプライチェーン管理（ＳＣＭ）システム１１７、労働力管理システム１１９、モバイルデバイス１１９Ａ、１１９Ｂ、１１９Ｃ（フルフィルメントセンタ（ＦＣ）２００の内部にあるものとして図示）、第三者フルフィルメントシステム１２１Ａ、１２１Ｂ、１２１Ｃ、フルフィルメントセンタ認証システム（ＦＣ認証）１２３、労働管理システム（ＬＭＳ）１２５を含む。
【００１７】
ＳＡＴシステム１０１は、いくつかの実施形態では注文ステータスおよび配送ステータスを監視するコンピュータシステムとして実装されてもよい。例えば、ＳＡＴ装置１０１は注文がその約束配送日（ＰＤＤ）を過ぎているかどうかを決定し、新しい注文を開始すること、配送されていない注文の品目を再出荷すること、配送されていない注文をキャンセルすること、注文するカスタマとのコンタクトを開始することなどを含む、適切な行動をとることができる。ＳＡＴ装置１０１は、（特定の期間中に出荷された荷物の数などの）出力及び（出荷に使用するために受け取った空のボール紙箱の数などの）入力を含む他のデータを監視することもできる。また、ＳＡＴシステム１０１はシステム１００内の異なるデバイス間のゲートウェイとして機能し、外部フロントエンドシステム１０３およびＦＯシステム１１３などのデバイス間の通信（例えば、ストアアンドフォワードまたは他の技術を使用する）を可能にしてもよい。
【００１８】
いくつかの実施形態では、外部フロントエンドシステム１０３が外部ユーザがシステム１００内の１つまたは複数のシステムと対話することを可能にするコンピュータシステムとして実装することができる。例えば、システム１００がシステムの提示によってユーザがアイテムの注文を行うことができるようにする実施形態では、外部フロントエンドシステム１０３が検索リクエストを受信し、アイテムページを提示し、決済情報を要請するウェブサーバとして実装されてもよい。例えば、外部フロントエンドシステム１０３は、アパッチＨＴＴＰサーバー、マイクロソフトインターネットインフォメーションサービス、ＮＧＩＮＸ等のソフトウェアを実行するコンピュータ又はコンピュータとして実施することができる。他の実施形態では、外部フロントエンドシステム１０３が外部デバイス（例えば、モバイルデバイス１０２Ａまたはコンピュータ１０２Ｂ）からの要求を受信および処理し、それらの要求に基づいてデータベースおよび他のデータストアから情報を取得し、取得した情報に基づいて受信した要求に対する応答を提供するように設計されたカスタムウェブサーバソフトウェアを実行することができる。
【００１９】
いくつかの実施形態では、外部フロントエンドシステム１０３がウェブキャッシングシステム、データベース、検索システム、または支払いシステムのうちの１つまたは複数を含むことができる。一態様では外部フロントエンドシステム１０３がこれらのシステムのうちの１つまたは複数を備えることができ、別の態様では外部フロントエンドシステム１０３がこれらのシステムのうちの１つまたは複数に接続されたインターフェース（例えば、サーバ間、データベース間、または他のネットワーク接続）を備えることができる。
【００２０】
図１Ｂ、図１Ｃ、図１Ｄ、および図１Ｅによって示されるステップの例示的な組は、外部フロントエンドシステム１０３のいくつかの動作を説明するのに役立つ。外部フロントエンドシステム１０３は提示および／またはディスプレイのために、システム１００内のシステムまたはデバイスから情報を受信することができる。例えば、外部フロントエンドシステム１０３は、検索結果を含む１つ以上のウェブページをホスティングまたは提供することができる： ページ(ＳＲＰ)(例えば、図１Ｂ）、単一詳細ページ(ＳＤＰ)(例えば、図１Ｃ）、カードページ（例えば、図１Ｄ）、または注文ページ（例えば、図１Ｅ）。ユーザデバイス（例えば、モバイルデバイス１０２Ａまたはコンピュータ１０２Ｂを使用する）は外部フロントエンドシステム１０３にナビゲートし、サーチボックスに入力することによってサーチをリクエストすることができる。外部フロントエンドシステム１０３は、システム１００内の１つまたは複数のシステムからリクエストすることができる。例えば、外部フロントエンドシステム１０３は、検索要求を満たす情報をＦＯシステム１１３に要求してもよい。また、外部フロントエンドシステム１０３は検索結果に含まれる商品ごとに、約束配送日または「ＰＤＤ」を（ＦＯシステム１１３から）リクエストし、受信することもできる。ＰＤＤは、いくつかの実施形態では、製品を含む荷物がいつユーザの所望の場所に到着するかの推定値、または、特定の期間内、例えば、その日の最後（午後１１時５９分）までに注文された場合、製品がユーザの所望の場所に配送されることを約束される日付の推定値を表すことができる（ＰＤＤはＦＯシステム１１３に関して以下でさらに説明される）。
【００２１】
外部フロントエンドシステム１０３がその情報に基づいてＳＲＰ(例えば、図１Ｂ）を準備することができる。ＳＲＰは、検索要求を満たす情報を含むことができる。例えば、これは、検索要求を満たす製品の写真を含むことができる。ＳＲＰはまた、各製品についてのそれぞれの価格、または各製品についての強化された配送オプション、ＰＤＤ、重み、規模、オファー、割引などに関する情報を含んでもよい。外部フロントエンドシステム１０３は（例えば、ネットワークを介して）要求側ユーザデバイスにＳＲＰを送信することができる。
【００２２】
次いで、ユーザデバイスは例えば、ユーザインターフェースをクリックまたはタップすることによって、または別の入力デバイスを使用して、ＳＲＰ上で表される製品を選択することによって、ＳＲＰから製品を選択することができる。ユーザデバイスは選択された商品に関するリクエストを作成し、それを外部フロントエンドシステム１０３に送ることができる。これに応じて、外部フロントエンドシステム１０３は、選択された商品に関する情報をリクエストすることができる。例えば、情報は、それぞれのＳＲＰ上の製品について提示される情報を超える追加の情報を含むことができる。これは、例えば、貯蔵寿命、原産国、体重、大きさ、荷物中の品目の個数、取扱説明書、または生成物に関する他の事項を含むことができる。また、情報は（例えば、この製品および少なくとも１つの他の製品を購入した顧客のビッグデータおよび／または機械学習分析に基づく）類似の製品に対する推奨、頻繁に質問される質問に対する回答、顧客からのレビュー、製造業者情報、写真などを含むことができる。
【００２３】
外部フロントエンドシステム１０３は受信したプロダクトインフォメーションに基づいて、ＳＤＰ(単一ディテールページ）（例えば、図１Ｃ）を準備することができる。ＳＤＰは、「今すぐ買う」ボタン、「カードに追加する」ボタン、数量フィールド、アイテムの写真などの他の対話型要素も含むことができる。ＳＤＰは、製品を提供する売り手のリストをさらに含むことができる。リストは各売り手が提供する価格に基づいて注文されてもよく、その結果、最低価格で製品を販売することを提案する売り手は最上位にリストされてもよい。リストは最高ランクの売り手が最上位にリストされるように、売り手ランキングに基づいて注文されてもよい。売り手ランキングは例えば、約束されたＰＤＤを満たす売り手の過去の実績を含む、複数の要因に基づいて定式化されてもよい。外部フロントエンドシステム１０３は（例えば、ネットワークを介して）要求側ユーザデバイスにＳＤＰを配送することができる。
【００２４】
要求側ユーザデバイスは、製品情報をリストするＳＤＰを受信してもよい。その後、ＳＤＰを受信すると、ユーザデバイスはＳＤＰと対話することができる。例えば、要求側ユーザデバイスのユーザは、ＳＤＰ上の「カートに入れる」ボタンをクリックするか、または他の方法で対話することができる。これは、ユーザに関連付けられたショッピングカートに製品を追加する。ユーザデバイスは、このリクエストを送信して、商品をショッピングカートに追加することができる（１０３）。
【００２５】
外部フロントエンドシステム１０３はカートページ（例えば、図１Ｄ）を生成することができる。カートページはいくつかの実施形態ではユーザが仮想「ショッピングカート」に追加した製品をリストし、ユーザデバイスは、ＳＲＰ、ＳＤＰ、または他のページ上のアイコンをクリックするか、または他の方法で対話することによって、カートページを要求してもよい。いくつかの実施形態では、カートページがユーザがショッピングカートに追加したすべての製品、ならびに各製品の数量、各製品毎の価格、関連する数量に基づく各製品の価格、ＰＤＤに関する情報、配送方法、出荷費用、ショッピングカート内の製品を修正するためのユーザインターフェース要素（例えば、数量の削除または修正）、他の製品を注文するかまたは製品の定期的な配送を設定するためのオプション、利息支払いを設定するためのオプション、購入を進めるためのユーザインターフェース要素などのカート内の製品に関する情報を列挙することができる。ユーザデバイスのユーザはショッピングカート内の製品の購入を開始するために、ユーザインターフェース要素（例えば、「今すぐ買う」と読むボタン）をクリックするか、さもなければユーザインターフェース要素と対話することができる。そうすると、ユーザデバイスは、購買を開始するためにこのリクエストを外部フロントエンドシステム１０３へ送信することができる。
【００２６】
外部フロントエンドシステム１０３は購買を開始するためのリクエストを受信することに応じて、オーダーページ（例えば、図１Ｅ）を生成することができる。注文ページはいくつかの実施形態ではショッピングカートからアイテムを再リストし、支払いおよび出荷情報の入力を要求する。例えば、注文ページはショッピングカート内のアイテムの購入者に関する情報（例えば、名前、住所、電子メールアドレス、電話番号）、受取人に関する情報（例えば、名前、住所、電話番号、配送情報）、出荷情報（例えば、配送および／または集荷の速度／方法）、支払情報（例えば、クレジットカード、銀行振込、小切手、記憶クレジット）、現金受領を要求するためのユーザインターフェース要素（例えば、税務目的のための）などを要求する区画を含むことができる。外部フロントエンドシステム１０３は、注文ページをユーザデバイスへ送信することができる。
【００２７】
ユーザデバイスはオーダページに情報を入力し、その情報を外部フロントエンドシステム１０３へ送信するユーザインターフェース要素をクリックするか、または他の方法で対話することができる。そこから、外部フロントエンドシステム１０３は買い物かご内の製品を用いて新しい注文の作成および加工を可能にするために、システム１００内の様々なシステムに情報を送信することができる。
【００２８】
いくつかの実施形態では、外部フロントエンドシステム１０３が売り手が注文に関する情報を送受信することを可能にするようにさらに構成されてもよい。
【００２９】
内部フロントエンドシステム１０５はいくつかの実施形態では内部ユーザ（例えば、システム１００を所有し、運営し、またはリースする団体の従業員）がシステム１００内の１つまたは複数のシステムと対話することを可能にするコンピュータシステムとして実装することができる。例えば、ネットワーク１０１がシステムの提示によってユーザが品目の注文を行うことができるようにする実施形態では、内部フロントエンドシステム１０５は内部ユーザが注文に関する診断および統計情報を表示したり、品目情報を変更したり、注文に関する統計をレビューしたりすることができるウェブサーバとして実装されてもよい。例えば、内蔵フロントエンドシステム１０５は、アパッチＨＴＴＰサーバー、マイクロソフトインターネットインフォメーションサービス、ＮＧＩＮＸ等のソフトウェアを実行するコンピュータ又はコンピュータとして実現することができる。他の実施形態では、内蔵フロントエンドシステム１０５がシステム１００に示されたシステムまたはデバイス（ならびに図示されていない他のデバイス）からの要求を受信および処理し、それらの要求に基づいてデータベースおよび他のデータストアから情報を取得し、取得された情報に基づいて受信された要求への応答を提供するように設計されたカスタムウェブサーバソフトウェアを実行することができる。
【００３０】
いくつかの実施形態では、内蔵フロントエンドシステム１０５がウェブキャッシングシステム、データベース、検索システム、支払いシステム、分析システム、注文監視システムなどのうちの１つまたは複数を含むことができる。一態様では内部フロントエンドシステム１０５がこれらのシステムのうちの１つまたは複数を備えることができ、別の態様では内部フロントエンドシステム１０５がこれらのシステムのうちの１つまたは複数に接続されたインターフェース（たとえば、サーバ間、データベース間、または他のネットワーク接続）を備えることができる。
【００３１】
輸送システム１０７は、いくつかの実施形態ではシステム１００内のシステムまたはデバイスとモバイルデバイス１０７Ａ〜１０７Ｃとの間の通信を可能にするコンピュータシステムとして実装されてもよい。いくつかの実施形態では、トランスポーテーションシステム１０７が１つまたは複数のモバイルデバイス１０７Ａ〜１０７Ｃ（例えば、携帯電話、スマートフォン、ＰＤＡなど）から受信することができる。例えば、いくつかの実施形態では、モバイルデバイス１０７Ａ〜１０７Ｃが配送作業員によって操作されるデバイスを含むことができる。配送作業員は、正社員、臨時社員、または交替社員であってもよく、モバイルデバイス１０７Ａ〜１０７Ｃを利用して、ユーザによって注文された製品を含む荷物の配送を行うことができる。例えば、荷物を配送するために、配送作業員は、どの荷物を配送すべきか、およびそれをどこに配送すべきかを示す通知をモバイルデバイス上で受信することができる。配送場所に到着すると、配送作業員は荷物を（例えば、トラックの後ろに、または荷物の箱に）配置し、モバイルデバイスを使用して荷物上の識別情報（例えば、バーコード、イメージ、文字列、ＲＦＩＤタグなど）に関連するデータを走査または捕捉し、荷物を（例えば、前扉に置いたままにするか、警備員を置いたままにするか、受信者に渡すなどによって）配送することができる。いくつかの実施形態では、配送作業員が荷物の写真をキャプチャすることができ、および／またはモバイルデバイスを使用してシグネチャを取得することができる。モバイルデバイスは例えば、時刻、日付、ＧＰＳ場所、写真、配送作業員に関連付けられた識別子、モバイルデバイスに関連付けられた識別子などを含む配送に関する情報を含む情報を輸送機関１０７へ送信することができる。輸送システム１０７はシステム１００内の他のシステムによるアクセスのために、この情報をデータベース（図示せず）に記憶することができる。輸送システム１０７はいくつかの実施形態ではこの情報を使用して、特定の荷物の場所を示す追跡データを準備し、他のシステムへ送信することができる。
【００３２】
いくつかの実施形態ではあるユーザが１つの種類のモバイルデバイスを使用することができる（例えば、永久作業員はバーコードスキャナ、スタイラス、および他のデバイスなどのカスタムハードウェアと共に専用のＰＤＡを使用することができる）が他のユーザは他の種類のモバイルデバイスを使用することができる（例えば、一時的または移動作業員は既製の携帯電話および／またはスマートフォンを利用することができる）。
【００３３】
いくつかの実施形態では、輸送システム１０７がユーザを各デバイスに関連付けることができる。例えば、輸送システム１０７はユーザ（例えば、ユーザ識別子、従業員識別子、または電話番号）とモバイルデバイス（例えば、国際モバイル装置識別子（ＩＭＥＩ）、国際移動加入識別子（ＩＭＳＩ）、電話番号、汎用一意識別子（ＵＵＩＤ）、またはグローバル一意識別子（ＧＵＩＤ）によって表される）との間の関連を記憶することができる。交通機関１０７はこの関連付けを、配送上で受信されたデータと共に使用して、とりわけ、作業員の場所、作業員の有効性、または作業員のスピードを決定するために、データベースに格納されたデータを分析することができる。
【００３４】
売り手ポータル１０９は、いくつかの実施形態では売り手または他の外部エンティティがシステム１００内の１つまたは複数のシステムと電子的に通信することを可能にするコンピュータシステムとして実装され得る。例えば、売り手は、コンピュータシステム（図示せず）を利用して、売り手が売り手ポータル１０９を使用してシステム１００を通して売りたい製品について、製品情報、注文情報、連絡先情報などをアップロードまたは提供することができる。
【００３５】
出荷および注文追跡システム１１１はいくつかの実施形態では（例えば、デバイス１０２Ａ〜１０２Ｂを使用するユーザによって）顧客によって注文された製品を含む荷物の場所に関する情報を受信し、格納し、転送するコンピュータシステムとして実装され得る。いくつかの実施形態では、出荷および注文追跡装置１１１が顧客が注文した製品を含む荷物を配送する出荷会社によって運営されるウェブサーバ（図示せず）からの情報をリクエストまたは記憶することができる。
【００３６】
いくつかの実施形態では、出荷および注文追跡システム１１１がシステム１００に示されたシステムからの情報をリクエストし、記憶することができる。例えば、出荷および注文追跡システム１１１は、輸送システム１０７にリクエストすることができる。上述のように、交通機関１０７はユーザ（例えば、配送作業員）または乗り物（例えば、配送車）のうちの１つまたは複数に関連付けられた１つまたは複数のモバイルデバイス１０７Ａ〜１０７Ｃ（例えば、携帯電話、スマートフォン、ＰＤＡなど）から受信することができる。いくつかの実施形態では、出荷および注文追跡装置１１１がフルフィルメントセンタ（例えば、フルフィルメントセンタ２００）内の個々の製品の場所を決定するために、労働力管理システム（ＷＭＳ）１１９にリクエストすることもできる。出荷および注文追跡システム１１１は輸送システム１０７またはＷＭＳ １１９のうちの１つまたは複数からデータを要求し、それを処理し、要求に応じてそれを装置（例えば、ユーザデバイス１０２Ａおよび１０２Ｂ）に提示することができる。
【００３７】
フルフィルメント(履行)最適化（ＦＯ）システム１１３はいくつかの実施形態では他のシステム（例えば、外部フロントエンドシステム１０３および／または出荷および注文追跡システム１１１）からの顧客注文に関する情報を記憶するコンピュータシステムとして実装されてもよい。ＦＯシステム１１３はまた、特定のアイテムがどこに保持または格納されるかを記述する情報を格納してもよい。たとえば、特定の項目は１つのフルフィルメントセンタにのみ格納され、他の特定の項目は複数のフルフィルメントセンタに格納される場合がある。さらに他の実施形態では、特定のフルフィルメントセンタが特定のセットのアイテム（例えば、生鮮食品または冷凍製品）のみを格納するように設計されてもよい。ＦＯシステム１１３はこの情報ならびに関連する情報（例えば、数量、サイズ、受領日、有効期限など）を格納する。
【００３８】
また、ＦＯシステム１１３は、商品毎に対応するＰＤＤ(約束配送日）を計算してもよい。ＰＤＤは、いくつかの実施形態では１つまたは複数の要因に基づくことができる。例えば、ＦＯシステム１１３は製品に対する過去の需要（例えば、その製品がある期間中に何回注文されたか）、製品に対する予想需要（例えば、来るべき期間中にその製品を注文するために何人の顧客が予想されるか）、ある期間中にいくつの製品が注文されたかを示すネットワーク全体の過去の需要、来るべき期間中にいくつの製品が注文されることが予想されるかを示すネットワーク全体の予想需要、各フルフィルメントセンタ２００に記憶された製品の１つ以上のカウント、その製品に対する各製品、予想または現行の注文などに基づいて、製品に対するＰＤＤを計算することができる。
【００３９】
いくつかの実施形態では、ＦＯシステム１１３が定期的に（例えば、１時間ごとに）商品ごとにＰＤＤを決定し、それを検索または他のシステム（例えば、外部フロントエンドシステム１０３、ＳＡＴシステム１０１、出荷および注文追跡システム１１１）へ送信するためにデータベースに格納することができる。他の実施形態では、ＦＯシステム１１３が１つまたは複数のシステム（例えば、外部フロントエンドシステム１０３、ＳＡＴシステム１０１、出荷および注文追跡システム１１１）から電子要求を受信し、オンデマンドでＰＤＤを計算することができる。
【００４０】
フルフィルメントメッセージングゲートウェイ１１５はいくつかの実施形態ではＦＯシステム１１３などのシステム１００の１つ以上のシステムから１つのフォーマットまたはプロトコルで要求または応答を受信し、それを別のフォーマットまたはプロトコルに変換し、変換されたフォーマットまたはプロトコルで、ＷＭＳ １１９または第三者フルフィルメントシステム１２１Ａ、１２１Ｂ、または１２１Ｃなどの他のシステムに転送するコンピュータシステムとして実装されてもよい。
【００４１】
サプライチェーン管理（ＳＣＭ）システム１１７は、いくつかの実施形態では予測機能を実行するコンピュータシステムとして実装することができる。例えば、ＳＣＭシステム１１７は例えば、製品に対する過去の需要、製品に対する予想される需要、ネットワーク全体の過去の需要、ネットワーク全体の予想される需要、各フルフィルメントセンタ２００に記憶された計数製品、各製品に対する予想または現在の注文などに基づいて、特定の製品に対する需要の水準を予測することができる。この予測された水準およびすべてのフルフィルメントセンタにわたるそれぞれの製品の量に応じて、ＳＣＭシステム１１７は特定の製品に対する予測された需要を満たすのに充分な量を購入し、在庫するための１つまたは複数の購入注文を生成することができる。
【００４２】
労働力管理システム（ＷＭＳ）１１９は、いくつかの実施形態ではワークフローをモニタするコンピュータシステムとして実装されてもよい。例えば、ＷＭＳ １１９は個別のイベントを示すイベントデータを個々のデバイス（例えば、デバイス１０７Ａ〜１０７Ｃまたは１１９Ａ〜１１９Ｃ）から受信することができる。例えば、ＷＭＳ １１９は、荷物を走査するためにこれらの装置の１つの使用を示すイベントデータを受信してもよい。フルフィルメントセンタ２００および図２に関して以下で論じるように、実行処理中に、荷物識別器（例えば、バーコードまたはＲＦＩＤタグデータ）は特定の段階で機械によってスキャンまたは読み取ることができる（例えば、自動またはハンドヘルドバーコードスキャナ、ＲＦＩＤリーダ、高速カメラ、タブレット１１９Ａ、モバイルデバイス／ＰＤＡ １１９Ｂ、コンピュータ１１９Ｃなどのデバイス）。ＷＭＳ １１９は荷物識別子、時刻、日付、場所、ユーザ識別子、または他の情報と共に、対応するデータベース（図示せず）に、荷物識別子の走査または読み取りを示すそれぞれの事象を格納することができ、この情報を他のシステム（例えば、出荷および注文追跡システム１１１）に提供することができる。
【００４３】
ＷＭＳ １１９はいくつかの実施形態では１つまたは複数のデバイス（たとえば、デバイス１０７Ａ〜１０７Ｃまたは１１９Ａ〜１１９Ｃ）をシステム１００に関連する１つまたは複数のユーザに関連付ける情報を記憶することができる。例えば、いくつかの状況では、ユーザ（パートまたはフルタイムの従業員など）がユーザがモバイルデバイスを所有する（例えば、モバイルデバイスがスマートフォンである）という点で、モバイルデバイスに関連付けられてもよい。他の状況では、ユーザがユーザが一時的にモバイルデバイスを保管している（例えば、ユーザは日の始めにモバイルデバイスをチェックアウトし、日中にそれを使用し、日の終わりにそれを返す）という点で、モバイルデバイスに関連付けられてもよい。
【００４４】
ＷＭＳ １１９は、いくつかの実施形態ではシステム１００に関連する各ユーザの作業ログを維持することができる。例えば、ＷＭＳ １１９は任意の割り当てられたプロセス（例えば、トラックのアンロード、ピックゾーンからのアイテムのピッキング、リビン(ｒｅｂｉｎ)ウォールワーク、パッキングアイテム）、ユーザ識別子、場所（例えば、フルフィルメントセンタ２００内のフロアまたはゾーン）、従業員によってシステム内を移動されたユニットの数（例えば、ピッキングされたアイテムの数、パッキングされたアイテムの数）、装置に関連する識別子（例えば、装置１１９Ａ〜１１９Ｃ）などを含む、各従業員に関連する情報を記憶することができる。いくつかの実施形態では、ＷＭＳ １１９がデバイス１１９Ａ〜１１９Ｃ上で動作するタイムキーピングシステムなどのタイムキーピングシステムからチェックインおよびチェックアウト情報を受信することができる。
【００４５】
第三者フルフィルメント（３ＰＬ）システム１２１Ａ〜１２１Ｃは、いくつかの実施形態では物流および製品のサードパーティプロバイダに関連するコンピュータシステムを表す。例えば、（図２に関して以下に説明するように）いくつかの製品がフルフィルメントセンタ２００に格納されている間、他の製品は、オフサイトで格納されてもよく、オンデマンドで生産されてもよく、またはフルフィルメントセンタ２００に格納するために利用できなくてもよい。３ＰＬシステム１２１Ａ〜１２１ＣはＦＯシステム１１３から（例えば、ＦＭＧ １１５を介して）注文を受信するように構成されてもよく、製品および／またはサービス（例えば、配送または設置）を顧客に直接的に提供してもよい。いくつかの実施形態では３ＰＬシステム１２１Ａ〜１２１Ｃのうちの１つまたは複数がシステム１００の一部とすることができ、他の実施形態では３ＰＬシステム１２１Ａ〜１２１Ｃのうちの１つまたは複数がシステム１００の外部（例えば、サードパーティプロバイダによって所有または運営される）とすることができる。
【００４６】
フルフィルメントセンタ自動システム（ＦＣ認証）１２３は、いくつかの実施形態では様々な機能を有するコンピュータシステムとして実装され得る。例えば、いくつかの実施形態では、ＦＣ認証１２３がシステム１００内の１つまたは複数の他のシステムのためのシングルサインオン（ＳＳＯ）サービスとして動作することができる。例えば、ＦＣ認証１２３はユーザが内部フロントエンドシステム１０５を介してログインすることを可能にし、ユーザが出荷および注文追跡系１１１においてリソースにアクセスするための同様の特権を有していることを決定し、ユーザが２回目のログイン処理を必要とせずにそれらの特権にアクセスすることを可能にしてもよい。他の実施形態では、ＦＣ認証１２３がユーザ（例えば、従業員）が自分自身を特定の作業に関連付けることを可能にすることができる。例えば、従業員の中には、電子装置（装置１１９Ａ〜１１９Ｃなど）を持たない者もいれば、その代わりに、１日の過程中に、フルフィルメントセンタ２００内で、タスクからタスクへ、およびゾーンからゾーンへ移動することができる。ＦＣ認証１２３は、それらの従業員が彼らがどの仕事をしているか、および彼らが様々な時刻にどの区域にいるかを示すことを可能にするように構成されてもよい。
【００４７】
労働管理システム（ＬＭＳ）１２５は、いくつかの実施形態では従業員（フルタイムおよびパートタイムの従業員を含む）のための出勤および残業を記憶するコンピュータシステムとして実装されてもよい。例えば、ＬＭＳ １２５は、ＦＣ認証１２３、ＷＭＡ １１９、装置１１９Ａ〜１１９Ｃ、輸送装置１０７、および／または装置１０７Ａ〜１０７Ｃから受信することができる。
【００４８】
図１Ａに示される特定の構成は単なる例である。例えば、図１ＡはＦＯシステム１１３に接続されたＦＣ認証システム１２３を示すが、全ての実施形態がこの特定の構成を必要とするわけではない。実際、いくつかの実施形態では、システム１００内のシステムがインターネット、イントラネット、ＷＡＮ(ワイドエリアネットワーク）、ＭＡＮ(メトロポリタンエリアネットワーク）、ＩＥＥＥ ８０２．１１ａ／ｂ／ｇ／ｎ規格に準拠する無線ネットワーク、専用線などを含む１つまたは複数の公衆またはプライベートネットワークを介して互いに接続され得る。いくつかの実施形態では、システム１００内のシステムの１つ以上がデータセンター、サーバファームなどに実装された１つ以上の仮想サーバとして実装されてもよい。
【００４９】
図２は、フルフィルメントセンタ２００を示す。フルフィルメントセンタ２００は、注文時に顧客に出荷するためのアイテムを格納する物理的な場所の実例である。フルフィルメントセンタ（ＦＣ）２００は多数のゾーンに分割することができ、その各々を図２に示す。いくつかの実施形態ではこれらの「ゾーン」がいくつかの実施形態ではアイテムを受け取り、アイテムを格納し、アイテムを取り出し、アイテムを出荷するプロセスの異なる段階間の仮想分割と考えることができ、したがって、「ゾーン」は図２に示されているが、ゾーンの他の分割も可能であり、図２のゾーンはいくつかの実施形態では省略、複製、または修正することができる。
【００５０】
インバウンドゾーン２０３は、図１Ａのシステム１００を使用して製品を販売したい売り手からアイテムが受け取られるＦＣ ２００の領域を表す。例えば、売り手は、トラック２０１を使用してアイテム２０２Ａ及び２０２Ｂを配送することができる。アイテム２０２Ａはそれ自体の出荷パレットを占有するのに十分な大きさの単一のアイテムを表すことができ、アイテム２０２Ｂは、スペースを節約するために同じパレット上に一緒に積み重ねられたアイテムのセットを表すことができる。
【００５１】
作業員はインバウンドゾーン２０３内のアイテムを受け取り、オプションとして、コンピュータシステム（図示せず）を使用して、アイテムの破損および正当性を検査することができる。例えば、作業員は、コンピュータシステムを使用して、品目２０２Ａおよび２０２Ｂの数量を品目の注文数量と比較することができる。数量が合致しない場合、その作業員は、項目２０２Ａまたは２０２Ｂのうちの１つまたは複数を拒否することができる。もし量が一致すれば、作業員はそれらのアイテムを（例えば、人形、手すり、フォークリフト、または手動で使用して）緩衝区域２０５に移動させることができる。バッファゾーン２０５は例えば、予測される需要を満たすのに十分な量のアイテムがピッキングゾーン内にあるため、ピッキングゾーン内で現在必要とされていないアイテムのための一時記憶領域であってもよい。いくつかの実施形態では、フォークリフト２０６が物品をバッファゾーン２０５の周り、およびインバウンドゾーン２０３とドロップゾーン２０７との間で移動させるように動作する。ピッキングゾーンに品目２０２Ａまたは２０２Ｂが必要な場合（例えば、予想される需要のため）、フォークリフトは、品目２０２Ａまたは２０２Ｂを落下ゾーン２０７に移動させることができる。
【００５２】
ドロップゾーン２０７は、アイテムがピッキングゾーン２０９に移動される前にアイテムを格納するＦＣ ２００の領域であってもよい。ピッキングタスクに割り当てられた作業員（「ピッカ」）はピッキングゾーン内のアイテム２０２Ａおよび２０２Ｂに接近し、ピッキングゾーンのバーコードをスキャンし、モバイルデバイス（例えば、装置１１９Ｂ）を使用してアイテム２０２Ａおよび２０２Ｂに関連するバーコードをスキャンすることができる。次いで、ピッカーはアイテムをピッキングゾーン２０９に（例えば、カートの上に置くか、またはそれを運ぶことによって）取り込むことができる。
【００５３】
ピッキングゾーン２０９は、アイテム２０８が記憶ユニット２１０に記憶されるＦＣ ２００の領域であってもよい。いくつかの実施形態では、貯蔵ユニット２１０が物理的な棚、本棚、箱、運搬箱、冷蔵庫、冷凍庫、冷蔵庫などのうちの１つまたは複数を含むことができる。いくつかの実施形態では、ピッキングゾーン２０９が複数のフロアに編成されてもよい。いくつかの実施形態では、作業員または機械が例えば、フォークリフト、エレベータ、コンベアベルト、カート、ハンドトラック、ドリー、自動ロボットもしくは装置、または手動を含む多数の方法で、物品をピッキングゾーン２０９に移動させてもよい。例えば、ピッカーはアイテム２０２Ａおよび２０２Ｂをドロップゾーン２０７内のハンドトラックまたはカート上に置き、アイテム２０２Ａおよび２０２Ｂをピッキングゾーン２０９まで歩くことができる。
【００５４】
ピッカーは、保管ユニット２１０上の特定のスペースのような、ピッキングゾーン２０９内の特定のスポットにアイテムを配置する（または「収納する」）命令を受け取ることができる。例えば、ピッカーはモバイルデバイス（例えば、装置１１９Ｂ）を使用してアイテム２０２Ａを走査することができる。デバイスは例えば、通路、棚、および場所を示すシステムを使用して、ピッカーがアイテム２０２Ａを収納すべき場所を示すことができる。次に、デバイスはその場所にアイテム２０２Ａを格納する前に、その場所でバーコードをスキャンするようにピッカーに促すことができる。装置は図１ＡのＷＭＳ １１９のようなコンピュータシステムに（例えば、無線ネットワークを介して）データを送信し、装置１１９Ｂを使用するユーザによってアイテム２０２Ａがその場所に格納されたことを示すことができる。
【００５５】
ユーザが注文を出すと、ピッカーは記憶ユニット２１０から１つまたは複数のアイテム２０８を取り出すために、デバイス１１９Ｂ上で命令を受け取ることができる。ピッカーはアイテム２０８を取り出し、アイテム２０８上のバーコードをスキャンし、それを搬送機構２１４上に置くことができる。搬送機構２１４はスライドとして表されているが、いくつかの実施形態では搬送機構がコンベヤベルト、エレベータ、カート、フォークリフト、ハンドトラック、台車、カートなどのうちの１つまたは複数として実施することができる。次に、品目２０８は、パッキングゾーン２１１に到着することができる。
【００５６】
パッキングゾーン２１１は、アイテムがピッキングゾーン２０９から受け取られ、最終的に顧客に出荷するためにボックスまたはバッグにパッキングされるＦＣ ２００の領域であってもよい。パッキングゾーン２１１では受取アイテム（「リビン(ｒｅｂｉｎ)作業員」）に割り当てられた作業員がピッキングゾーン２０９からアイテム２０８を受け取り、それがどの注文に対応するかを決定する。例えば、リビン(ｒｅｂｉｎ)作業員はアイテム２０８上のバーコードを走査するために、コンピュータ１１９Ｃなどの装置を使用することができる。コンピュータ１１９Ｃはどの注文アイテム２０８が関連付けられているかを視覚的に示すことができる。これは例えば、注文に対応する壁面２１６上の空間または「セル」を含むことができる。注文が完了すると（例えば、セルが注文のためのすべてのアイテムを含むため）、リビン(ｒｅｂｉｎ)作業員は注文が完了したことをパッキング作業員（または「パッカー」）に示すことができる。梱包業者はセルから品目を取り出し、それらを出荷のために箱または袋に入れることができる。その後、パッカーは例えば、フォークリフト、カート、ドリー、ハンドトラック、コンベヤベルトを介して、又は他の方法で、箱又はバッグをハブゾーン２１３に送ることができる。
【００５７】
ハブゾーン２１３は、パッキングゾーン２１１から全てのボックスまたはバッグ（「荷物」）を受け取るＦＣ ２００の領域であってもよい。ハブゾーン２１３内の作業員および／またはマシンは荷物２１８を検索し、それぞれの荷物が行こうとする配送領域の一部を決定し、荷物を適切なキャンプゾーン２１５にルーティングすることができる。例えば、配送領域が２つのより小さいサブ領域を有する場合、荷物は２つのキャンプゾーン２１５のうちの１つに進む。いくつかの実施形態では、作業員またはマシンが（例えば、デバイス１１９Ａ〜１１９Ｃのうちの１つを使用して）荷物を走査して、その最終的な宛先を決定することができる。荷物をキャンプゾーン２１５にルーティングすることは、例えば、荷物が向けられている地理的エリアの一部を（例えば、郵便番号に基づいて）決定することと、地理的エリアの一部に関連付けられたキャンプゾーン２１５を決定することとを含むことができる。
【００５８】
キャンプゾーン２１５はいくつかの実施形態では１つまたは複数の建物、１つまたは複数の物理的な空間、または１つまたは複数のエリアを備えることができ、荷物は、経路および／またはサブ経路に分類するためにハブゾーン２１３から受け取られる。いくつかの実施形態ではキャンプゾーン２１５がＦＣ ２００から物理的に分離されているが、他の実施形態ではキャンプゾーン２１５がＦＣ ２００の一部を形成することができる。
【００５９】
キャンプゾーン２１５内の作業員および／またはマシンは例えば、目的地と現存する経路および／またはサブ経路との照合、経路および／またはサブ経路ごとの作業負荷の算出、時刻、出荷方法、荷物２２０を出荷する費用、荷物２２０内のアイテムに関連付けられたＰＤＤなどに基づいて、荷物２２０がどの経路および／またはサブ経路に関連付けられるべきかを決定することができる。いくつかの実施形態では、作業員またはマシンが（例えば、デバイス１１９Ａ〜１１９Ｃのうちの１つを使用して）荷物を走査して、その最終的な宛先を決定することができる。荷物２２０が特定の経路および／またはサブ経路に割り当てられると、作業員および／またはマシンは、出荷される荷物２２０を移動させることができる。例示的な図２において、キャンプゾーン２１５は、トラック２２２、かご２２６、および配送作業員２２４Ａおよび２２４Ｂを含む。いくつかの実施形態では、トラック２２２が配送作業員２２４Ａによって駆動されてもよく、配送作業員２２４ＡはＦＣ ２００の荷物を配送する常勤の従業員であり、トラック２２２はＦＣ ２００を所有し、リースし、または運営する同じ企業によって所有され、リースされ、または運営される。いくつかの実施形態では、自動車２２６が配送作業員２２４Ｂによって駆動されてもよく、ここで、配送作業員２２４Ｂは必要に応じて（例えば、季節的に）送達する「屈曲」または時折の作業員である。自動車２２６は、配送作業員２２４Ｂによって所有され、リースされ、または操作され得る。
【００６０】
いくつかの実施形態では、注文のアイテムのソートがＦＣ ２００において実施されてもよい。例えば、仕分けは、仕分け装置２１６を使用して梱包ゾーン２１１内で実施することができる。
【００６１】
図３は、開示された実施形態に一致する、集荷および配送のための経路計画のための例示的な装置３００の概略図である。装置３００は少なくとも１つのモバイルデバイス（例えば、モバイルデバイス１０７Ａ−１０７Ｃ）及び少なくとも１つのコンピュータ（例えば、コンピュータ３０２）を含む。図３には一例として１つのコンピュータ３０２しか示されていないが、コンピュータ３０２に類似した２つ以上のコンピュータをシステム３００に含めることができることを理解されたい。モバイルデバイス１０７Ａ〜１０７Ｃは、ネットワーク３１０を使用してコンピュータ３０２に接続される。いくつかの実施形態では、コンピュータ３０２がＳＡＴ １０１、輸送システム１０７、ＳＯＴ １１１、ＦＯ １１３、またはＷＭＳ １１９内のコンピュータとして実装することができる。いくつかの実施形態では、ネットワーク３１０がシステム１００の一部または全部であってもよい。
【００６２】
コンピュータ３０２は、マイクロコンピュータ、メインフレームコンピュータ、スーパーコンピュータ、汎用コンピュータ、特殊目的コンピュータ、統合／組み込みコンピュータ、サーバコンピュータ、パーソナルコンピュータ、ラップトップコンピュータ、タブレットコンピュータ、携帯電話、パーソナルデータアシスタント（ＰＤＡ）、ウェアラブルコンピューティングデバイス、クラウドコンピュータなど、任意の数の任意のタイプのコンピュータの任意の組み合わせとして実現することができる。コンピュータ３０２のようなシステム３００内のコンピュータはネットワーク（例えば、ネットワーク３１０）を用いて相互接続された異なる地理的場所に場所する複数のコンピュータを含む仮想コンピュータとして実施することもできる。
【００６３】
コンピュータ３０２は、データベース３０４、プロセッサ３０６、およびメモリ３０８を含む。メモリ３０８は、経路計画のためのプロセスまたは手順を実施するためにプロセッサ３０６によって実行され得る命令を記憶することができる。データベース３０４は、１つ以上のローカルまたはリモートコンピュータまたは分散コンピュータシステムに記憶され、他のコンピュータにアクセス可能な構造化データのコレクションの任意の形態として実施可能である。
【００６４】
プロセッサ３０６は、情報を操作または処理することができる汎用または特定の電子デバイスとすることができる。例えば、プロセッサ３０６は、任意の数の中央処理ユニット（または「ＣＰＵ」）、グラフィックス処理ユニット（または「ＧＰＵ」）、光プロセッサ、プログラマブル論理コントローラ、マイクロコントローラ、マイクロプロセッサ、デジタル信号プロセッサ、知的財産（ＩＰ）コア、プログラマブル論理アレイ（ＰＬＡ）、プログラマブルアレイ論理（ＰＡＬ）、ジェネリックアレイ論理（ＧＡＬ）、コンプレックスプログラマブル論理デバイス（ＣＰＬＤ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、システムオンチップ（ＳｏＣ）、特定用途向け集積回路（ＡＳＩＣ）、およびデータ処理が可能な任意のタイプの回路の任意の組み合わせを含んでもよい。プロセッサ３０６はネットワーク（例えば、ネットワーク３１０）を介して接続された複数のマシンまたは装置に分散された１つ以上のプロセッサを含む仮想プロセッサであってもよい。
【００６５】
メモリ３０８はプロセッサ３０６によってアクセス可能な（例えば、図示されていないバスを介して）コードおよびデータを記憶することができる汎用または特定の電子装置であってもよい。例えば、メモリ３０８は、任意の数のランダム・アクセス・メモリ、リード・オンリー・メモリ、光ディスク、磁気ディスク、ハード・ドライブ、ソリッド・ステート・ドライブ、フラッシュ・ドライブ、セキュリティ・デジタル（ＳＤ）カード、メモリ・スティック、コンパクト・フラッシュ（ＣＦ）カード、または任意のタイプの記憶装置の任意の組み合わせを含むことができる。コードには、オペレーティング・システム（ＯＳ）と、特定のタスクのための１つ以上のアプリケーション・プログラム（または「アプリ」）が含まれる場合がある。メモリ３０８はネットワーク（例えば、ネットワーク３１０）を介して接続された複数のマシンまたは装置に分散された１つ以上のメモリを含む仮想メモリであってもよい。
【００６６】
ネットワーク３１０は、１つまたは複数のパブリックまたはプライベート通信ネットワークとすることができる。例えば、ネットワーク３１０は、任意の数のインターネット、イントラネット、ローカルエリアネットワーク、ワイドエリアネットワーク、メトロポリタンエリアネットワーク、仮想プライベートネットワーク、無線ネットワーク、有線ネットワーク、専用線、セルラデータネットワーク、およびブ経路ゥース接続、赤外線接続、または近距離無線通信（ＮＦＣ）接続を使用するネットワークの任意の組み合わせを含むことができる。
【００６７】
いくつかの実施形態では、配送作業員が雇用状況（例えば、正社員、臨時社員、または交代勤務従業員）、年功序列（例えば、年功従業員または初心者）、勤務シフト（例えば、終日または半日従業員）、輸送方法（例えば、歩行、自転車または運転従業員）などの異なる基準によって分類され得、異なる需要特性を有する配送のタスクに、異なる分類の作業員を割り当てることができる。いくつかの実施形態では配送作業員の識別子がレコードとしてデータベース４０４に格納されてもよく、配送作業員の分類はレコードの属性として格納されてもよい。本明細書における「配送作業員」は、荷物の配送、荷物の集荷、またはそれらの組合せの作業を実行することができることに留意されたい。
【００６８】
いくつかの実施形態では、配送作業員の識別子とモバイルデバイスの識別子との間の関連付けはレコードとしてデータベース３０４に格納されてもよい。例えば、データベース３０４は作業員の識別子の関連を記憶することができ、モバイルデバイスの識別子はエントリーとして記憶することができる。いくつかの実施形態では、モバイルデバイス１０７Ａ〜１０７Ｃが配送作業員および／または配送車と関連付けられてもよい。そのような団体は，所有権，指定又は一時的所有に基づくことができる。例えば、配送作業員はモバイルデバイス１０７Ａ（例えば、スマートフォン）を所有し、それに関連付けられてもよい。別の例として、モバイルデバイス１０７Ｂ（例えば、既製のＰＤＡ）は、配送トラックに割り当てられ、関連付けられてもよい。別の例では、配送作業員がモバイルデバイス１０７Ｃ（例えば、ウェアラブルデバイス）にログインし、それに関連付けられてもよい。
【００６９】
いくつかの実施形態では、モバイルデバイス１０７Ａ〜１０７Ｃを使用して、配送作業員または車両の状態を監視および更新し、その状態データを示すデータを、ネットワーク３１０を介してコンピュータ３０２へ送信することができる。ステータスデータは例えば、配送作業員または車両がタスクにアイドル状態またはビジー状態であるか否か、配送作業員または車両が新規の配送タスクに割り当てられるために利用可能であるか否か、配送作業員または車両の場所、配送作業員の出勤および残業情報、配送作業員がとった経路、配送作業員または車両の走行距離、または配送タスクマネジメントに関連する他のステータス情報を示すことができる。
【００７０】
本発明に従って実施される荷物集荷および配送のための経路計画の方法、装置、およびシステムは、以下のように図４〜図７に関連して詳細に説明される。図４−７において、プロセス４００、６００、および７００は、コンピュータ読み取り可能な記憶媒体に記憶された、プログラムコードまたは命令などのソフトウェアまたはファームウェアとして実施することができる。プログラムコードまたは命令は、プロセッサによって読み取られて実行され、前述のプロセスを実装することができる。例えば、コンピュータ可読記憶媒体はメモリ３０８であってもよく、プロセッサはプロセッサ３０６であってもよい。いくつかの実施形態では、前述のプロセスがＰＬＡ、ＰＡＬ、ＧＡＬ、ＣＰＬＤ、ＦＰＧＡ、ＳｏＣ、またはＡＳＩＣなどの専用ハードウェアとして実装され得る。前述のプロセスは、アルゴリズムによって指定された動作を実行することができる専用ハードウェアにプログラムされたアルゴリズムとして実装することができる。いくつかの実施形態では、前述のプロセスが前述のソフトウェアとハードウェアとの組み合わせとして実装されてもよい。
【００７１】
図４は、開示された実施形態に従った、集荷および配送のための経路計画の例示的な処理４００の流れ図である。
【００７２】
工程４０２において、プロセッサ３０６は、地理的領域内の所定の地理的場所と、所定の地理的場所を接続する所定の経路を表すデータとを受信する。いくつかの実施形態では、所定の地理的場所および所定の経路が地理的領域で働く経験豊富な配送作業員によって使用される経路であってもよい。それらは、監督者の評価などによって手動で、または機械などによって自動的に予め決定されてもよい。例えば、プロセッサ３０６は、配送作業員の配送経路の得点を決定することができる。得点は、配送経路で働く配送作業員の配送的な有効性または体験の程度を示すことができる。いくつかの実施形態では、得点が経路に沿った配送を完了するのに費やされた時間、経路のために配送または拾われた荷物の数、様々な郵便番号間の移動に費やされた時間などの様々な要因に基づいて計算することができる。いくつかの実施形態では、得点が配送効率に比例し得る。いくつかの実施形態では、得点が配送効率に反比例し得る。所定の場所および所定の経路は経路計画のためのテンプレートとして使用されてもよく、代替的に、それぞれ「テンプレート場所」および「テンプレート経路」と呼ばれてもよい。テンプレート場所のテンプレート経路を決定するために、いくつかの実施形態では、プロセッサ３０６がスコアが配送効率に比例すると仮定して、テンプレート場所を接続し、最も高いスコアを有する経路をテンプレート経路として選択することができる。いくつかの実施形態では、プロセッサ３０６がテンプレート場所を接続し、最も短い移動時間を有する経路をテンプレート経路として選択することができる。
【００７３】
上記の例では、得点が所定の数値を上回る場合、プロセッサ３０６は配送経路を所定の経路として決定し、配送経路の地理的場所を所定の地理的場所として決定することができる。いくつかの実施形態では、プロセッサ３０６が地理的領域内のすべての配送作業員についてスコアを分類し、経験作業員としてそれらの上位パーセントを選択することができる。プロセッサ３０６は、インプットとして、選択された経験豊富な作業員が訪れた地理的場所および経路を使用することができる。
【００７４】
別の例として、経験豊富な配送作業員によって使用される経路は、配送作業員の識別子、および訪問先場所の経路またはシーケンスの全方向に従って分類されてもよい。同じ場所の組に対して、異なる配送作業員は、異なる経路に対して、ほぼ同じ水準の有効性をもたらすことができる。これらの異なる経路は、経路計画における異なる考慮事項および／または制限を含むことができる。これらの異なる経路を含め、分類することによって、これらの考慮事項および制限事項の特徴および特徴は、経路計画のためのシステムにおいて考慮され得る。
【００７５】
工程４０４において、プロセッサ３０６は、所定の経路に沿った所定の場所の連続的な近さに基づいて、地理的領域内の単位エリアを決定する。単位エリアは、配送作業員が訪れるための独立した地理的グラニュールであり得る１組の地理的ユニットを含む地理的エリアである。例えば、単位エリアは、建物、モール、近隣、道路によって囲まれたエリア、コミュニティ、または任意の場所のセットであってもよい。地理的単位は、家、アパート、店、オフィス、建物内の部屋、またはコミュニティ内の建物であってもよい。
【００７６】
図５は、開示された実施形態に一致する例示的な単位エリアを示す図である。図５において、ドットは地理的単位を表し、ポリゴン５０２〜５０８は単位エリアを表す。単位エリア５０２には５つの地理的単位があり、単位エリア５０４には４つの地理的単位があり、単位エリア５０６には２つの地理的単位があり、単位エリア５０８には３つの地理的単位がある。単位エリア５０２〜５０８は、配送作業員が単位エリア５０２〜５０８のうちの１つの中の地理的単位を連続して訪問し、その後、任意の他の単位エリア内の任意の他の建物を訪問することができるように分割される。いくつかの実施形態では、地理的ユニットの異なる部分が異なる単位エリアに属すると決定されてもよい。例えば、複数の入口単位エリア（例えば、モール）は広いエリアをカバーすることがあり、その中で、地理的ユニット（例えば、部屋又は店舗）は、各入口までの距離が異なることがある。これらの入口は、第１の入口および第２の入口が異なる通りにあるなど、第２の入口から離れた第１の入口を含むことができる。第１の入口付近の第１の地理的ユニットと第２の入口付近の第２の地理的ユニットに対して、第１の地理的ユニットと第２の地理的ユニットは効率的な経路計画のために、２つの異なる単位エリアに分割することができる。
【００７７】
いくつかの実施形態では、単位エリアが経路計画および生成のための単位として使用されてもよい。例えば、所与の一組の場所に対する経路を生成するために、１つの単位エリア内のすべての場所は経路内の１つの停車場として集合的に扱われてもよく、すなわち、配送作業員（例えば、トラックドライバー）は荷物配送または集荷のためにそれらの場所に停車し、現単位エリア内で配送の作業を完了するときに次回の停車場に出発してもよい。経路計画および生成のためのユニットとして単位エリアを使用することは、計算費用および計算量を削減し、配送効率を向上させることができる。例えば、図５において、単位エリア５０２〜５０８は、計画された経路の停留所として扱われてもよい。
【００７８】
図４に戻って、工程４０６において、プロセッサ３０６は、単位エリアの少なくとも１つを接続する経路を決定するための配送パターンを生成する。各々の配送模様は単位エリアのうちの少なくとも１つを含むことができ、単位エリアのうちの少なくとも１つは、訪問順序に関連付けられることができる。前記訪問順序は、前記単位エリアのうちの少なくとも一つを配送形態で訪問する順序を表すことができる。配送方式では、訪問順序は固定であってもよい。例えば、図５では、配送パターン５００が単位エリア５０２〜５０６を含み、単位エリア５０２〜５０６が図５の矢印で示される訪問シークエンス５０２５０４５０６に関連する。これらの配送パターンは、経路計画に使用することができる。
【００７９】
ステップ４０８で、プロセッサ３０６が、訪問する目標場所を含むタスクデータを受信した場合、プロセッサ３０６は、配送パターンおよび目標データを使用して、目標場所を訪問するための目標経路を決定する。いくつかの実施形態では、タスクデータはＳＡＴ １０１から受信されてもよい。
【００８０】
ステップ４１０において、プロセッサ３０６は、目標経路をモバイル装置へ送信する。例えば、モバイルデバイス１０７Ａ〜１０７Ｃのいずれかであってもよい。いくつかの実施形態では、モバイル装置が配送作業員によって運ばれてもよい。配送作業員は、モバイル装置によって受信された目標経路に沿って荷物を配送または集荷のための作業に割り当てられてもよい。
【００８１】
いくつかの実施形態ではステップ４０４において、プロセッサ３０６は所定の経路に沿った所定の場所の連続的な近さに基づいて単位エリアを決定することができる。例えば、プロセッサ３０６は、地理的領域内の配送可能な場所を受信することができる。配送可能な場所は、配送および集荷に利用可能な場所であってもよい。
【００８２】
プロセッサ３０６は、第１の機械学習モデルを使用して、配送可能な場所のそれぞれについて場所ベクトルを決定することができる。場所ベクトルは、配送可能な場所のベクトル表現であってもよく、２つの場所ベクトル間の距離が配送経路に沿った２つの場所ベクトルに対応する２つの場所の連続的な近さを示してもよいように決定されてもよい。距離は、２つの場所ベクトルの間の差として決定され得る。連続的な近さは、配送経路に沿って２つの場所に行く距離を指すことができる。いくつかの実施形態では、第１の機械学習モデルが第１のニューラルネットワークモデルであってもよい。例えば、第１のニューラルネットワークモデルは、word2vecモデルのニューラルネットワークに類似し得る。いくつかの実施形態では、第１のニューラルネットワークモデルがワンホットベクトルフォーマットの配送可能な場所のアドレスを入力として使用し、配送可能な場所の場所ベクトルを決定することができる。第１のニューラルネットワークモデルは、ステップ４０２において、所定の場所を使用して生成され、訓練されてもよい。
【００８３】
次いで、プロセッサ３０６は、配送可能な場所のそれぞれについて特徴ベクトルを決定することができる。特徴ベクトルは、配送可能な場所の場所ベクトルおよび場所属性を含むことができる。いくつかの実施形態では、場所特徴が地理座標、建物の番号、エリアの名前、道路の名前、または郵便番号のうちの少なくとも１つを含むことができる。例えば、特徴ベクトルは建物番号、コミュニティの名前、および（［０．１，０．５，０．３］、３、「Ａ」、１００１０）のような郵便番号を含むことができ、［０．１，０．５，０．３］は場所ベクトルであり、３は建物番号であり、「Ａ」はコミュニティの名前であり、１００１０は郵便番号である。
【００８４】
次いで、プロセッサ３０６は、特徴ベクトル間の距離に基づいて配送可能な場所をグループ化することによって、単位エリアを決定することができる。２つの特徴ベクトル間の距離は、２つの特徴ベクトル間の差として決定され得る。１つの単位エリアにグループ化された配送可能な場所の特徴ベクトル間の距離は、所定の閾値内であってもよい。例えば、第１の特徴ベクトル（［０．１、０．５、０．３］、３、「Ａ」、１００１０）および第２の特徴ベクトル（［０．１２、０．４８、０．３］、５、「Ａ」、１００１０）について、距離は、（［０．０２、−０．０２、０］、２、０、０）などの２つの特徴ベクトル間の直接減算として決定される差分ベクトルの大きさとして決定され得る。文字の場合、減算はＡＳＣＩＩ 値を使用して実行できる。差分ベクトルの大きさが所定の閾値内にある場合、２つの対応する配送可能な場所は、同じ単位エリアにグループ化されてもよい。いくつかの実施形態では、２つの配送可能な場所が同じ建物番号、コミュニティの同じ名前、または同じ郵便番号を共有する場合であっても、差分ベクトルの大きさが所定の閾値を超える限り、それらは異なる単位エリアにグループ化されてもよい。
【００８５】
いくつかの実施形態では、ステップ４０２において、場所ベクトルを決定するための第１のニューラルネットワークモデルは以下のように、所定の場所を使用して訓練されてもよい。プロセッサ３０６は、所定の場所の各々について場所ベクトルを決定することができる。例えば、場所ベクトルの要素は、所定の場所のアドレスの属性を含むことができる。属性は例えば、街路番号、街路名、部屋番号、都市、地方又は州、又は郵便番号を含むことができる。
【００８６】
次いで、プロセッサ３０６は、第１のニューラルネットワークモデルに現在の場所の場所ベクトルを入力することによって、所定の場所の現在の場所の確率値を決定することができる。各確率値は所定の場所の１つに対応することができ、所定の場所の１つが現在の場所の直後に訪れる確率を示すことができる。次いで、プロセッサ３０６は、第１の所定の場所から始まる所定の経路の順序で、所定の場所のそれぞれについての確率値を決定することができる。現在の場所は、確率値が現在決定されている所定の場所であってもよい。
【００８７】
次に、プロセッサ３０６は、後続の場所が最高確率値に対応するかどうかを判定することができる。次の場所は、所定の経路に沿った現在の場所の直後の場所である。このステップは、第１のニューラルネットワークモデルが正しく訓練されているかどうかを測定することである。もしそれが正しく訓練されていれば、後続の場所は最高の確率値を有するのであろう。すなわち、第１のニューラルネットワークモデルは、現在の場所の後に訪れるべき次の場所として、後続の場所を正しく予測する。
【００８８】
後続の場所が最高確率値に対応しない場合、プロセッサ３０６は、第１のニューラルネットワークモデルのパラメータを更新することができる。いくつかの実施形態では、第１のニューラルネットワークモデルが少なくとも１つの隠れ層を含むことができる。パラメータは、隠れ層の各ノードに関連する重みであってもよい。更新は例えば、バックプロパゲーションを使用して実施することができる。
【００８９】
後続の場所が最高確率値に対応する場合、プロセッサ３０６は、第１のニューラルネットワークモデルに後続の場所の場所ベクトルを入力することによって、現在の場所、すなわち後続の場所に続く場所の確率値を決定することに進むことができる。このような動作は、所定の経路に沿った全ての所定の場所が処理されるまで繰り返されてもよい。それまで、第１のニューラルネットワークは所定の場所のいずれかが与えられると、第１のニューラルネットワークモデルが所定の経路に沿って訪れる次の場所を正しく予測するように、正しく訓練される。
【００９０】
所定の経路に沿った所定の場所の各々に続く場所が所定の場所の各々について第１のニューラルネットワークモデルによって決定された確率値における最高確率値に対応する場合、プロセッサ３０６は、ステップ４０４において、配送可能な場所の各々について場所ベクトルを決定するための第１のニューラルネットワークモデルを決定することができる。第１のニューラルネットワークモデルを使用することによって、プロセッサ３０６は、より高い精度およびより効率で場所ベクトルを決定することができる。
【００９１】
図６は、開示された実施形態に一致する、経路生成のための機械学習モデルを訓練する例示的なプロセス６００のフローチャートである。プロセス６００では、プロセス４００の工程４０６で生成された配送パターンを経路生成に使用することができる。
【００９２】
ステップ６０２において、プロセッサ３０６は、単位エリアの各々について、単位エリアのベクトル表現を決定する。いくつかの実施形態では、プロセッサ３０６が単位エリア内の場所のアドレスにグラフ埋め込み技法を適用することによってベクトル表現を決定することができる。グラフ埋め込み技術は高次元情報（例えば、グラフ）を低次元情報（例えば、ベクトル）にマッピングするために使用されてもよい。いくつかの実施形態では、アドレスがアドレスが訪問されたかどうかを示すタグに関連付けられてもよい。グラフ埋め込み技術は、このようなタグをアドレスの埋め込み関数に含めることができる。
【００９３】
工程６０４において、プロセッサ３０６は、所定の場所をネットワーク羅する単位エリアのための訓練配送パターンを決定する。それぞれの訓練配送パターンは、訪問順序で順序付けられた単位エリアのうちの少なくとも１つを含むことができる。訓練配送パターンは、機械学習モデルのみを訓練するために決定されてもよい。例えば、訓練配送パターンは、所定の場所のうちの少なくとも１つを含むものとして識別された全ての単位エリアから決定されてもよい。いくつかの実施形態では、訓練配送パターンが識別された単位エリアを所定の経路に沿ってグループ化することによって決定されてもよい。いくつかの実施形態では、訓練配送パターンの各々が多くても３つの単位エリアを含むことができる。
【００９４】
いくつかの実施形態では、訓練配送パターンが工程４００の工程４０４において、単位エリアと実質的に同時に決定され、記憶されてもよい。これらの実施形態では、プロセッサ３０６が工程６０４で、記憶された訓練配送パターンを取り出すことができる。
【００９５】
いくつかの実施形態では工程４０４において、プロセッサ３０６は第１のニューラルネットワークモデルを使用して、単位エリアおよび訓練配送パターンを実質的に同時に決定することができる。例えば、プロセッサ３０６はパターン接続（例えば、場所間の関係、セグメント、または他の対応）を生成するために、第１のニューラルネットワークモデルによって決定された現在の場所および以前の場所を記録することができる。
【００９６】
一例では、プロセッサ３０６が次いで、特定のパターン接続が１つまたは複数の所定の経路でどのくらいの頻度で発生するかを反映する周波数値を決定することができる。そのパターン接続が所定の値（例えば、２、３、４、または任意の正の整数）を超える頻度値に対応する場合、プロセッサ３０６は、パターン接続を受け入れ、それを使用して、訓練配送パターンを生成することができる。
【００９７】
別の例では、プロセッサ３０６が次いで、第１のニューラルネットワークモデルによって現在の場所について決定された確率値に基づいて、現在の接続を受け入れるかどうかを決定することができる。この例では現在の場所が以前の場所の後続の場所としての最高確率値に対応する場合、プロセッサ３０６は現在のコネクションを受け入れ、それを使用して訓練配送パターンを生成することができる。
【００９８】
工程６０６において、プロセッサ３０６は、それぞれの訓練配送パターンについてベクトル表現を決定する。いくつかの実施形態では、配送模様のベクトル表現が単位エリアのベクトル表現と同様であってもよい。いくつかの実施形態では、訓練配送パターンのベクトル表現がその中の単位エリアのベクトル表現を追加することによって決定されてもよい。
【００９９】
工程６０８において、プロセッサ３０６は、それぞれの訓練配送パターンについて得点を決定する。スコアは、訪問シーケンスに沿って単位エリアを訪問するための効率レベルを示すことができる。いくつかの実施形態では、プロセッサ３０６が訓練配送パターンのベクトル表現を機械学習モデルに入力することによって得点を決定することができる。いくつかの実施形態では異なる訓練配送パターンが同じ組の単位エリアを含むことができるが、異なる訪問シーケンスを有することができる。スコアの各々についてスコアを計算することによって、異なる訪問シーケンスの効率レベルを決定し、これを使用して、同じ組の単位エリアについて最も効率的な経路を決定することができる。
【０１００】
ステップ６１０において、訪問シーケンスが所定の経路と一致しない場合、プロセッサ３０６は機械学習モデルのパラメータを更新する。いくつかの実施形態では訪問シーケンスが所定の経路の任意の部分と同じでない場合、プロセッサ３０６は訪問シーケンスが所定の経路と一致しないと判定することができる。いくつかの実施形態では、機械学習モデルが第２のニューラルネットワークモデルであってもよい。いくつかの実施形態では、第２のニューラルネットワークモデルが少なくとも１つの隠れ層を含むことができる。パラメータは、隠れ層の各ノードに関連する重みであってもよい。更新は例えば、バックプロパゲーションを使用して実施することができる。
【０１０１】
工程６１２において、訓練配送パターンの全ての訪問シーケンスが所定の経路と一致する場合、プロセッサ３０６は、配送パターンを生成するための機械学習モデルを決定する。いくつかの実施形態では任意の訓練配送パターンの訪問シーケンスが所定の経路の一部と一致する場合、プロセッサ３０６は訓練配送パターンのすべての訪問シーケンスが所定の経路と一致すると判定することができる。このステップまで、機械学習モデルは、正しく訓練され得る。機械学習モデルを使用することによって、プロセッサ３０６は、より高い精度およびより効率的に配送パターンを生成することができる。
【０１０２】
いくつかの実施形態では、図４のステップ４０６で配送パターンを生成することはプロセス６００で決定された機械学習モデルを使用して実施されてもよい。例えば、プロセッサ３０６は、単位エリアを使用して候補配送パターンを決定することができる。それぞれの配送パターンは、訪問順に順序付けられた単位エリアのうちの少なくとも１つを含むことができる。このステップは、ステップ６０４と同様に実施することができる。いくつかの実施形態では、単位エリアの全ての実現可能な組み合わせが生成され、候補配送パターンとして決定されてもよい。
【０１０３】
次いで、プロセッサ３０６は、それぞれの候補配送パターンについてベクトル表現を決定することができる。いくつかの実施形態では、候補配送パターンのベクトル表現が候補配送パターン内の単位エリアのベクトル表現を追加することによって決定されてもよい。このステップは、ステップ６０６と同様に実施することができる。
【０１０４】
プロセッサ３０６は次に、候補配送パターンのベクトル表現を訓練された機械学習モデルに入力することによって、それぞれの候補配送パターンの得点を決定することができる。このステップは、ステップ６０８と同様に実施することができる。
【０１０５】
次いで、プロセッサ３０６は、所定のしきい値よりも高いスコアを有する候補配送パターンとして配送パターンを生成することができる。プロセッサ３０６（または別の装置）は図７に関して以下で説明するように、配送パターンを使用して経路を生成することができる。
【０１０６】
図７は、開示された実施形態に一致する、荷物集荷および配送のための経路生成の例示的な処理７００の流れ図である。
【０１０７】
ステップ７０２で、プロセッサ３０６は、訪問する目標場所を含むタスクデータを受信する。例えば、目標場所は、顧客の住所のような配送または集荷先であってもよい。目標場所は、処理４００の工程４０２と同じ地理的領域にあってもよい。いくつかの実施形態では、目標データが目標場所間の距離をさらに含むことができる。
【０１０８】
ステップ７０４において、プロセッサ３０６は、目標単位エリアを目標場所をカバーする単位エリアとして決定する。例えば、目標単位エリアは、目標場所のうちの少なくとも１つを含む全ての単位エリアを含むことができる。一部の実施形態では、目標単位エリア間の距離が目標場所間の距離から決定されてもよい。
【０１０９】
ステップ７０６において、プロセッサ３０６は、目標単位エリアをリンクする目標経路を決定する。配送作業員は、目標経路に沿って１回、それぞれの目標単位エリアを訪れることができる。いくつかの実施形態では、プロセッサ３０６が以下のように目標経路を決定することができる。
【０１１０】
プロセッサ３０６は、目標単位エリアをリンクする実現可能な配送パターンの少なくとも１つの組を決定することができる。いくつかの実施形態では、実現可能な配送パターンが目標場所をネットワーク羅し、所定のしきい値よりも高いスコアを有することができる、工程４０６で生成されたすべての配送パターンを含む。実現可能な配送パターンの訪問シーケンスをエンド・ツー・エンド方式でリンクすることによって、目標単位エリアを単一の候補経路でリンクすることができる。いくつかの実施形態では、単一の候補経路内の目標単位エリアを連結することができる実現可能な配送パターンの２つ以上の組合せが存在することができる。言い換えれば、目標単位エリアをリンクするための複数の候補経路があってもよい。その場合、プロセッサ３０６は、以下のように目標経路を決定することができる。
【０１１１】
次いで、プロセッサ３０６は、配送作業員が目標単位エリアを訪れるのに最短の時刻を有する実現可能な配送パターンとして目標経路を決定することができる。いくつかの実施形態では、工程７０４で決定された単位エリア間の距離に基づいて、配送作業員が目標単位エリアを訪れるために候補経路に沿って移動する期間を推定することができる。目標経路は、最も短い持続時間を有する候補経路として決定されてもよい。
【０１１２】
本開示はその特定の実施形態を参照して示され、説明されてきたが、本開示は修正なしに、他の環境において実施され得ることが理解されるのであろう。前述の説明は、例示の目的で提示されている。これは、ネットワーク羅的ではなく、開示された正確な形態または実施形態に限定されない。当業者には、開示された実施形態の明細書および実施を考慮することによって、修正および適合が明らかになるのであろう。加えて、開示された実施形態の態様はメモリに格納されるものとして説明されているが、当業者はこれらの態様が例えばハードディスクまたはCD ROM、あるいは他の形態のＲＡＭまたはＲＯＭ、ＵＳＢ媒体、ＤＶＤ、ブルーレイ、または他の光学ドライブ媒体などの二次記憶デバイスなどの他のタイプのコンピュータ可読媒体に格納されてもよいことを理解するのであろう。
【０１１３】
記載された説明および開示された方法に基づくコンピュータプログラムは、熟練した開発者の技術の範囲内である。様々なプログラムまたはプログラムモジュールは当業者に知られている技法のいずれかを使用して作成することができ、または既存のソフトウェアに関連して設計することができる。例えば、プログラムセクションまたはプログラムモジュールは、.Net Framework、.Net Compact Framework（およびVisual Basic、Ｃ などの関連言語）、Java、C++、Objective-C、HTML、HTML/AJAXの組み合わせ、XML、またはJavaアプレットを含むHTML内またはこれらの手段によって設計することができる。
【０１１４】
さらに、例示的な実施形態が本明細書で説明されてきたが、本開示に基づいて当業者によって理解されるように、同等の要素、修正、省略、組み合わせ（例えば、様々な実施形態にわたる態様の）、適応、および／または変更を有する任意のおよびすべての実施形態の範囲。クレームの限定はクレームに使用されている文言に広く基づいて解釈されるものとし、本明細書に記載されている例に限定されるものではなく、又は出願手続中に解釈されるものとする。実施例は、非排他的であると解釈されるべきである。さらに、開示された方法のステップは、ステップを並べ替えること、および／またはステップを挿入または削除することを含む、任意の方法で修正されてもよい。したがって、本明細書および実施例は単に例示的なものとみなされ、真の範囲および精神は以下の特許請求の範囲およびそれらの均等物の全範囲によって示されることが意図される。
【図１Ａ】
2021513132.tif 000003
【図１Ｂ】
2021513132.tif 000004
【図１Ｃ】
2021513132.tif 000005
【図１Ｄ】
2021513132.tif 000006
【図１Ｅ】
2021513132.tif 000007
【図２】
2021513132.tif 000008
【図３】
2021513132.tif 000009
【図４】
2021513132.tif 000010
【図５】
2021513132.tif 000011
【図６】
2021513132.tif 000012
【図７】
2021513132.tif 000013
【国際調査報告】
2021513132.tif 000014
2021513132.tif 000015