(57)【要約】【課題】より最適化した配送経路を生成する装置を提供する。【解決手段】ソース配送員が複数の配送物品を配送するために順次訪問した配送地点から構成された配送経路を受信するステップと、前記予め設定された数以上の配送経路に共通に含まれた配送地点に関する経路パターンを生成するステップと、前記経路パターンを用いて、ターゲット配送員が割り当てられた配送物品のそれぞれに対応する配送地点をどのような順に訪問するかを示す配送計画を生成するステップとを含む配送計画生成方法及び配送計画生成方法を行う配送計画生成装置が提供される。【選択図】図１
2018026086.tif 000002
【特許請求の範囲】
【請求項１】
ソース配送員が複数の配送物品を配送するために順次訪問した配送地点から構成された配送経路を受信するステップと、
予め設定された数以上の配送経路に共通に含まれた配送地点に関する経路パターンを生成するステップと、
前記経路パターンを用いて、ターゲット配送員が割り当てられた配送物品のそれぞれに対応する配送地点をどのような順に訪問するかを示す配送計画を生成するステップと、
を含む配送計画生成方法。
【請求項２】
前記経路パターンを生成するステップは、前記配送経路を分析し、配送地域に含まれた配送地点のうちどのような配送地点を最初に訪問したかを示す経路パターンを生成する、請求項１に記載の配送計画生成方法。
【請求項３】
前記経路パターンを生成するステップは、前記配送経路を分析し、配送しようとする複数の配送地点をどのような配送順に配送したかを示す経路パターンを生成する、請求項１に記載の配送計画生成方法。
【請求項４】
前記経路パターンを生成するステップは、前記配送経路を分析し、配送員の現在の位置以後に配送しようとする複数の配送地点をどのような順に配送したかを示す経路パターンを生成する、請求項１に記載の配送計画生成方法。
【請求項５】
前記経路パターンを生成するステップは、前記配送履歴に共通に含まれた配送地点から構成された集合を生成し、前記集合から導き出された配送履歴間の類似度に基づいて経路パターンを生成する、請求項１に記載の配送計画生成方法。
【請求項６】
前記配送計画を生成するステップは、前記経路パターンと配送会社サーバから受信した（ｉ）配送物品に関する配送作業、（ｉｉ）配送作業を行う前記ターゲット配送員、（ｉｉｉ）配送物品に対応する配送地点に関する配送経路のうち少なくとも１つを考慮した配送要件、又は、配送するときの配送環境を考慮して配送計画を生成する、請求項１に記載の配送計画生成方法。
【請求項７】
前記配送計画を生成するステップは、前記配送計画により決定された配送地点の配送順序を考慮して、前記配送員が配送物品を配送車両に配置する積載順序をともに生成する、請求項６に記載の配送計画生成方法。
【請求項８】
前記配送計画を生成するステップは、前記配送計画が配送要件を満足するか否か、及び前記配送計画が経路パターンに類似するか否かに応じて前記配送計画を評価することによって前記配送計画を変更する、請求項６に記載の配送計画生成方法。
【請求項９】
前記経路決定方法は、
前記ターゲット配送員に前記生成された配送計画を伝達するステップと、
前記配送計画を受信した前記ターゲット配送員の配送経路が前記配送計画と異なる場合、前記ターゲット配送員の配送経路を考慮して前記経路パターンをアップデートするステップと、
をさらに含む、請求項１に記載の配送計画生成方法。
【請求項１０】
配送会社サーバと通信する通信部と、
プロセッサと、
を含み、
前記プロセッサは、
前記配送会社サーバから、前記通信部を介してソース配送員が複数の配送物品を配送するために順次訪問した配送地点から構成された配送経路を受信し、
前記受信された配送経路及び前記配送会社サーバから受信した（ｉ）配送物品に関する配送作業、（ｉｉ）配送作業を行うターゲット配送員、（ｉｉｉ）配送物品に対応する配送地点に関する配送経路のうち少なくとも１つを考慮した配送要件、又は、配送するときの配送環境を考慮して、前記ターゲット配送員が割り当てられた配送物品のそれぞれに対応する配送地点をどのような順に訪問するかを示す配送計画を生成する、配送計画生成装置。
【請求項１１】
前記通信部は、前記配送会社サーバを介して前記生成された配送計画を前記ターゲット配送員に伝達する、請求項１０に記載の配送計画生成装置。
【請求項１２】
前記配送計画生成装置は、前記受信された配送経路を格納する配送履歴データベースをさらに含む、請求項１０に記載の配送計画生成装置。
【請求項１３】
前記プロセッサは、予め設定された数以上の配送経路に共通に含まれた配送地点に関する経路パターンを生成し、前記経路パターンを用いて前記ターゲット配送員が割り当てられた配送物品のそれぞれに対応する配送地点をどのような順に訪問するかを示す配送計画を生成する、請求項１０に記載の配送計画生成装置。
【請求項１４】
前記プロセッサは、前記配送計画が配送要件を満足するか否か、及び前記配送計画が前記経路パターンに類似するか否かに応じて前記配送計画を評価することにより前記配送計画を変更する、請求項１３に記載の配送計画生成装置。
【請求項１５】
前記プロセッサは、前記通信部を介して受信された前記ターゲット配送員の配送経路が前記配送計画と異なる場合、前記ターゲット配送員の配送経路を考慮して前記経路パターンをアップデートする、請求項１３に記載の配送計画生成装置。
【請求項１６】
前記プロセッサは、前記配送経路を分析し、配送地域に含まれた配送地点のうちどのような配送地点を最初に訪問したかを示す経路パターンを生成する、請求項１０に記載の配送計画生成装置。
【請求項１７】
前記プロセッサは、前記配送経路を分析し、配送しようとする複数の配送地点をどのような配送順に配送したかを示す経路パターンを生成する、請求項１０に記載の配送計画生成装置。
【請求項１８】
前記プロセッサは、前記配送経路を分析し、配送員の現在の位置の後に配送しようとする複数の配送地点をどのような順に配送したかを示す経路パターンを生成する、請求項１０に記載の配送計画生成装置。
【請求項１９】
前記プロセッサは、前記配送履歴に共通に含まれた配送地点から構成された集合を生成し、前記集合から導き出された配送履歴間の類似度に基づいて経路パターンを生成する、請求項１０に記載の配送計画生成装置。
【請求項２０】
前記プロセッサは、前記配送計画により決定された配送地点の配送順序を考慮して、前記配送員が配送物品を配送車両に配置する積載順序をともに生成する、請求項１０に記載の配送計画生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配送物品を配送員にどのように分配するかを決定し、配送員が分配された配送物品を配送する順序、経路を設定する装置及び方法に関する。
【背景技術】
【０００２】
運搬経路問題（Ｖｅｈｉｃｌｅ  Ｒｏｕｔｉｎｇ  Ｐｒｏｂｌｅｍ：ＶＲＰ）は複数の配送員及び複数の配送物品に対して配送物品を配送員にどのように分配するかを決定し、配送員が分配された配送物品を配送する順序及び経路をどのように設定するかに関するものである。一般に、ＶＲＰを解決するために導き出されたソリューションは、設定された経路に応じて配送員が移動した総移動距離に応じて好ましいソリューションであるか、又は不適なソリューションであるかが評価される。前記ソリューションが好ましいソリューションであるか、又は不適なソリューションであるかを評価する基準は、総移動距離の以外にも他の基準が追加される。
【０００３】
ＶＲＰを解決する最適なソリューションは、全ての場合の数を探索することにより導き出される。ただし、全ての場合の数を探索するために所要する時間は、配送員の数又は配送物品の数に応じて幾何級数的に増加する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、配送員の配送経路を学習し、配送経路を生成するために学習した結果を用いることによって、より最適化した配送経路を生成する装置及び方法を提供する。
【課題を解決するための手段】
【０００５】
本発明の一態様によると、ソース配送員が複数の配送物品を配送するために順次訪問した配送地点から構成された配送経路を受信するステップと、予め設定された数以上の配送経路に共通に含まれた配送地点に関する経路パターンを生成するステップと、前記経路パターンを用いて、ターゲット配送員が割り当てられた配送物品のそれぞれに対応する配送地点をどのような順に訪問するかを示す配送計画を生成するステップとを含む配送計画生成方法及び配送計画生成方法が記録されたコンピュータが読出し可能な記録媒体が提供される。
【０００６】
一態様によると、前記経路パターンを生成するステップは、前記配送経路を分析し、配送地域に含まれた配送地点のうちどのような配送地点を最初に訪問したかを示す経路パターンを生成する配送計画生成方法及び配送計画生成方法が記録されたコンピュータが読出し可能な記録媒体が提供される。
【０００７】
一態様によると、前記経路パターンを生成するステップは、前記配送経路を分析し、配送しようとする複数の配送地点をどのような配送順に配送したかを示す経路パターンを生成する、配送計画生成方法及び配送計画生成方法が記録されたコンピュータが読出し可能な記録媒体が提供される。
【０００８】
一態様によると、前記経路パターンを生成するステップは、前記配送経路を分析し、配送員の現在の位置以後に配送しようとする複数の配送地点をどのような順に配送したかを示す経路パターンを生成する、配送計画生成方法及び配送計画生成方法が記録されたコンピュータが読出し可能な記録媒体が提供される。
【０００９】
一態様によると、前記経路パターンを生成するステップは、前記配送履歴に共通に含まれた配送地点から構成された集合を生成し、前記集合から導き出された配送履歴間の類似度に基づいて経路パターンを生成する、配送計画生成方法及び配送計画生成方法が記録されたコンピュータが読出し可能な記録媒体が提供される。
【００１０】
一態様によると、前記配送計画を生成するステップは、前記経路パターンと配送会社サーバから受信した（ｉ）配送物品に関する配送作業、（ｉｉ）配送作業を行う前記ターゲット配送員、（ｉｉｉ）配送物品に対応する配送地点に関する配送経路のうち少なくとも１つを考慮した配送要件、又は、配送するときの配送環境を考慮して配送計画を生成する、配送計画生成方法及び配送計画生成方法が記録されたコンピュータが読出し可能な記録媒体が提供される。
【００１１】
一態様によると、前記配送計画を生成するステップは、前記配送計画により決定された配送地点の配送順序を考慮して、前記配送員が配送物品を配送車両に配置する積載順序をともに生成する、配送計画生成方法及び配送計画生成方法が記録されたコンピュータが読出し可能な記録媒体が提供される。
【００１２】
一態様によると、前記配送計画を生成するステップは、前記配送計画が配送要件を満足するか否か、及び前記配送計画が経路パターンに類似するか否かに応じて前記配送計画を評価することによって前記配送計画を変更する、配送計画生成方法及び配送計画生成方法が記録されたコンピュータが読出し可能な記録媒体が提供される。
【００１３】
一態様によると、前記経路決定方法は、前記ターゲット配送員に前記生成された配送計画を伝達するステップと、前記配送計画を受信した前記ターゲット配送員の配送経路が前記配送計画と異なる場合、前記ターゲット配送員の配送経路を考慮して前記経路パターンをアップデートするステップとをさらに含む、配送計画生成方法及び配送計画生成方法が記録されたコンピュータが読出し可能な記録媒体が提供される。
【００１４】
本発明の一態様によると、配送会社サーバと通信する通信部と、プロセッサとを含み、前記プロセッサは、前記配送会社サーバから、前記通信部を介してソース配送員が複数の配送物品を配送するために順次訪問した配送地点から構成された配送経路を受信し、前記受信された配送経路及び前記配送会社サーバから受信した（ｉ）配送物品に関する配送作業、（ｉｉ）配送作業を行うターゲット配送員、（ｉｉｉ）配送物品に対応する配送地点に関する配送経路のうち少なくとも１つを考慮した配送要件、又は、配送するときの配送環境を考慮して、前記ターゲット配送員が割り当てられた配送物品のそれぞれに対応する配送地点をどのような順に訪問するかを示す配送計画を生成する配送計画生成装置が提供される。
【００１５】
一態様によると、前記通信部は、前記配送会社サーバを介して前記生成された配送計画を前記ターゲット配送員に伝達する配送計画生成装置が提供される。
一態様によると、前記配送計画生成装置は、前記受信された配送経路を格納する配送履歴データベースをさらに含む配送計画生成装置が提供される。
【発明の効果】
【００１６】
本発明の一実施形態によると、配送員の配送経路を学習し、配送経路を生成するために学習した結果を用いることで、より最適化した配送経路を生成することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施形態に係る配送計画生成装置を含む運送管理システムの構造を示す図である。
【図２】一実施形態に係る配送計画生成装置、配送会社サーバ、及び配送員が配送計画を導き出し、配送計画により複数の配送物品を配送する動作を説明するためのフローチャートである。
【図３】一実施形態に係る配送計画生成装置が生成した配送計画の一例、及び配送計画を受信した配送員の実際の配送経路を比較した図である。
【図４】本発明の一実施形態に係る配送計画生成装置が行う動作を説明するためのフローチャートである。
【図５】本発明の一実施形態に係る配送計画生成装置が配送履歴から経路パターンを生成する動作を説明するための例示的な図である。
【図６】一実施形態に係る配送計画生成装置が配送地点を訪問した順序の類似度を測定する動作を説明するための例示的な図である。
【図７】一実施形態に係る配送計画生成装置が配送経路に共通に含まれた配送地点から配送経路の類似度を測定する動作を説明するための例示的な図である。
【図８】本発明の一実施形態に係る配送計画生成装置が配送計画及び実際の配送経路を比較して、実際の配送経路を学習する動作を説明するための例示的な図である。
【図９】本発明の一実施形態に係る配送計画生成装置の構造を概念的に示す図である。
【発明を実施するための形態】
【００１８】
本明細書に開示されている本発明の概念による実施形態に対して特定の構造的又は機能的な説明は、単に本発明の概念による実施形態を説明するための目的として例示されたものであり、本発明の概念による実施形態は様々な形態で実施され、本明細書に説明された実施形態に限定されることはない。
【００１９】
本発明の概念による実施形態は様々な変更を加えることができ、様々な形態を有し得るため、実施形態を図面に例示及び本明細書の詳細に基づいて説明する。しかし、これは本発明の概念による実施形態を特定の開示形態に限定されるものではなく、本発明の思想及び技術範囲に含まれる変更、均等物、又は、代替物を含む。
【００２０】
第１又は第２などの用語を複数の構成要素を説明するために用いることができるが、このような用語は１つの構成要素を他の構成要素から区別する目的としてのみ解釈されなければならない。例えば、第１構成要素は第２構成要素と命名することができ、同様に第２構成要素は第１構成要素にも命名することができる。
【００２１】
いずれかの構成要素が他の構成要素に「連結されて」いると言及された場合、その次の構成要素に直接的に連結されてもよく、又は中間に他の構成要素が存在することもあり得ると理解されなければならない。
【００２２】
単数の表現は、文脈上、明白に異なる意味をもたない限り複数の表現を含む。本明細書において、「含む」又は「有する」等の用語は明細書上に記載した特徴、数字、ステップ、動作、構成要素、部品又はこれらを組み合わせたものが存在することを示すものであって、１つ又はそれ以上の他の特徴や数字、ステップ、動作、構成要素、部品、又はこれを組み合わせたものなどの存在又は付加の可能性を予め排除しないものとして理解しなければならない。
【００２３】
異なる定義さがれない限り、技術的であるか又は科学的な用語を含むここで用いる全ての用語は、本実施形態が属する技術分野で通常の知識を有する者によって一般的に理解されるものと同じ意味を有する。一般的に用いられる予め定義された用語は、関連技術の文脈上で有する意味と一致する意味を有するものと解釈すべきであって、本明細書で明白に定義しない限り、理想的又は過度に形式的な意味として解釈されることはない。
【００２４】
以下、実施形態を添付する図面を参照しながら詳細に説明する。添付図面を参照して説明することにおいて、図面符号に関係なく同一の構成要素は同一の参照符号を付与し、これに対する重複説明は省略することにする。
【００２５】
図１は、本発明の一実施形態に係る配送計画生成装置１１０を含む運送管理システム（Ｔｒａｎｓｐｏｒｔａｔｉｏｎ  Ｍａｎａｇｅｍｅｎｔ  Ｓｙｓｔｅｍ：ＴＭＳ）１００の構造を示す図である。本発明の一実施形態によると、配送会社のＶＲＰを解決する配送計画生成装置１１０が提供される。配送計画生成装置１１０は配送会社のＶＲＰを解決するために、１つ以上の配送会社サーバと有線／無線ネットワークを介して接続される。図１を参照すると、配送計画生成装置１１０は配送会社サーバＡ１２１及び配送会社サーバＢ１２２に接続されている。
【００２６】
図１を参照すると、運送管理システム１００は、配送会社サーバＡ１２１及び配送会社サーバＢ１２２を含む。配送会社サーバＡ１２１及び配送会社サーバＢ１２２は、配送計画生成装置１１０が提供するサービスを必要とする主体である。配送会社サーバＡ１２１又は配送会社サーバＢ１２２は、配送に関するサービスをクライアントに提供する。例えば、配送会社サーバＡ１２１又は配送会社サーバＢ１２２は、配送サービスに関するコマースサービスを提供する。配送会社サーバＡ１２１又は配送会社サーバＢ１２２は、配送に関するサービスをクライアントに提供するために配送員と通信する。
【００２７】
配送員は配送物品をクライアントに伝達する主体であり、配送員が配送物品をクライアントに伝達する動作を配送という。配送物品は、配送の対象となる物を意味する。運送管理システム１００は１つ以上の配送員を含む。配送員は端末を用いて、配送会社サーバと有線／無線ネットワークを用いて接続され得る。端末は、スマートフォン、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｃｅ）、ラップトップ、タブレットＰＣなどを含む。図１を参照すると、配送員「Ｍ−ｎ」は、配送会社サーバＭと接続したｎ番目の配送員であることを意味する。すなわち、配送員Ａ−１及び配送員Ａ−２は配送会社サーバＡ１２１に接続され、配送員Ｂ−１は配送会社サーバ１２２に接続される。
【００２８】
配送注文は、配送物品をいずれかの時間帯に特定地域でピックアップした後、他の時間帯に他の特定地域に伝達するとの情報を含み得る。配送注文は、クライアントの要求に応じて生成される。クライアントは、配送会社サーバＡ１２１又は配送会社サーバＢ１２２に配送注文を伝達することによって、配送注文に対応して配送物品を配送することを要求し得る。
【００２９】
配送地点は、配送物品が配送される地理的な位置を意味する。配送経路は、配送員が複数の配送物品を配送するために、複数の配送物品のそれぞれに対応する少なくとも１つ以上の配送地点を順次訪問して生成された配送員の移動経路である。
【００３０】
配送会社サーバＡ１２１又は配送会社サーバＢ１２２が１つ以上の配送注文を処理する場合、１つ以上の配送物品を１つ以上の配送員に配分し、配送員の配送経路を設定しなければならない。すなわち、配送会社サーバＡ１２１及び配送会社サーバＢ１２２のそれぞれが互いに異なる配送注文を受信することで、配送会社サーバＡ１２１及び配送会社サーバＢ１２２のそれぞれに対して互いに異なるＶＲＰが発生し得る。
【００３１】
配送計画生成装置１１０は、配送会社サーバＡ１２１及び配送会社サーバＢ１２２のそれぞれのＶＲＰを解決し、配送会社サーバＡ１２１及び配送会社サーバＢ１２２に接続された配送員に配送物品を分配し、配送員の配送経路を決定する。配送員が割り当てられた配送物品のそれぞれに対応する配送地点をどのような順に訪問するかを示す配送経路を配送計画という。配送計画は、配送経路だけではなく、配送員に分配された配送物品に関する情報を含む。すなわち、配送計画生成装置１１０は、配送会社サーバＡ１２１及び配送会社サーバＢ１２２のそれぞれに所属する配送員の配送計画を決定し得る。
【００３２】
配送計画生成装置１１０は、配送会社サーバＡ１２１及び配送会社サーバＢ１２２に決定された配送計画を伝達する。配送会社サーバＡ１２１及び配送会社サーバＢ１２２は、受信された配送計画を配送員に伝達する。配送員は、端末にインストールされたアプリケーションを用いて配送計画を受信する。
【００３３】
以下では、図２を参考にして、配送計画生成装置１１０が配送計画を生成して配送員に伝達する動作をより詳細に説明する。一実施形態によると、配送計画生成装置１１０は、図２を参照して説明した動作を配送計画生成装置１１０に接続した全ての配送会社サーバ（例えば、図１に示す配送会社サーバＡ１２１及び配送会社サーバＢ１２２）及び配送会社サーバに接続した配送員（例えば、図１に示す配送員Ａ−１〜配送員Ｂ）に対して行うことができる。
【００３４】
図２は、一実施形態に係る配送計画生成装置２１０、配送会社サーバ２２０、及び配送員２３０が配送計画２５０を導き出し、配送計画２５０により複数の配送物品を配送する動作を説明するためのフローチャートである。
【００３５】
図２を参照すると、配送計画生成装置２１０は、配送会社サーバ２２０から配送要件２４０を受信する。配送要件２４０は、配送計画２５０を生成するとき考慮しなければならない条件ないし情報を意味する。配送会社サーバ２２０は、配送計画生成装置２１０に処理しなければならない配送注文及び配送を行う配送員などの配送計画２５０を生成するための情報を送信する。
【００３６】
配送要件２４０は、（ｉ）配送注文に関する情報（配送地点の位置、配送する時間帯、積載量、配送タイプなど）、（ｉｉ）配送を行う１つ以上の配送員に関する情報（最大積載量、開始位置、終了位置、開始時間、終了時間）、（ｉｉｉ）配送時に守らなければならない要件（最大積載率、配送距離、交差禁止線、最小移動距離など）、及び（ｉｖ）配送計画２５０を算出するために必要な設定値（ＧＩＳ（Ｇｅｏｇｒａｐｈｉｃ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍ）タイプ、配送先待機時間、中心拠点情報、拠点復帰の有無など）などを含む。
【００３７】
より具体的な例として、配送要件２４０は、指定された配送員に特定地域の注文を割り当てるという要件を含み得る。配送要件２４０は配送員それぞれの選好地域に関する情報を含み、選好地域に基づいて配送注文を割り当てるとの要件を含み得る。配送要件２４０として、互いに異なる２つの配送員が同じ場所を訪問しないとの要件を含み得る。配送要件２４０として、互いに異なる２つの配送員の配送計画が交差しないとの要件を含み得る。配送要件２４０は、配送員が配送計画による移動距離を最小にするとの要件を含み得る。
【００３８】
配送要件２４０は、配送員に配送物品を分配するとき考慮しなければならない要件を含む。例えば、配送要件２４０は、配送員のそれぞれに最小ｘ件以上の配送物品を割り当てるとの要件を含み得る。他の例として、配送要件２４０は、配送車両の最大積載量を超過しないように、配送員に配送物品を配分するとの要件を含み得る。
【００３９】
また、配送要件２４０は配送環境の変化により変更され得る。例えば、配送プロセス又は配送員２３０の契約が変更される場合、配送要件２４０も変更される。したがって、配送計画生成装置２１０が同じ配送注文により配送計画２５０を算出しても、時間ごと地域ごとに異なる配送計画２５０が生成されることがある。
【００４０】
配送会社サーバ２２０は、配送要件２４０と共に配送要件２４０に対してＩＤの作成要求を伝達する。配送計画生成装置２１０は要求に応じて、配送要件２４０に対するＩＤを配送会社サーバ２２０に伝達する。配送会社サーバ２２０は、受信された配送要件２４０に対するＩＤを用いて、配送計画生成装置２１０に様々な要求を伝達し得る。
【００４１】
例えば、配送会社サーバ２２０は、配送要件２４０に対するＩＤを用いて配送要件２４０を再び送信しないながら配送計画２５０を再び算出することを要求し得る。配送会社サーバ２２０は、配送要件２４０に対するＩＤを用いて配送要件２４０をアップデートし得る。さらに、配送会社サーバ２２０は、配送要件２４０に対するＩＤを用いて配送計画生成装置２１０に配送要件２４０を用いて配送計画２５０を生成することを要求し得る。
【００４２】
図２を参照すると、ステップ２１１において、配送計画生成装置２１０は、配送会社サーバ２２０の前記要求に応じて配送計画２５０を生成する。配送計画生成装置２１０は、メタヒューリスティックアルゴリズム（Ｍｅｔａｈｅｕｒｉｓｔｉｃ  Ａｌｇｏｒｉｔｈｍ）を用いて、ＶＲＰに対する最適なソリューションの近似値が配送計画２５０を生成する。より具体的に、配送計画生成装置２１０は、ＡＬＮＳアルゴリズム（Ａｄａｐｔｉｖｅ  Ｌａｒｇｅ  Ｎｅｉｇｈｂｏｒｈｏｏｄ  Ｓｅａｒｃｈ：ＡＬＮＳ  Ａｌｇｏｒｉｔｈｍ）又は遺伝的アルゴリズム（Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）を用いることができる。
【００４３】
特に、配送計画生成装置２１０は、受信された配送要件２４０により配送計画２５０を決定する。配送計画生成装置２１０は、配送計画２５０が配送要件２４０に適しないかに応じて、配送計画２５０に付されるペナルティを決定するペナルティ関数を生成し得る。配送計画２５０の集合をＰとすれば、配送要件ｆは数式（１）のように定義される。
【００４４】
【数１】
2018026086.tif 000003
数式（１）を参照すると、ペナルティ関数は配送計画２５０から配送計画２５０に付与される実数のペナルティを出力する。ペナルティが高いほど配送計画２５０が配送要件２４０を満足しないことを意味する。
【００４５】
例えば、配送要件２４０が配送員２３０に最小３０件の配送物品を割り当てるとの要件を含む場合、配送員２３０の集合Ｄに対して、配送計画生成装置２１０は配送要件２４０から数式（２）のペナルティ関数を生成する。
【００４６】
【数２】
2018026086.tif 000004
配送計画生成装置２１０は、生成したペナルティ関数を用いて配送計画２５０を評価する。配送計画生成装置２１０が数式（２）のペナルティ関数を用いて５人の配送員の配送計画２５０を評価すると仮定する。５人のうち２人の配送員がそれぞれ２２個と２５個の配送物品が配分された場合、数式（２）を参照すると、配送計画２５０のペナルティは配送員それぞれのペナルティを全て和して、ｆ（ｐ）＝０＋０＋０＋ｍａｘ（０、３０−２２）＋ｍａｘ（０、３０−２５）＝８＋５＝１３になる。算出されたペナルティを用いて、配送計画生成装置２１０は、１３よりも低いペナルティを有するように配送計画２５０を修正する。これによって、配送計画生成装置２１０は、配送要件２４０に適する配送計画２５０を生成することができる。
【００４７】
更なる例として、配送要件２４０が配送員２３０それぞれの配送経路の長さが１０ｋｍ以下にならなければならないとの要件を含む場合、配送員２３０の集合Ｄに対して、配送計画生成装置は配送要件２４０から数式（３）のようなペナルティ関数を生成する。
【００４８】
【数３】
2018026086.tif 000005
配送要件２４０が互いに異なるｎ個の要件を含む場合、配送計画２５０に対するペナルティは互いに異なるｎ個の要件から生成されたｎ個のペナルティ関数それぞれに加重値を乗算した和に決定される。したがって、配送計画２５０に対するペナルティは数式（４）により決定される。
【００４９】
【数４】
2018026086.tif 000006
例えば、配送要件２４０が（ｉ）配送員２３０に最小３０件の配送物品を割り当てるとの要件及び（ｉｉ）配送員２３０それぞれの配送経路の長さが１０ｋｍ以下でなければならないとの要件を含んでいる場合、配送計画２５０に対するペナルティは数式（２）及び数式（３）のそれぞれに加重値を乗算した和によって決定され得る。
【００５０】
数式（４）を参照すると、配送計画生成装置２１０は新しい配送要件２４０を自由に追加することができ、配送要件２４０を自由に変更し得る。また、配送要件２４０のそれぞれが独立的に結合され得るため、配送要件２４０のそれぞれは容易にモジュール化される。したがって、配送計画生成装置２１０は、配送環境の急激な変化により柔軟に対応できる。さらに、配送計画生成装置２１０は、互いに異なる配送要件２４０を要求する配送会社サーバのそれぞれについて容易に対応できる。
【００５１】
配送計画生成装置２１０は、ペナルティが減少するよう配送計画２５０を修正し、配送要件２４０を満足する配送計画２５０を決定する。配送計画生成装置２１０は、決定された配送計画２５０を出力する。より具体的に、配送計画生成装置２１０は、配送会社サーバ２２０に配送計画２５０に対するＩＤを伝達する。配送会社サーバ２２０は、配送計画２５０に対するＩＤを用いて配送計画２５０にアクセスする。配送会社サーバ２２０は、配送員２３０が携帯した端末を介して配送員２３０に配送計画２５０を伝達する。
【００５２】
図２を参照すると、ステップ２３１において、配送員２３０は、受信した配送計画２５０により配送地点を訪問して配送を行う。配送計画生成装置２１０は、配送員２３０の配送経路を学習し得る。すなわち、配送計画生成装置２１０は、配送計画２５０を受信した配送員２３０が実際に配送した配送経路を受信して学習することができる。
【００５３】
図３は、一実施形態に係る配送計画生成装置が生成した配送計画３１０の一例、及び配送計画３１０を受信した配送員の実際の配送経路３２０を比較した図である。配送会社サーバが配送計画生成装置に、配送員にとって５個の配送物品を互いに異なる５個の配送地点（Ａ〜Ｅ）に配送するように配送計画３１０の生成を要求したと仮定する。図３を参照すると、配送計画生成装置は、配送要件を考慮して５個の配送地点をＡ、Ｂ、Ｃ、Ｄ、Ｅの順に連結して配送計画３１０を生成する。
【００５４】
図３を参照すると、配送員は配送計画３１０を受信したにもかかわらず、配送計画３１０とは別に５個の配送地点をＡ、Ｂ、Ｃ、Ｅ、Ｄの順に訪問する。すなわち、配送員の実際の配送経路３２０は配送計画３１０と異なることもある。配送員は、携帯した端末を用いて配送計画３１０に含まれた配送経路の全て又は一部を変更し得る。配送員の端末は、配送会社サーバに変更された配送計画３１０を伝達する。また、配送員の端末は、ＧＰＳ装置を用いて配送員の配送経路をリアルタイム追跡した後、配送会社サーバに追跡した配送員の配送経路を伝達する。
【００５５】
これによって、配送会社サーバは、実際の配送経路３２０を収集できる。配送会社サーバは、配送会社に所属している１つ以上の配送員の配送経路を追跡及び管理できる。さらに、配送会社サーバは、収集された実際の配送経路３２０を配送計画生成装置に伝達する。配送計画生成装置は、受信した実際の配送経路３２０を学習し得る。学習された実際の配送経路３２０は、新しい配送計画を生成するために用いられる。
【００５６】
再び図２を参照すると、配送員２３０の変更された配送経路２７０が配送会社サーバ２２０に伝えられる。配送員２３０の端末は、配送計画２５０と配送員２３０の移動経路とを比較し、変更された配送経路２７０を導き出すことができる。配送会社サーバ２２０は、変更された配送経路２７０を配送計画生成装置２１０に伝達する。より具体的に、配送会社サーバ２２０は、受信した配送計画２５０に対するＩＤを用いて配送計画生成装置２１０に配送員２３０が配送計画２５０とは相違に変更された配送経路２７０に沿って配送物品を配送したことを知らせる。
【００５７】
図２を参照すると、ステップ２１２において、配送計画生成装置２１０は、変更された配送経路２７０を学習する。変更された配送経路２７０を学習した結果は、配送計画生成装置２１０に含まれた記憶装置に蓄積される。図２に示す動作が繰り返し実行されることにより、配送計画生成装置２１０は配送員２３０の配送経路を続けて収集し得る。さらに、配送計画生成装置２１０は、接続された１つ以上の配送会社サーバから配送会社サーバそれぞれに所属している配送員の配送経路を収集し得る。配送員２３０が過去に配送物品を実行しながら生成した配送経路を配送計画２５０と区分して配送履歴と呼ぶ。配送計画生成装置２１０は、送計画２５０の生成に前もって配送会社サーバ２２０から配送履歴を受信し得る。
【００５８】
図４は、本発明の一実施形態に係る配送計画生成装置が行う動作を説明するためのフローチャートである。以下では、図４を参考して配送計画生成装置が配送履歴を収集し、収集した配送履歴により配送計画を生成する動作について説明する。
【００５９】
一実施形態によると、配送計画生成方法を実行するためのプログラムが記録されたコンピュータで読み出し可能な記録媒体が提供される。前記プログラムは、配送計画生成方法を格納したアプリケーション、デバイスドライバ、ファームウェア、ミドルウェア、動的リンクライブラリー（ＤＬＬ）、及びアプレットのうち少なくとも１つを含む。本発明の一実施形態によると、配送計画生成装置はプロセッサを含み、プロセッサは、配送計画生成方法の記録された記録媒体を読み出すことによって、図４に示された動作を行うことができる。さらに、配送計画生成装置は、クラウドサーバの形態で運送管理システムに含まれ得る。
【００６０】
図４を参照すると、ステップＳ４１０において、一実施形態に係る配送計画生成装置は、配送会社サーバから配送履歴を受信する。言い換えれば、配送履歴により配送物品を配送した配送員をソース配送員とすると、配送計画生成装置は、ソース配送員が複数の配送物品を配送するために順に訪問した配送地点から構成された配送経路を受信する。また、配送履歴は、ソース配送員が複数の配送物品のそれぞれに対応する配送地点を訪問した順序又は訪問した時間に関する情報が含まれ得る。
【００６１】
図４を参照すると、ステップＳ４２０において、一実施形態に係る配送計画生成装置は配送履歴を分析し、配送履歴から経路パターンを生成する。より具体的に、配送計画生成装置は、予め設定された数以上の配送経路に共通に含まれた配送地点に関する経路パターンを生成する。配送計画生成装置は、複数の配送履歴に共通に含まれた配送地点を探知する。さらに、配送計画生成装置は、共通に含まれた配送地点が配送履歴にどのような順に含まれているかを探知する。配送計画生成装置は、探知した結果を用いて配送履歴のパターンを探知し得る。
【００６２】
経路パターンは様々な方法で生成される。配送計画生成装置は配送経路を分析し、配送地域に含まれた配送地点のうちどのような配送地点を最初に訪問したかを示す経路パターンを生成する。例えば、配送員が瑞草区に配送する場合、配送計画生成装置は数多い配送員が良才洞を最初に訪問したことが探知される。配送計画生成装置はこれを用いて、瑞草区に対する配送経路を生成するとき、良才洞を最初の訪問先として指定できる。
【００６３】
配送計画生成装置は配送経路を分析し、配送しようとする複数の配送地点をどのような配送順に配送したかを示す経路パターンを生成する。配送計画生成装置は配送経路を分析し、配送員の現在の位置の後に配送しようとする複数の配送地点をどのような順に配送したかを示す経路パターンを生成する。配送計画生成装置が配送順序を考慮して経路パターンを生成する動作については後でより詳しく説明する。また、配送計画生成装置は、配送履歴に共通に含まれた配送地点から構成された集合を生成し、集合から導き出された配送履歴間の類似度に基づいて経路パターンを生成することができる。
【００６４】
さらに、配送計画生成装置は、配送履歴の時間帯を考慮して経路パターンを生成する。例えば、配送計画生成装置は、出退勤時間帯の配送経路又は配送時間が深夜時間帯の配送経路又は配送時間と異なることを考慮して経路パターンを生成し得る。他の例として、配送計画生成装置は、土曜日及び日曜日の配送経路又は配送時間が月曜日ないし金曜日の配送経路又は配送時間と異なることを考慮して経路パターンを生成し得る。配送計画生成装置は、配送計画に対応する時間帯の経路パターンのみを用いて配送計画を生成し得る。
【００６５】
図４を参照すると、ステップＳ４３０において、一実施形態に係る配送計画生成装置は、経路パターンを用いてターゲット配送員が割り当てられた配送物品のそれぞれに対応する配送地点をどのような順に訪問するかを示す配送計画を生成する。すなわち、配送計画は、ソース配送員の共通の配送経路を含む。ターゲット配送員は、配送計画を行う配送員を意味する。ソース配送員と区分するためにターゲット配送員という用語を用いたが、ソース配送員及びターゲット配送員は互いに異なる配送員を意味することはない。すなわち、ターゲット配送員は、ソース配送員の全て又は一部であってもよく、配送履歴を提供したソース配送員も配送計画が必要な場合にターゲット配送員になり得る。
【００６６】
配送計画生成装置は公開されたＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｉｎｔｅｒｆａｃｅ）によって配送会社サーバにサービスを提供する。配送計画生成装置は、配送会社サーバからＡＰＩを介して配送計画を決定するために必要な情報を受信する。先に説明したように、配送計画を決定するために必要な情報は配送要件を含む。
【００６７】
配送計画生成装置は、受信された配送要件からペナルティ関数を生成し、生成されたペナルティ関数を用いて配送計画が配送要件に適するかを評価する。配送計画生成装置は、評価された結果に応じて配送計画を修正する。さらに、配送計画生成装置は、配送環境を考慮して配送計画を生成する。
【００６８】
また、配送計画生成装置は、経路パターンについても配送計画が経路パターンに類似するかを判断し、配送計画が経路パターンに類似しないほど配送計画に高いペナルティを付与するペナルティ関数を生成する。すなわち、配送計画生成装置は、経路パターンを配送要件と類似方式により配送計画を評価することに用いられる。配送計画生成装置は、配送計画が配送要件を満足するか否か、及び配送計画が経路パターンに類似するか否かに応じて配送計画を評価することで配送計画を変更し得る。これにより、配送計画は配送要件を満足しながらも経路パターンと類似に変更され得る。
【００６９】
合わせると、配送計画生成装置は、経路パターンと配送会社サーバから受信した（ｉ）配送物品に関する配送作業、（ｉｉ）配送作業を行うターゲット配送員、（ｉｉｉ）配送物品に対応する配送地点に関する配送経路のうち少なくとも１つを考慮した配送要件、又は、配送するときの配送環境を考慮して配送計画を生成することができる。
【００７０】
追加的に、配送計画生成装置は、配送計画によって決定された配送地点の配送順序を考慮してターゲット配送員が配送物品を配送車両に配置する積載順序を配送計画と共に生成し得る。すなわち、積載順序は、配送車両の最も内側に配送計画により最後に訪問する配送地点に対応する配送物品を配置し、最も外側には最初に訪問する配送地点に対応する配送物品を配置するよう決定される。
【００７１】
図４を参照すると、ステップＳ４４０において、一実施形態に係る配送計画生成装置は、ターゲット配送員に生成された配送計画を伝達する。配送会社サーバは、ＡＰＩを介して配送計画生成装置から配送計画を受信し、受信された配送計画をターゲット配送員が携帯した端末に送信する。ターゲット配送員は、携帯した端末を介して受信された配送計画を確認する。配送計画生成装置が配送計画と共に生成された積載順序を伝達した場合、ターゲット配送員は携帯した端末を用いて積載順序まで確認することができる。ターゲット配送員は、携帯した端末を用いて配送計画又は積載順序を修正し得る。
【００７２】
図４を参照すると、ステップＳ４５０において、一実施形態に係る配送計画生成装置は、配送計画を受信したターゲット配送員の配送経路が配送計画と異なる場合、ターゲット配送員の配送経路を考慮して経路パターンをアップデートする。ターゲット配送員が携帯した端末を用いて配送計画又は積載順序を修正した場合、端末は、修正された配送計画又は積載順序を配送会社サーバに伝達する。修正された配送計画又は積載順序は、配送会社サーバを介して配送計画生成装置に伝えられる。
【００７３】
また、ターゲット配送員の端末は、ターゲット配送員の配送経路を追跡し得る。端末はターゲット配送員の配送経路を配送会社サーバに伝達し、配送会社サーバはターゲット配送員の配送経路を配送計画生成装置に伝達する。配送計画生成装置は、受信されたターゲット配送員の配送経路を配送計画と比較して、ターゲット配送員の配送経路が配送計画と異なるかを確認する。配送計画生成装置は、ターゲット配送員の配送経路をソース配送員の配送履歴と同一に取り扱うことができ、その後、経路パターンを生成するためにターゲット配送員の配送経路を用いることができる。
【００７４】
したがって、配送計画生成装置は、配送計画を活かしながら配送計画に対応して生成された配送履歴を続けて収集し得る。配送計画生成装置は、収集された配送履歴により経路パターンを持続的にアップデートする。言い換えれば、配送計画生成装置は、収集された配送履歴を学習できる。したがって、配送計画生成装置は、配送履歴を収集するにつれてより最適化した配送計画を生成することができる。
【００７５】
図５は、本発明の一実施形態に係る配送計画生成装置が配送履歴から経路パターンを生成する動作を説明するための例示的な図である。図５を参照すると、配送計画生成装置が１つ以上の配送会社サーバから収集した７個の配送履歴が示されている。説明の便宜のために、図５は、配送履歴に含まれた配送地点のみを配送順に羅列して図示する。配送計画生成装置は、配送地点をＧＰＳ座標、行政区域単位（県、市、区、町、村、洞など）又は郵便番号を用いて分類する。図５は、配送計画生成装置が洞の単位で配送地点を分類した一例を示す。説明の便宜のために、図５において説明と関連のない一部の配送地点は省略した。
【００７６】
一実施形態によると、配送計画生成装置は配送経路を分析し、配送しようとする複数の配送地点をどのような配送順に配送したかを示す経路パターンを生成する。すなわち、配送地点Ａ、配送地点Ｂ、及び配送地点Ｃが順に配送経路に含まれる場合、配送計画生成装置は配送員が配送地点Ａ、配送地点Ｂ、及び配送地点Ｃの順に配送することを学習する。配送計画生成装置は、全体の配送員のうち配送地点Ａ、配送地点Ｂ、及び配送地点Ｃの順に配送した配送員の比率を考慮して経路パターンを生成し得る。
【００７７】
図５を参照すると、７個の配送履歴のうち５個の配送履歴（配送履歴１、２、３、５、６）に対応する配送員が道谷洞、大峙洞、三成洞の順に配送したことが確認される。したがって、配送計画生成装置は、道谷洞、大峙洞、三成洞の順に配送計画を生成するよう、経路パターン（１）５１０を生成する。配送計画生成装置は、経路パターン（１）５１０を考慮して配送計画を生成する。すなわち、配送計画生成装置は、配送地点に大峙洞、道谷洞、及び三成洞が含まれた場合、道谷洞、大峙洞、三成洞の順に配送地点を設定して配送計画を生成し得る。
【００７８】
配送計画生成装置は、経路パターン（１）５１０に経路パターン（１）５１０の信頼度又は経路パターン（１）５１０の根拠に関する情報が含まれ得る。図５を参照すると、経路パターン（１）５１０は、道谷洞、大峙洞、三成洞の順に配送された配送経路が５回出現したことを示す情報（Ｓｕｐｐｏｒｔ５）を含む。配送計画生成装置が道谷洞、大峙洞、三成洞の順に配送された配送経路を含む新しい配送履歴を受信した場合、経路パターン（１）５１０の前記情報をＳｕｐｐｏｒｔ６に修正する。
【００７９】
経路パターン（１）５１０に含まれた信頼度又は根拠に関する情報は、経路パターン（１）５１０をアップデートするとき用いられる。例えば、以後に大峙洞、三成洞、道谷洞の順に配送された配送経路が７回以上出現した場合、経路パターン（１）５１０の出現回数を超過するため、配送計画生成装置は経路パターン（１）５１０の順序を大峙洞、三成洞、道谷洞の順に修正したり、又は、経路パターン（１）５１０を除去する。
【００８０】
配送計画生成装置は、複数の経路パターン間の関係を用いて経路パターンを生成したり又はアップデートする。図５を参照すると、道谷洞、大峙洞、三成洞の順に配送した５個の配送履歴のうち、三成洞の以後に新沙洞を訪問した配送履歴が３個であることが確認される。配送計画生成装置は、経路パターン（１）５１０を考慮して、経路パターン（１）５１０に類似の５個の配送履歴のうち、道谷洞、大峙洞、三成洞、新沙洞の順序の配送経路が６０％の確率に出現したことを表示した経路パターン（２）５２０を生成する。配送計画生成装置は、配送履歴を続けて受信して経路パターン（２）５２０の経路パターン（１）５１０に対する出現確率が予め設定された確率を超過する場合、経路パターン（１）５１０をアップデートしたり又は除去する。
【００８１】
一実施形態によると、配送計画生成装置は配送経路を分析し、配送員の現在位置の以後に配送しようとする複数の配送地点をどのような順に配送したかを示す経路パターンを生成し得る。すなわち、配送員が現在の配送地点Ａに位置し、その次配送経路に配送地点Ｂ、配送地点Ｃ、及び配送地点Ｄが含まれた場合、配送計画生成装置は、配送員が配送地点Ｂ、配送地点Ｃ、及び配送地点Ｄの順に訪問することを学習する。
【００８２】
図５を参照すると、配送履歴１、２、３、５、６に対応する配送員が現在道谷洞に位置し、その次の配送地点に大峙洞及び三成洞が含まれている場合、大峙洞、三成洞の順に配送したことが確認される。したがって、配送計画生成装置は、配送員が現在道谷洞に位置し、その次の配送地点に大峙洞及び三成洞が含まれている場合、大峙洞、三成洞の順に配送を行うよう経路パターン（１）５１０を生成し得る。
【００８３】
配送計画生成装置は、配送地点Ａ及び配送地点Ｂを順に含む複数の配送経路に対して、配送地点Ａ及び配送地点Ｂの間に予め設定された数以下の他の配送地点が含まれても、複数の配送経路で配送地点Ａ及び配送地点Ｂの順に配送が実行されたことを探知する。図５を参照すると、配送履歴１は、道谷洞及び大峙洞の間に２個の任意の配送地点を含み、配送履歴６は、道谷洞及び大峙洞の間に３個の任意の配送地点を含む。配送計画生成装置は、配送履歴１及び配送履歴６それぞれの道谷洞及び大峙洞の間の配送地点が互いに異なっても、配送履歴１及び配送履歴６で道谷洞、大峙洞の順に配送されたことが探知される。
【００８４】
上述したように、配送計画生成装置は、予め設定された数以上の配送経路に共通して含まれた配送地点及び配送地点を訪問した順序を用いて経路パターンを生成することができる。さらに、配送計画生成装置は、配送地点を訪問した順序の類似度を考慮して経路パターンを生成することができる。
【００８５】
図６は、一実施形態に係る配送計画生成装置が配送地点を訪問した順の類似度を測定する動作を説明するための例示的な図である。配送計画生成装置が配送経路（１）６１０を基準として、配送経路（１）６１０と残りの配送経路（２）６２０、配送経路（３）６３０、及び配送経路（４）６４０の間の配送地点を訪問した順の類似度を測定するものと仮定する。
【００８６】
図６を参照すると、配送経路（１）６１０、配送経路（２）６２０、配送経路（３）６３０、及び配送経路（４）６４０は、共通した配送地点Ａ〜配送地点Ｄを含んでいる。配送経路（１）６１０、配送経路（２）６２０、配送経路（３）６３０、及び配送経路（４）６４０は、配送履歴の全て又は一部であり得る。配送計画生成装置は、複数の配送履歴のうち配送地点Ａ〜配送地点Ｄを含む配送経路（１）６１０、配送経路（２）６２０、配送経路（３）６３０、及び配送経路（４）６４０を抽出した後、配送地点Ａ〜配送地点Ｄを訪問した順の類似度を測定する。測定された類似度は、経路パターンを生成するために用いられる。
【００８７】
より具体的に、配送計画生成装置は、配送経路に含まれた配送地点の間の移動を１：１マッチングすることで配送経路の類似度を測定し得る。配送計画生成装置は、数式（５）の経路類似度を算出することによって配送経路の類似度を測定する。
【００８８】
【数５】
2018026086.tif 000007
配送計画生成装置は配送経路を学習したり、又は配送計画を生成することに経路類似度を用いることができる。前述したように、配送計画生成装置は、経路類似度が最も高い配送経路を用いて経路パターンを生成し得る。また、配送計画生成装置は、経路類似度を用いて配送計画が経路パターンとどれ程類似するかを測定し得る。さらに、配送計画生成装置は、経路類似度が増加するように配送計画を修正し得る。したがって配送計画生成装置は、経路パターンと類似の配送計画を生成することができる。
【００８９】
一実施形態によると、配送計画生成装置は、配送経路に共通に含まれた配送地点の個数を用いて配送経路の類似度を測定し得る。図７は、一実施形態に係る配送計画生成装置が配送経路に共通に含まれた配送地点から配送経路の類似度を測定する動作を説明するための例示的な図である。配送計画生成装置は、配送履歴に共通に含まれた配送地点から構成された集合を生成し、集合から導き出された配送履歴間の類似度に基づいて経路パターンを生成し得る。
【００９０】
より具体的に、配送計画生成装置は、配送履歴に対応する集合を生成する。図７を参照すると、配送計画生成装置は、配送履歴１７１０に含まれた配送地点を要素にする集合Ｓ１＝｛Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｚ｝を生成し、配送履歴（２）７２０に含まれた配送地点を要素にする集合Ｓ２＝｛Ａ、Ｘ、Ｙ、Ｄ、Ｃ、Ｅ、Ｕ、Ｚ｝を生成する。
【００９１】
配送計画生成装置は、集合Ｓ１及びＳ２の和集合及び積集合を用いて配送履歴間の類似度を算出する。配送計画生成装置は、Ｊａｃｃａｒｄの類似度を用いて数式（６）により集合Ｓ１及びＳ２の類似度を算出する。
【００９２】
【数６】
2018026086.tif 000008
配送計画生成装置は、配送地点の重要度を考慮して配送履歴間の類似度を算出する。例えば、配送計画生成装置は、配送履歴がより多くの人口密接地域又は拠点となる配送地点を共通して含むほど類似度はさらに高く算出される。より具体的に、配送計画生成装置は、配送地点ｋの重要度であるＷｋを考慮して数式（７）により集合Ｓ１及びＳ２の類似度を算出することができる。
【００９３】
【数７】
2018026086.tif 000009
配送計画生成装置は、数式（６）又は数式（７）により配送経路間の類似度を測定し、これを経路パターンを生成したり、又は配送計画を評価するために用いられる。すなわち、配送計画生成装置は、配送履歴に共通に含まれた配送地点から、数式（６）又は数式（７）により配送履歴の類似度を測定し、これを用いて予め設定された類似度以上の配送経路を用いて経路パターンを生成し得る。
【００９４】
また、配送計画生成装置は、数式（６）又は数式（７）により配送計画が経路パターンとどれ程度適するかを測定し得る。配送計画生成装置は、配送計画及び経路パターン間の類似度が増加するように配送計画を修正する。例えば、数式（７）を考慮して、配送計画生成装置は、重要度の高い配送地点を配送計画に追加し得る。これによって、配送計画は経路パターンと類似に決定され得る。
【００９５】
図８は、本発明の一実施形態に係る配送計画生成装置が配送計画８１０及び実際の配送経路８２０を比較して、実際の配送経路８２０を学習する動作を説明するための例示的な図である。配送員は、受信した配送計画８１０とは相違に配送地点に訪問することができ、配送員の実際の配送経路８２０と配送計画８１０が変わり得る。配送計画生成装置は、図２〜図４を参照して説明した動作を行って実際の配送経路８２０を受信し得る。
【００９６】
図８を参照すると、一実施形態に係る配送計画生成装置は、郵便番号を用いて配送経路を分析する。配送計画生成装置は、経路パターンＰ（１）８３０を用いて配送計画８１０を生成する。経路パターンＰ（１）８３０は、配送地点の郵便番号が１８１５１、１８１４７及び１８１４３である場合、予め設定された数以上の配送員が１８１５１、１８１４７及び１８１４３の順に配送したことを示す。図８を参照すると、配送計画８１０に含まれた配送地点は１８１５０、１８１５１、１７７０９、１８１４７、１８１４３及び１８１４５に順に設定され、１８１５１、１８１４７及び１８１４３の順の経路パターンＰ（１）８３０を満足していることが確認される。
【００９７】
図８を参照すると、配送員は配送計画８１０とは相違に配送したことが分かる。特に、経路パターンＰ（１）８３０に対して、配送員は郵便番号が１８１５１、１８１４７及び１８１４３である配送地点に対して１８１４３、１８１４７及び１８１５１の順に配送したことが確認される。配送計画生成装置は、配送計画８１０及び実際の配送経路８２０を比較して、１８１４３、１８１４７及び１８１５１の順に配送したことを示す経路パターンＰ（２）８４０及び経路パターンＰ（１）８３０間の関係を決定する。図８を参照すると、配送計画生成装置は、経路パターンＰ（１）８３０が１１人の配送履歴に共通に含まれたものであって（Ｓｕｐｐｏｒｔ１１）、経路パターンＰ（１）８３０により生成された配送計画８１０を提供された４人の配送員が全て経路パターンＰ（２）８４０に沿って配送したことを表示（Ｃｏｎｆｉｄｅｎｃｅ１．０）する。
【００９８】
配送計画生成装置は、経路パターンＰ（１）８３０を経路パターンＰ（２）８４０に修正する配送員の数が予め設定された数を超過すると、経路パターンＰ（１）８３０をアップデートしたり、又は除去する。これにより、配送計画生成装置は、実際の配送経路８２０を学習することができる。
【００９９】
図９は、本発明の一実施形態に係る配送計画生成装置９１０の構造を概念的に示す図である。図９を参照すると、配送計画生成装置９１０は、配送会社サーバ９６０と通信する通信部９３０及びプロセッサ９２０を含む。
【０１００】
プロセッサ９２０は、配送会社サーバ９６０から通信部９３０を介してソース配送員が複数の配送物品を配送するために順次訪問した配送地点で構成された配送経路を受信する。配送計画生成装置９１０は、プロセッサ９２０を用いて受信された配送経路から予め設定された数以上の配送経路に共通に含まれた配送地点に関する経路パターンを抽出し得る。
【０１０１】
一実施形態によると、配送計画生成装置９１０は、受信された配送経路を格納する配送履歴データベース９４０を含む。配送計画生成装置９１０は、抽出された経路パターンを配送履歴データベース９４０に格納する。配送会社サーバ９６０が配送計画を生成することを要求した場合、配送計画生成装置９１０は、配送履歴データベース９４０に格納された情報を使用できる。
【０１０２】
配送計画生成装置９１０は、通信部９３０を介して配送会社サーバ９６０から配送計画を生成するために考慮しなければならない配送要件を受信する。配送要件は、（ｉ）配送物品に関する配送作業、（ｉｉ）配送作業を行う前記ターゲット配送員、（ｉｉｉ）配送物品に対応する配送地点に関する配送経路のうち少なくとも１つを考慮して生成される。配送計画生成装置９１０は、配送会社サーバ９６０から受信された配送要件にＩＤを付与する。
【０１０３】
配送計画生成装置９１０は、プロセッサ９２０を用いて配送経路、配送要件又は配送するときの配送環境を考慮し、ターゲット配送員が割り当てられた配送物品のそれぞれに対応する配送地点をどのような順に訪問するかを示す配送計画を生成する。配送計画生成装置９１０は、配送計画を生成するとき使用されるＧＩＳデータベース９５０を含む。
【０１０４】
配送計画生成装置９１０が配送計画が配送要件に適するかを評価するペナルティ関数を用いて配送計画を生成することについては前述した通りである。配送計画生成装置９１０は、数式（５）ないし数式（７）を用いて経路パターンと配送計画が適するかを考慮して配送計画を生成する。配送会社サーバ９６０は、配送要件に付与されたＩＤを用いて、配送計画生成装置９１０が配送要件を生成する動作を追跡する。さらに、配送会社サーバ９６０は、配送計画生成装置９１０に配送要件を生成することを中断することを要求する。
【０１０５】
図９を参照すると、通信部９３０は、前記配送会社サーバ９６０を介して生成された配送計画をターゲット配送員に伝達する。言い換えれば、配送計画生成装置９１０は、通信部９３０を介して生成された配送計画を配送会社サーバ９６０に伝達し、配送会社サーバ９６０は、配送計画をターゲット配送員の端末９７０に伝達する。端末９７０は、ターゲット配送員が配送計画とは相違に配送地点を訪問した場合、実際の配送経路を配送会社サーバ９６０を介して配送計画生成装置９１０に伝達し得る。
【０１０６】
配送計画生成装置９１０は、プロセッサ９２０によって実際の配送経路を学習する。受信されたターゲット配送員の実際の配送経路は、配送履歴データベース９４０に格納される。配送計画生成装置９１０は、数式（５）ないし数式（７）を用いて実際の配送経路が経路パターンにどれ程適するかを評価し、これを用いて経路パターンをアップデートすることができる。これによって、配送計画生成装置９１０は継続的に配送経路を学習することができ、配送経路の学習により一層最適化した配送計画を生成することができる。
【０１０７】
上述した装置は、ハードウェア構成要素、ソフトウェア構成要素、又はハードウェア構成要素及びソフトウェア構成要素の組合せで具現される。例えば、本実施形態で説明した装置及び構成要素は、例えば、プロセッサ、コントローラ、ＡＬＵ（ａｒｉｔｈｍｅｔｉｃ  ｌｏｇｉｃ  ｕｎｉｔ）、デジタル信号プロセッサ（ｄｉｇｉｔａｌ  ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｏｒ）、マイクロコンピュータ、ＦＰＡ（ｆｉｅｌｄ  ｐｒｏｇｒａｍｍａｂｌｅ  ａｒｒａｙ）、ＰＬＵ（ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  ｕｎｉｔ）、マイクロプロセッサー、又は命令（ｉｎｓｔｒｕｃｔｉｏｎ）を実行して応答する異なる装置のように、１つ以上の汎用コンピュータ又は特殊目的コンピュータを用いて具現される。処理装置は、オペレーティングシステム（ＯＳ）及びオペレーティングシステム上で実行される１つ以上のソフトウェアアプリケーションを実行する。また、処理装置は、ソフトウェアの実行に応答してデータをアクセス、格納、操作、処理、及び生成する。理解の便宜のために、処理装置は１つが使用されるものとして説明する場合もあるが、当該技術分野で通常の知識を有する者は、処理装置が複数の処理要素（ｐｒｏｃｅｓｓｉｎｇ  ｅｌｅｍｅｎｔ）及び／又は複数類型の処理要素を含むことが分かる。例えば、処理装置は、複数のプロセッサ又は１つのプロセッサ及び１つのコントローラを含む。また、並列プロセッサ（ｐａｒａｌｌｅｌ  ｐｒｏｃｅｓｓｏｒ）のような、他の処理構成も可能である。
【０１０８】
ソフトウェアは、コンピュータプログラム、コード、命令、又はこれらのうちの１つ以上の組合せを含み、希望通りに動作するように処理装置を構成し、独立的又は結合的に処理装置に命令する。ソフトウェア及び／又はデータは、処理装置によって解釈され、処理装置に命令又はデータを提供するためのあらゆる類型の機械、構成要素、物理的装置、仮想装置、コンピュータ格納媒体又は装置、或いは送信される信号波を介して永久的又は一時的に具現化される。ソフトウェアは、ネットワークに接続されたコンピュータシステム上に分散され、分散された方法で格納されるか又は実行される。ソフトウェア及びデータは１つ以上のコンピュータ読み取り可能な記録媒体に格納される。
【０１０９】
本実施形態による方法は、多様なコンピュータ手段を介して実施されるプログラム命令の形態で具現され、コンピュータ読み取り可能な記録媒体に記録される。記録媒体は、プログラム命令、データファイル、データ構造などを単独又は組合せて含む。記録媒体及びプログラム命令は、本発明の目的のために特別に設計して構成されたものでもよく、コンピュータソフトウェア分野の技術を有する当業者にとって公知のものであり使用可能なものであってもよい。コンピュータ読み取り可能な記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク及び磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体、フロプティカルディスクのような磁気−光媒体、及びＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を保存して実行するように特別に構成されたハードウェア装置を含む。プログラム命令の例としては、コンパイラによって生成されるような機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行される高級言語コードを含む。ハードウェア装置は、本発明の動作を実行するために１つ以上のソフトウェアモジュールとして作動するように構成してもよく、その逆も同様である。
【０１１０】
以上、本発明の実施形態について図面を参照しながら詳細に説明したが、本発明は、上述の実施形態に限定されるものではなく、本発明の技術的範囲から逸脱しない範囲内で多様に変更実施することが可能である。
【符号の説明】
【０１１１】
１００：運送管理システム
１１０：配送計画生成装置
１２１：配送会社サーバＡ
１２２：配送会社サーバＢ
【図１】
2018026086.tif 000010
【図２】
2018026086.tif 000011
【図３】
2018026086.tif 000012
【図４】
2018026086.tif 000013
【図５】
2018026086.tif 000014
【図６】
2018026086.tif 000015
【図７】
2018026086.tif 000016
【図８】
2018026086.tif 000017
【図９】
2018026086.tif 000018