ルートのコンパクトさ (Route compactness)

車両ルーティング問題 (VRP) では、ルートの最適化には、単なる車両容量や顧客需要以上のものが含まれます。ルートのコンパクトさとクラスタリングは、空間的位置に基づいてルートを管理および最適化するために使用される2つの主要な概念です。

ルートのコンパクトさとは、単一のルートに含まれるノード（顧客）の地理的な密度または近接性を指します。コンパクトなルートとは、停留所が互いに近く、移動時間と距離を最小限に抑えるルートのことです。この概念は、過度に広がったり、遠く離れた地点を結ぶ長くて非効率的な区間を持たないルートとして視覚化されることがよくあります。それは望ましい品質として機能し、VRP ソリューションを各車両にとってより効率的で地理的に焦点を絞った領域へと導きます。

計画に対するコンパクトさの影響 (Impact of compactness on planning)

効率の向上: 良好なクラスタリングから生じるコンパクトなルートは、「ステムタイム」（デポからサービスエリアまでの移動）と「ルートタイム」（顧客間の移動）を最小限に抑えます。

計画と管理の容易化: ドライバーを特定のクラスターまたはゾーンに割り当てると、毎日の配車がより単純で予測可能になります。

顧客サービスの向上: サービスエリアが狭くなると、配達ウィンドウの信頼性が高まり、応答時間が短縮される可能性があります。

スケーラビリティ: この戦略により、企業は新しい顧客を最も近い既存のクラスターに割り当てることで新しい顧客を簡単に追加したり、新しいクラスターにサービスを提供するために新しい車両を追加することでスケールアップしたりできます。

例 (Example)

都市全体に広がる100件の配達注文を持つケータリング会社を想像してください。同社には5台の配達バンがあり、それぞれ20件の注文を処理する能力があります。

ルートのコンパクトさがない場合: ルーティングアルゴリズムは、都市をジグザグに進み、重複し、長距離をカバーして、それぞれ20人の顧客にサービスを提供する5つのルートを作成する可能性があります。あるバンは北側から南側へ移動し、別のバンはその逆を行う可能性があります。
ルートのコンパクトさがある場合: 各バンには1つのクラスターが割り当てられます。バン1は「ダウンタウン」クラスターのみにサービスを提供し、バン2は「西郊外」のみにサービスを提供します。結果として得られるルートは非常にコンパクトであり、単一のバンのすべての停留所が同じ近隣にあるためです。これにより、クラスター化されていない非コンパクトなルートと比較して、移動時間と運用コストが大幅に削減されます。

Stateless API での実装 (Implementation in Stateless API)

この機能は、専用のロジスティクス車両ルーティング問題 (VRP) ソルバー内のオプション機能です。ルートのコンパクトさは、最適化の目標に応じて時間または距離のいずれかのコストをノード

への車両移動に追加するポリリニアモデルを採用することで実現されます。このモデルは長距離移動にペナルティを科し、それによってよりコンパクトなルートを促進します。ソフト制約として総コスト関数に統合されたこのメカニズムは、ルートのコンパクトさを自動的に高め、他の最適化ペナルティとのバランスを取ります。

`travel_matrix_operator` による高度なルートコスト制御 (Advanced Route Cost Control with `travel_matrix_operator`)

コンパクトさの促進を含む、ルートコストの高度で柔軟な制御のために、engine_settings.model_parameters 内で travel_matrix_operator を構成できます。この強力な演算子は、標準のルート依存コスト計算をより一般的な式に置き換え、移動時間と距離が全体的な最適化目標にどのように寄与するかを詳細にカスタマイズできるようにします。

総コスト値は、さまざまなルーティングエンジンとマトリックスタイプからの寄与を合計することによって計算されます。コストのルート依存部分の一般的な式は次のとおりです。

{\tt cost} = R(\widetilde{T}_{ij}^{(1)})+R(\widetilde{D}_{ij}^{(1)})+R(\widetilde{T}_{ij}^{(2)})+R(\widetilde{D}_{ij}^{(2)})

