車両間の最大距離を最小限に抑えるために、スパン コスト係数を使用することをお勧めします。
# Try to minimize the max distance among vehicles.
# /!\ It doesn't mean the standard deviation is minimized
distance_dimension.SetGlobalSpanCostCoefficient(100)
https://developers.google.com/optimization/routing/vrp#exampleから取得
これは、費用関数が距離 (つまり、燃料の使用量) ではなく移動時間に基づいており、目標が最後の車両をできるだけ早くデポに戻すことである場合に特に役立ちます。
Q1: 目的関数を車両間の最大コスト (総コストとグローバル スパンの合計ではない) に定義できますか?
これが不可能な場合、私はその理由が何であるか疑問に思っています。A) そのような制約を実装するのは難しい、または B) (スパン制約を使用する場合と比較して) 悪い解決策をもたらす暗黙の欠点が欠けていると想像できます。
グローバル スパン制約を 1000 に設定したとしても (しかし、それはどういう意味ですか?)、すべての車両が使用されていることを保証するものではないことに気付きました。より多くの車両を使用することで、そのソリューションを改善できるはずですよね?
編集: これは最小限の作業例です。20 か所の停留所で 5 台の車両を利用できます。停留所間の移動時間を 1 時間と定義しているため、最適な解決策は、各ルートに 4 つの停留所が含まれ、すべての車両が 4 時間後に車両基地に戻ることです。グローバル スパンの制約がなければ、1 台の車両が合計 20 時間ですべての作業を行います。グローバル スパン制約 (係数 = 1000) を使用すると、2 台の車両がそれぞれ 10 か所の停留所にサービスを提供します。
import ortools.constraint_solver.pywrapcp
import ortools.constraint_solver.routing_enums_pb2
stops = 20
vehicles = 5
depot = 0
routing = ortools.constraint_solver.pywrapcp.RoutingModel(stops, vehicles, depot)
def cost_function(x,y):
return 1
routing.SetArcCostEvaluatorOfAllVehicles(cost_function)
evaluator = cost_function
slack_max = 24
capacity = 24
fix_start_cumul_to_zero = True
name = "time"
routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)
time_dimension = routing.GetDimensionOrDie("time")
time_dimension.SetGlobalSpanCostCoefficient(1000)
search_params = ortools.constraint_solver.pywrapcp.RoutingModel.DefaultSearchParameters()
assignment = routing.SolveWithParameters(search_params)
ソリューション プロッターの出力:
車両 0 のルート: 0 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 0 ルート 0 の所要時間: 10 時間
車両 1 のルート: 0 -> 10 -> 0 ルート 1 の所要時間: 2 時間
車両 2 のルート: 0 -> 0 ルート 2 の所要時間: 1 時間
車両 3 のルート: 0 -> 0 ルート 3 の所要時間: 1 時間
車両 4 のルート: 0 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 ルート 4 の所要時間: 10 時間
全ルートの合計所要時間: 24 時間