テリトリーの最適化を含む VRP

多くの運送会社は、ビジネス上の制約により、強力な顧客関係を維持するため、およびその他の理由から、運転手と車両の組み合わせで特定の地理的エリアをサービスするモードで運営されています。

テリトリーの最適化機能を使用すると、ツアーを最適化する際に、特定のテリトリー間で車両をプログラムで割り当てることができます。リクエストを作成しながらテリトリーの最適化を行う際、実行するジョブの場所によって、作業量と保有車両の積載量のバランスを制御することができます。車両または車両グループを特定のテリトリーに割り当てて、希望するテリトリーで車両を運行できるようにするか、または他のテリトリーでの運行を制限します。

ツアープランでは、車両が許可されている、または希望する作業の空間的制約を定義するために、テリトリーが使用されます。問題を作成する場合、各テリトリーは id によって参照されます。この id はユーザーの完全な管理下にあり、地理的な場所や行政上の命名規則には拘束されません。 idのテリトリーは、車両とジョブの両方の定義で一貫して使用される一意の識別子です。ユーザーは、ジョブの場所を正しく表すように、ジョブにテリトリーを割り当てる責任があります。

このチュートリアルでは、テリトリー最適化に対する 3 つのアプローチについて考察します。

限定テリトリー

限定テリトリー機能は、車両または車両グループが特定のテリトリーでのみ作業するよう制限する必要がある場合に適用できます。各車両が特定のテリトリー(都市内の 1 エリアなど) を訪問することのみを許可されている運行管理が該当します。

特定の車両 type に対し、その フィールドterritoriesには、例えば、車両が制限されている地域 idの、North が含まれます。

"fleet": {
    "types": [
        {
            ...
            "territories": {
                "strict": true,
                "items": [{"id": "North"}]
            }
        }
    ]
}

個々の job は、territoryIds フィールドを持っており、そこでテリトリーの id、例えば North が指定されます。

"plan": {
    "jobs": [
        {
            ...
            "tasks": {
                "deliveries": [
                    {
                        "places": [{
                            ...
                            "territoryIds": ["North"]
                        }]
                    }
                ]
            }
        }
    ]
}

以下の例では、2 台の車両と、異なるエリアで実行される 3 つのジョブをがあります。ジョブ A は北で、ジョブ B は南、ジョブ C はテリトリーが指定されていません。この問題では、各車両がこれらのテリトリーのいずれか 1 つのみを訪問できます。

デポ (@)、3 つのジョブ (A 、 B 、 C)、および限定テリトリー
 (北 : 紫、南 : 赤) を含むジョブプラン
図 1. デポ (@) 、 3 つのジョブ (A 、 B 、 C) 、および限定テリトリー (青 : 紫、南 : 赤) を含むジョブプラン
{
    "fleet": {
        "types": [
            {
                "id": "car_1",
                "profile": "car_profile",
                "costs": {
                    "distance": 0.0001,
                    "time": 0
                },
                "territories": {
                    "strict": true,
                    "items": [
                        {
                            "id": "North"
                        }
                    ]
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2021-07-04T06:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        },
                        "end": {
                            "time": "2021-07-04T13:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        }
                    }
                ],
                "capacity": [
                    0
                ],
                "amount": 1
            },
            {
                "id": "car_2",
                "profile": "car_profile",
                "costs": {
                    "distance": 0.0001,
                    "time": 0
                },
                "territories": {
                    "strict": true,
                    "items": [
                        {
                            "id": "South"
                        }
                    ]
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2021-07-04T06:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        },
                        "end": {
                            "time": "2021-07-04T13:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        }
                    }
                ],
                "capacity": [
                    0
                ],
                "amount": 1
            }
        ],
        "profiles": [
            {
                "type": "car",
                "name": "car_profile"
            }
        ]
    },
    "plan": {
        "jobs": [
            {
                "id": "A",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.628661,
                                        "lng": -122.342312
                                    },
                                    "territoryIds": [
                                        "North"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "B",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.623887,
                                        "lng": -122.341163
                                    },
                                    "territoryIds": [
                                        "South"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "C",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.622523,
                                        "lng": -122.337323
                                    },
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            }
        ]
    }
}

この問題の解決策では、車両 car_1territoryIds 属性が North を含んでいるジョブ、この例ではジョブ A にのみ割り当てられます。そのため、車両 car_2 は、テリトリー South のものであるジョブ B に割り当てられます。ジョブ C は、North でも South でもなく、どのツアーにも含まれません。