ここで、上付文字 (1) と (2) は、それぞれ primary と secondary のルーティングエンジンを指します。 $\widetilde{T}_{ij}$ と $\widetilde{D}_{ij}$ は、時間と距離のマトリックスを表します。関数 $R()$ は、線形ペナルティとポリリニアペナルティの両方を組み込んで、各マトリックスがコストにどのように寄与するかを定義します。

特定の移動セグメントのコスト関数 $R({m}_{ij})$ は、linear 部分と polylinear 部分で構成されます。

R({m}_{ij}) = m_{ij} \cdot {\tt linear} + \sum_k[({\tt base}_k + (m_{ij}-{\tt threshold}_k) \cdot{\tt rate}_k), \; {\tt if} \;m_{ij}>{\tt threshold}_k]

この式は、移動セグメント $m_{ij}$ （時間または距離）のコストが、線形コンポーネントと、場合によっては複数のポリリニアペナルティコンポーネントの合計であることを示しています。各ポリリニアコンポーネント $k$ は、 $m_{ij}$ がその threshold 条件を満たす場合にペナルティを適用します。

`travel_matrix_operator` の使用方法 (How to Use `travel_matrix_operator`)

これらの詳細設定を構成するには、engine_settings.model_parameters 内で travel_matrix_operator を定義します。

engine_settings.model_parameters.travel_matrix_operator
{
    "travel_matrix_operator": {
        "use_optimize_quantity": false,
        "primary": {
            "time": {
                "linear": 1,
                "polylinear": [
                    {
                        "threshold": 3600,
                        "relation": "greater",
                        "penalty": { "base": 5000, "rate": 2 }
                    }
                ]
            },
            "distance": { "linear": 0.5 }
        },
        "secondary": {
            "distance": {
                "linear": 0.1,
                "polylinear": [
                    {
                        "threshold": 10000,
                        "relation": "greater",
                        "penalty": { "base": 1000, "rate": 0.2 }
                    }
                ]
            }
        }
    }
}

主要パラメータ (Key Parameters)

use_optimize_quantity (boolean, デフォルト false、travel_matrix_operator が存在する場合):
- true の場合（下位互換性のため）、システムは optimize_quantity 値に基づいて1つのペナルティタイプのみを使用します。たとえば、optimize_quantity = "total_distance" の場合、primary.time と secondary.time の構成は無視されます。
- false の場合、optimize_quantity 値は無視され、travel_matrix_operator 内で定義されたすべてのパラメータがコスト計算に寄与します。これは、複雑なコスト関数を作成するための最大の柔軟性を提供します。
primary および secondary (objects): これらのセクションでは、2つの独立したルーティングエンジンからのコスト寄与を定義できます。これは、コンパクトさを促進するのに特に役立ちます。
- ユースケース: primary エンジンは現実世界の道路網の距離/時間を計算でき、secondary エンジン（例：spheroid または euclidean）は直線「直線距離」を計算します。二次エンジンの距離に小さなコスト係数を追加することで、地理的に分散したノードにペナルティを科し、ソルバーがより視覚的にコンパクトなルートを作成するように促します。
- time / distance (objects): primary と secondary 内で、時間と距離のマトリックスがコストにどのように寄与するかを指定できます。
  - linear (number, デフォルト 0): 移動値 ( $m_{ij}$ ) に直接適用されるスケーリング係数。値 1 は、移動時間/距離がそのままコストに追加されることを意味します。値 2 は、その寄与を2倍にします。
  - polylinear (array of objects): コンパクトさのルールを定義するのに理想的なペナルティ条件のリスト。

`polylinear` ペナルティ構成 (`polylinear` Penalty Configuration)

polylinear 配列内の各オブジェクトは、次のパラメータを持つペナルティルールです。

