ルートのコンパクトさ

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

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

コンパクトさが計画に与える影響

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

計画と管理の容易さ: ドライバーを特定のクラスターやゾーンに割り当てることで、日々の配車がよりシンプルで予測可能になります。

顧客サービスの向上: より狭いサービスエリアは、より信頼性の高い配達時間枠と迅速な対応時間につながる可能性があります。

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

例

ある都市に100件の配達注文を抱えるケータリング会社を想像してみてください。同社には5台の配達用バンがあり、それぞれ20件の注文を処理できる容量があります。

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

Stateless APIでの実装

この機能は、専用のロジスティクス車両ルーティング問題（VRP）ソルバー内のオプション機能です。ルートのコンパクトさは、ノード

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

`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`の使用方法

これらの高度な設定を構成するには、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 }
                    }
                ]
            }
        }
    }
}

主なパラメータ

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

`polylinear`ペナルティの設定

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

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

重要事項

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

実用例：コンパクトなルートの促進

主に移動時間を最適化し、地理的なコンパクトさを奨励し、非常に長い個々の移動にペナルティを課すコスト関数を作成しましょう。

目標:

主な目的：総移動時間を最小限に抑える。
ソフト制約：長くて非効率な区間を避けるために、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によって計算）に基づいて小さなコストを追加します。このペナルティは、主要な時間最適化を上書きするほど大きくはありませんが、移動時間が類似している場合にソルバーが地理的に近い停車地を選択するように誘導するのに十分重要であり、したがってコンパクトさを促進します。

コンパクトさが計画に与える影響​

例​

Stateless APIでの実装​

travel_matrix_operatorによる高度なルートコスト制御​

travel_matrix_operatorの使用方法​

主なパラメータ​

polylinearペナルティの設定​

実用例：コンパクトなルートの促進​