car_1 (イエローツアー)および car_2 (グリーンツアー)を利用した限定テリトリーのソリューション
図 2. car_1 (イエローツアー)および car_2 (グリーンツアー)を利用した限定テリトリーのソリューション
{
    "statistic": {
        "cost": 0.2675,
        "distance": 2675,
        "duration": 447,
        "times": {
            "driving": 447,
            "serving": 0,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "car_2_1",
            "typeId": "car_2",
            "stops": [
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:03:00Z",
                        "departure": "2021-07-04T06:03:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.623887,
                        "lng": -122.341163
                    },
                    "time": {
                        "arrival": "2021-07-04T06:04:54Z",
                        "departure": "2021-07-04T06:04:54Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "B",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:06:33Z",
                        "departure": "2021-07-04T06:06:33Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 0.1155,
                "distance": 1155,
                "duration": 213,
                "times": {
                    "driving": 213,
                    "serving": 0,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 0
        },
        {
            "vehicleId": "car_1_1",
            "typeId": "car_1",
            "stops": [
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:03:00Z",
                        "departure": "2021-07-04T06:03:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.628661,
                        "lng": -122.342312
                    },
                    "time": {
                        "arrival": "2021-07-04T06:04:48Z",
                        "departure": "2021-07-04T06:04:48Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "A",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:06:54Z",
                        "departure": "2021-07-04T06:06:54Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 0.152,
                "distance": 1520,
                "duration": 234,
                "times": {
                    "driving": 234,
                    "serving": 0,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 0
        }
    ],
    "unassigned": [
        {
            "jobId": "C",
            "reasons": [
                {
                    "code": "TERRITORY_CONSTRAINT",
                    "description": "cannot be assigned due to territory constraint"
                }
            ]
        }
    ]
}

指定のテリトリー

運行管理 には、指定のテリトリー(何らかの理由でより効率的に運用できるテリトリー)を持つ車両が存在する可能性があります。そのため、ディスパッチャは、指定の方法でそのテリトリーで車両を運用することを希望しています。 ただし、予備の作業量と時間がある場合は、これらの優先テリトリー以外の作業も集荷する必要があります。そのため、特定のテリトリーに割り当てるだけでは制限がかかりすぎます。 [ 優先するテリトリー ] オプションを使用すると、優先するテリトリーでジョブをスケジュールできます。可能であれば、他のテリトリーのジョブをスケジュールできます。

ツアープランでは "strict": false、で示されているテリトリーに対する厳格な制限とは対照 "strict": true的に、このようなテリトリの優先度がによって示されます。

"fleet": {
    "types": [
        {
            ...
            "territories": {
                "strict": false,
                "items": [{"id": "North"}]
            }
        }
    ]
}

その地域で指定されていない作業 place は、優先テリトリーの車両およびテリトリーが割り当てられていない車両のみが集荷できます。 厳しいテリトリーにある車両は、このような作業には対応できません。

以下の例では、 2 台の車両を使用しています。 私たちは、これらのうちの 1 つをテリトリーNorth内で厳密に運用するように設定しました。また、そのテリトリーSouthの別のものも制限なく運用するように設定しました。 5 つのジョブを実行する必要があります。そのうちの 2 つはテリトリー North内、 1 つはSouth内、もう 1 つは(どの車両にも割り当てられていません)South-Eastにあり、優先テリトリー外で作業する必要があります。

デポ (@) 、 5 つのジョブ (A ~ E) 、および優先テリトリー ( 北はバイオレット、南は赤、南はオレンジ ) のジョブプラン
図 3. デポ (@) 、 5 つのジョブ (A ~ E) 、および優先テリトリー ( 北はバイオレット、南は赤、南はオレンジ ) のジョブプラン
{
    "fleet": {
        "types": [
            {
                "id": "car_1",
                "profile": "car_profile",
                "costs": {
                    "distance": 0.0001,
                    "time": 0
                },
                "territories": {
                    "strict": true,
                    "items": [
                        {
                            "id": "North"
                        }
                    ]
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2021-07-04T06:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        },
                        "end": {
                            "time": "2021-07-04T06:08:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        }
                    }
                ],
                "capacity": [
                    0
                ],
                "amount": 1
            },
            {
                "id": "car_2",
                "profile": "car_profile",
                "costs": {
                    "distance": 0.0001,
                    "time": 0
                },
                "territories": {
                    "strict": false,
                    "items": [
                        {
                            "id": "South"
                        }
                    ]
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2021-07-04T06:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        },
                        "end": {
                            "time": "2021-07-04T13:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        }
                    }
                ],
                "capacity": [
                    0
                ],
                "amount": 1
            }
        ],
        "profiles": [
            {
                "type": "car",
                "name": "car_profile"
            }
        ]
    },
    "plan": {
        "jobs": [
            {
                "id": "A",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.628661,
                                        "lng": -122.342312
                                    },
                                    "territoryIds": [
                                        "North"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "B",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.623887,
                                        "lng": -122.341163
                                    },
                                    "territoryIds": [
                                        "South"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "C",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.622523,
                                        "lng": -122.337323
                                    },
                                    "territoryIds": [
                                        "South-East"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "D",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.624891,
                                        "lng": -122.347445
                                    },
                                    "territoryIds": [
                                        "North"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "E",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.623208,
                                        "lng": -122.330536
                                    },
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            }
        ]
    }
}

ソリューションから、領域の割り当てが厳密であるため、車両タイプ car_1territoryIds 属性 Northを持つジョブにのみ割り当てられていることがわかります。シフトの時間的制約により、 シフトに割り当てることができるのはジョブのみです。 A

車両タイプ car_2 がジョブBに割り当てられます。このジョブは、優先されるテリトリーSouthにあります。 さらに、シフト時間が長いために予備の作業量があるため 、車両によって明示的に提供されていない領域 (South-East)、テリトリーのない作業 E、 および 時間の制約 car_1 によりサービス を提供できない North での作業 D から作業 C が割り当てられます。

CAR_1 (イエローツアー)および CAR_2 (グリーンツアー)を利用した、指定のテリトリーのソリューション
図 4. CAR_1 (イエローツアー)および CAR_2 (グリーンツアー)を利用した、指定のテリトリーのソリューション
{
    "statistic": {
        "cost": 0.5169,
        "distance": 5169,
        "duration": 849,
        "times": {
            "driving": 849,
            "serving": 0,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "car_1_1",
            "typeId": "car_1",
            "stops": [
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:03:00Z",
                        "departure": "2021-07-04T06:03:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.628661,
                        "lng": -122.342312
                    },
                    "time": {
                        "arrival": "2021-07-04T06:04:48Z",
                        "departure": "2021-07-04T06:04:48Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "A",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:06:54Z",
                        "departure": "2021-07-04T06:06:54Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 0.152,
                "distance": 1520,
                "duration": 234,
                "times": {
                    "driving": 234,
                    "serving": 0,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 0
        },
        {
            "vehicleId": "car_2_1",
            "typeId": "car_2",
            "stops": [
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:03:00Z",
                        "departure": "2021-07-04T06:03:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.624891,
                        "lng": -122.347445
                    },
                    "time": {
                        "arrival": "2021-07-04T06:05:18Z",
                        "departure": "2021-07-04T06:05:18Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "D",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.623887,
                        "lng": -122.341163
                    },
                    "time": {
                        "arrival": "2021-07-04T06:06:50Z",
                        "departure": "2021-07-04T06:06:50Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "B",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.622523,
                        "lng": -122.337323
                    },
                    "time": {
                        "arrival": "2021-07-04T06:09:10Z",
                        "departure": "2021-07-04T06:09:10Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "C",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.623208,
                        "lng": -122.330536
                    },
                    "time": {
                        "arrival": "2021-07-04T06:11:02Z",
                        "departure": "2021-07-04T06:11:02Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "E",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:13:15Z",
                        "departure": "2021-07-04T06:13:15Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 0.3649,
                "distance": 3649,
                "duration": 615,
                "times": {
                    "driving": 615,
                    "serving": 0,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 0
        }
    ]
}

優先順位付けされたテリトリ

車両に設定されているテリトリーの制限が厳密ではなく、希望するテリトリーよりも詳細な制御が必要な場合は、テリトリーを優先順位付けできます。 つまり、車両を異なる優先順位の複数のエリアまたは地区に割り当てることができます。 たとえば、最も優先度の高いテリトリーを設定するには、優先度を 1 に設定し、優先度の低いテリトリーには 2 を使用します。最大 5 つの優先度を設定できます。 異なるテリトリーで同じ優先度を設定できます。 車両の作業スケジュールを評価する場合、優先度の高いテリトリーの作業が、優先度の低いテリトリーの作業よりも優先されます。

"fleet": {
    "types": [
        {
            ...
            "territories": {
                "strict": true,
                "items": [
                    {
                        "id": "North",
                        "priority": 1
                    },
                    {
                        "id": "South",
                        "priority": 2
                    },                    
                    {
                        "id": "South-East",
                        "priority": 2
                    }
                ]
            }
        }
    ]
}

1 台の車両に同じ優先度の複数のテリトリーを設定するオプションを使用すると、標準のテリトリーに限定された車両でジョブを実行できない場合に問題が解決することがあります。 車両の 1 台に複数のテリトリー (またはそれらのすべて) を低い優先度で設定すると、その車両は残りの車両に割り当てられないジョブを実行することになります。joker 例の車両タイプを確認して、どのように作動するかを確認してください。

以下の例では、 3 台の車両を使用しています。

  • car_1 2 つのテリトリーで厳密に運用 されます。North 優先度が高く、South優先度が低くなります。
  • car_2 3 つのテリトリーで厳格に運用 されています。South優先度は高く、Northと優先度は低いSouth-Eastを一緒にします。
  • jokerNorthSouth、および South-East の 3 つのテリトリーすべてで、残りのフリートより優先度が低く運航され、地域外でも運航できます。

これらの車両は、以下の異なるエリアで 6 つの作業を実施することを目的としています。

  • A 北部方面のジョブ
  • B 南部方面のジョブ
  • C 南東部方面のジョブ
  • D 北部方面のジョブ
  • E 優先順位が付けられたテリトリー外でのジョブ
  • F 南東部方面のジョブ
デポ( @ )、 6 つのジョブ( A ~ F )、優先順位付けされたテリトリー(北はバイオレット、南はレッド、南はオレンジ)のジョブプラン
図 5. デポ( @ )、 6 つのジョブ( A ~ F )、優先順位付けされたテリトリー(北はバイオレット、南はレッド、南はオレンジ)のジョブプラン
{
    "fleet": {
        "types": [
            {
                "id": "car_1",
                "profile": "car_profile",
                "costs": {
                    "distance": 0.0001,
                    "time": 0
                },
                "territories": {
                    "strict": true,
                    "items": [
                        {
                            "id": "North",
                            "priority": 1
                        },
                        {
                            "id": "South",
                            "priority": 2
                        }
                    ]
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2021-07-04T06:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        },
                        "end": {
                            "time": "2021-07-04T06:08:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        }
                    }
                ],
                "capacity": [
                    0
                ],
                "amount": 1
            },
            {
                "id": "car_2",
                "profile": "car_profile",
                "costs": {
                    "distance": 0.0001,
                    "time": 0
                },
                "territories": {
                    "strict": true,
                    "items": [
                        {
                            "id": "South",
                            "priority": 1
                        },
                        {
                            "id": "North",
                            "priority": 2
                        },
                        {
                            "id": "South-East",
                            "priority": 2
                        }
                    ]
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2021-07-04T06:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        },
                        "end": {
                            "time": "2021-07-04T06:11:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        }
                    }
                ],
                "capacity": [
                    0
                ],
                "amount": 1
            },
            {
                "id": "joker",
                "profile": "car_profile",
                "costs": {
                    "distance": 0.0001,
                    "time": 0
                },
                "territories": {
                    "strict": false,
                    "items": [
                        {
                            "id": "North",
                            "priority": 3
                        },
                        {
                            "id": "South",
                            "priority": 3
                        },
                        {
                            "id": "South-East",
                            "priority": 3
                        }
                    ]
                },
                "shifts": [
                    {
                        "start": {
                            "time": "2021-07-04T06:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        },
                        "end": {
                            "time": "2021-07-04T13:03:00Z",
                            "location": {
                                "lat": 47.625729,
                                "lng": -122.337255
                            }
                        }
                    }
                ],
                "capacity": [
                    0
                ],
                "amount": 1
            }
        ],
        "profiles": [
            {
                "type": "car",
                "name": "car_profile"
            }
        ]
    },
    "plan": {
        "jobs": [
            {
                "id": "A",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.628661,
                                        "lng": -122.342312
                                    },
                                    "territoryIds": [
                                        "North"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "B",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.623887,
                                        "lng": -122.341163
                                    },
                                    "territoryIds": [
                                        "South"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "C",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.622523,
                                        "lng": -122.337323
                                    },
                                    "territoryIds": [
                                        "South-East"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "D",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.624891,
                                        "lng": -122.347445
                                    },
                                    "territoryIds": [
                                        "North"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "E",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.623208,
                                        "lng": -122.330536
                                    },
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            },
            {
                "id": "F",
                "tasks": {
                    "deliveries": [
                        {
                            "places": [
                                {
                                    "location": {
                                        "lat": 47.621933,
                                        "lng": -122.334567
                                    },
                                    "territoryIds": [
                                        "South-East"
                                    ],
                                    "duration": 0
                                }
                            ],
                            "demand": [
                                0
                            ]
                        }
                    ]
                }
            }
        ]
    }
}

解決策では、車両タイプ car_1A 高優先度ゾーン内のジョブとして機能 NorthDNorthFSouth-East しますが、シフト時間の制約により、またはのジョブには割り当てられません。

車両タイプ car_2B 、最優先テリトリーSouthの作業、 優先順位の低いテリトリーNorthでの作業D 、 優先順位の低いテリトリー South-Eastでの作業Cに使用されます。

最後に、のテリトリjokerの設定は厳密ではないため、South-WestでジョブFを実行し、優先順位の高い地域外でジョブ Eを実行します。

CAR_1 (イエローツアー)、 CAR_2 (ライトグリーンツアー)、ジョーカー(ダークグリーンツアー)による優先順位の高いテリトリー向けのソリューション
図 6. CAR_1 (イエローツアー)、 CAR_2 (ライトグリーンツアー)、ジョーカー(ダークグリーンツアー)による優先順位の高いテリトリー向けのソリューション
{
    "statistic": {
        "cost": 0.6223000000000001,
        "distance": 6223,
        "duration": 1066,
        "times": {
            "driving": 1066,
            "serving": 0,
            "waiting": 0,
            "break": 0
        }
    },
    "tours": [
        {
            "vehicleId": "car_1_1",
            "typeId": "car_1",
            "stops": [
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:03:00Z",
                        "departure": "2021-07-04T06:03:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.628661,
                        "lng": -122.342312
                    },
                    "time": {
                        "arrival": "2021-07-04T06:04:48Z",
                        "departure": "2021-07-04T06:04:48Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "A",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:06:54Z",
                        "departure": "2021-07-04T06:06:54Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 0.152,
                "distance": 1520,
                "duration": 234,
                "times": {
                    "driving": 234,
                    "serving": 0,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 0
        },
        {
            "vehicleId": "car_2_1",
            "typeId": "car_2",
            "stops": [
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:03:00Z",
                        "departure": "2021-07-04T06:03:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.624891,
                        "lng": -122.347445
                    },
                    "time": {
                        "arrival": "2021-07-04T06:05:18Z",
                        "departure": "2021-07-04T06:05:18Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "D",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.623887,
                        "lng": -122.341163
                    },
                    "time": {
                        "arrival": "2021-07-04T06:06:50Z",
                        "departure": "2021-07-04T06:06:50Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "B",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.622523,
                        "lng": -122.337323
                    },
                    "time": {
                        "arrival": "2021-07-04T06:09:10Z",
                        "departure": "2021-07-04T06:09:10Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "C",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:10:59Z",
                        "departure": "2021-07-04T06:10:59Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 0.2811,
                "distance": 2811,
                "duration": 479,
                "times": {
                    "driving": 479,
                    "serving": 0,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 0
        },
        {
            "vehicleId": "joker_1",
            "typeId": "joker",
            "stops": [
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:03:00Z",
                        "departure": "2021-07-04T06:03:00Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "departure",
                            "type": "departure"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.623208,
                        "lng": -122.330536
                    },
                    "time": {
                        "arrival": "2021-07-04T06:05:22Z",
                        "departure": "2021-07-04T06:05:22Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "E",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.621933,
                        "lng": -122.334567
                    },
                    "time": {
                        "arrival": "2021-07-04T06:06:48Z",
                        "departure": "2021-07-04T06:06:48Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "F",
                            "type": "delivery"
                        }
                    ]
                },
                {
                    "location": {
                        "lat": 47.625729,
                        "lng": -122.337255
                    },
                    "time": {
                        "arrival": "2021-07-04T06:08:53Z",
                        "departure": "2021-07-04T06:08:53Z"
                    },
                    "load": [
                        0
                    ],
                    "activities": [
                        {
                            "jobId": "arrival",
                            "type": "arrival"
                        }
                    ]
                }
            ],
            "statistic": {
                "cost": 0.18920000000000003,
                "distance": 1892,
                "duration": 353,
                "times": {
                    "driving": 353,
                    "serving": 0,
                    "waiting": 0,
                    "break": 0
                }
            },
            "shiftIndex": 0
        }
    ]
}

」に一致する結果は 件です

    」に一致する結果はありません