threshold (number, デフォルト 0): ペナルティルールがトリガーされる値。単位はマトリックスタイプと一致します（距離はメートル、時間は秒）。
relation (string, 必須): "greater" または "less" である必要があります。ペナルティが threshold を超える移動値に適用されるか、下回る移動値に適用されるかを決定します。
penalty (dictionary, オプション, デフォルト {"base": 0, "rate": 0}):
- base (number, オプション, デフォルト 0): threshold 条件が満たされた場合に追加される固定ペナルティ。
- rate (number, オプション, デフォルト 0): threshold を超える（または下回る）移動単位ごとの追加ペナルティ。
ignore_first (オプション, デフォルト true): true の場合、partial_route（例：デポ）から最初の停留所までのトリップにはペナルティは適用されません。
ignore_last (オプション, デフォルト true): true の場合、最後の停留所から partial_route_end（例：デポ）に戻るトリップにはペナルティは適用されません。

重要な注意点

relation が less に設定されている場合、短いトリップに正のペナルティをもたらすには、rate を負にする必要があります。
各 polylinear 条件は独立して評価され、それらの影響が合計されて合計ペナルティが計算されます。
任意の2つのノード間の合計移動コストは、非現実的な最適化を防ぐために非負の値に制限されています。
混合フリートの場合、車両の matrix_id に基づいてペナルティが異なる場合があります。

実践例: コンパクトルートの促進 (Practical Example: Promoting Compact Routes)

主に 移動時間 を最適化するが、地理的なコンパクトさ も促進し、非常に長い個々のトリップにペナルティを科すコスト関数を作成しましょう。

目標:

主な目的: 総移動時間を最小化する。
ソフト制約: 長くて非効率な区間を避けるために、1時間（3600秒）を超える個々のトリップにペナルティを科す。
ソフト制約: 停留所間の直線距離に小さなペナルティを追加することで、ルートが地理的にコンパクトになるように促す。

構成:

engine_settings
{
    "routing_engine": { "routing_engine_name": "osrm" },
    "secondary_routing_engine": { "routing_engine_name": "spheroid" },
    "model_parameters": {
        "travel_matrix_operator": {
            "use_optimize_quantity": false,
            "primary": {
                "time": {
                    "linear": 1,
                    "polylinear": [
                        {
                            "threshold": 3600,
                            "relation": "greater",
                            "penalty": { "base": 5000, "rate": 2 }
                        }
                    ]
                }
            },
            "secondary": {
                "distance": {
                    "linear": 0.1
                }
            }
        }
    }
}

説明:

primary.time.linear: 1: これにより、総移動時間（primary エンジン、osrm から）がコスト関数の主要コンポーネントになります。
primary.time.polylinear: これは、1時間を超える単一のトリップに大きなペナルティを追加します。
- base: 5000: トリップが3600秒を超えると、大きな固定ペナルティが追加されます。
- rate: 2: 1時間のしきい値を超える1秒ごとに、2の追加ペナルティが追加されます。
secondary.distance.linear: 0.1: これは、停留所間の直線距離（secondary エンジン、spheroid によって計算）に基づいて小さなコストを追加します。このペナルティは、主要な時間最適化を無効にするほど大きくはありませんが、移動時間が同様の場合にソルバーが地理的により近い停留所を選択するように導き、コンパクトさを促進するのに十分重要です。

プレイグラウンド (Playground)

以下のプレイグラウンドを使用して、ルートのコンパクトさ の概念を試すことができます。

計画に対するコンパクトさの影響 (Impact of compactness on planning)​

例 (Example)​

Stateless API での実装 (Implementation in Stateless API)​

travel_matrix_operator による高度なルートコスト制御 (Advanced Route Cost Control with travel_matrix_operator)​

travel_matrix_operator の使用方法 (How to Use travel_matrix_operator)​

主要パラメータ (Key Parameters)​

polylinear ペナルティ構成 (polylinear Penalty Configuration)​

実践例: コンパクトルートの促進 (Practical Example: Promoting Compact Routes)​

プレイグラウンド (Playground)​