0

or-tools ルーティングの背後にある制約プログラミングをよりよく理解するために、デポと 2 つのルートを許可するように構成された他の 4 つのノードのおもちゃの例を作成しました。

ここに画像の説明を入力

これは、車両がデポから に移動し、0次に1ピッキング2またはのいずれかを選択してデポに移動し、デポに戻るという考え方です。車両は緑または赤のパスを選択します。私の実際の問題はより複雑で、複数の車両がありますが、同様の制約があります。340

この例では、コストのユークリッド距離関数を作成しました。

class Distances:
    def __init__(self):
        self.locations = [
            [-1,  0], # source
            [ 0, -1], # waypoint 1
            [ 0,  1], # waypoint 2
            [ 1,  0], # destination
        ]

    def __len__(self):
        return len(self.locations) + 1

    def dist(self, x, y):
        return int(10000 * math.sqrt(
            (x[0] - y[0]) ** 2 +
            (x[1] - y[1]) ** 2))

    def __call__(self, i, j):
        if i == 0 and j == 0:
            return 0
        if j == 0 or i == 0:
            return 1 # very small distance between depot and non-depot, simulating 0
        return self.dist(self.locations[i - 1], self.locations[j - 1])


distance = Distances()

そして、次数を制約する l0 距離関数:

# l0-distance to add order constraints
class Order:
    def __call__(self, i, j):
        return 0 if i == j else 1


order = Order()

次に、モデルを作成し、これを解決しようとします。

search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.ALL_UNPERFORMED)

search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.SIMULATED_ANNEALING
search_parameters.time_limit_ms = 3000

routing = pywrapcp.RoutingModel(len(distance), 1)

routing.SetArcCostEvaluatorOfAllVehicles(distance)
routing.SetDepot(0)
solver = routing.solver()

routing.AddDimension(order, int(1e18), int(1e18), True, "order")

# Since `ALL_UNPERFORMED` is used, each node must be allowed inactive
order_dimension = routing.GetDimensionOrDie("order")
routing.AddDisjunction([1], int(1e10))
routing.AddDisjunction([2, 3], int(1e10))
routing.AddDisjunction([4], int(1e10))

solver.AddConstraint(order_dimension.CumulVar(1) <= order_dimension.CumulVar(2))
solver.AddConstraint(order_dimension.CumulVar(1) <= order_dimension.CumulVar(3))

solver.AddConstraint(order_dimension.CumulVar(2) <= order_dimension.CumulVar(4))
solver.AddConstraint(order_dimension.CumulVar(3) <= order_dimension.CumulVar(4))

# routing.AddPickupAndDelivery(1, 2)
# routing.AddPickupAndDelivery(1, 3)
# routing.AddPickupAndDelivery(2, 4)
# routing.AddPickupAndDelivery(3, 4)

routing.CloseModelWithParameters(search_parameters)
assignment = routing.SolveWithParameters(search_parameters)

if assignment is not None:
    print('cost: ' + str(assignment.ObjectiveValue()))
    route = []
    index = routing.Start(0)
    while not routing.IsEnd(index):
        route.append(routing.IndexToNode(index))
        index = assignment.Value(routing.NextVar(index))
    for node in route:
        print(' - {:2d}'.format(node))
else:
    print('nothing found')

したがって[1]、 とは、最初のソリューションが機能[4]することを可能にする選言であり、緑または赤のパスのいずれかを選択する必要があることを示す選言です。ALL_UNPERFORMED[2, 3]

これらの選言により、ソルバーは解決策を見つけますが、それを追加して2 after3と1beforeにアクセスする必要がある場合4、ソルバーはアクセスしない2か3、まったくアクセスしません。これはなぜですか？の分離ペナルティを0 -> 1 -> 2/3 -> 4 -> 0回避して、より最適なルートをソルバーが見つけられないのはなぜですか?int(1e10)[2,3]

編集：

それらを削除してに追加することにより、順序制約をソフトに制約しますDistance.__call__。

if (i == 2 or j == 1) or (i == 3 or j == 1) or (i == 4 or j == 2) or (i == 4 or j == 3):
    return int(1e10)

許可されていない注文にペナルティを課すには、ルートが発生し0 -> 2 -> 1 -> 4 -> 0ます。では、 and を明示的に有効にしている場合でも、 or-tools が1andを交換しないのはなぜだろうか。2use_swap_activeuse_relocate_neighborssearch_parameters.local_search_operators

注:失敗した理由は次のとおりです。

if (i == 2 and j == 1) or (i == 3 and j == 1) or (i == 4 and j == 2) or (i == 4 and j == 3):
    return int(1e10)

結論: 検索空間は小さく、より良い解はuse_relocate_neighbors返された解の近傍にありますが、or-tools はそれを見つけられません。なんで？

すべてのコード:

import pandas
import os.path

import numpy
import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2


class Distances:
    def __init__(self):
        self.locations = [
            [-1,  0], # source
            [ 0, -1], # waypoint 1
            [ 0,  1], # waypoint 2
            [ 1,  0], # destination
        ]

    def __len__(self):
        return len(self.locations) + 1

    def dist(self, x, y):
        return int(10000 * math.sqrt(
            (x[0] - y[0]) ** 2 +
            (x[1] - y[1]) ** 2))

    def __call__(self, i, j):
        if i == 0 and j == 0:
            return 0
        if j == 0 or i == 0:
            return 1 # very small distance between depot and non-depot, simulating 0
        return self.dist(self.locations[i - 1], self.locations[j - 1])


distance = Distances()


# l0-distance to add order constraints
class Order:
    def __call__(self, i, j):
        return 0 if i == j else 1


order = Order()

search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.ALL_UNPERFORMED)

search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.SIMULATED_ANNEALING
search_parameters.time_limit_ms = 3000

routing = pywrapcp.RoutingModel(len(distance), 1)

routing.SetArcCostEvaluatorOfAllVehicles(distance)
routing.SetDepot(0)
solver = routing.solver()

routing.AddDimension(order, int(1e18), int(1e18), True, "order")

# Since `ALL_UNPERFORMED` is used, each node must be allowed inactive
order_dimension = routing.GetDimensionOrDie("order")
routing.AddDisjunction([1], int(1e10))
routing.AddDisjunction([2, 3], int(1e10))
routing.AddDisjunction([4], int(1e10))

solver.AddConstraint(
    (routing.ActiveVar(2) == 0)
    or
    (order_dimension.CumulVar(1) <= order_dimension.CumulVar(2))
)
solver.AddConstraint(
    (routing.ActiveVar(3) == 0)
    or
    (order_dimension.CumulVar(1) <= order_dimension.CumulVar(3))
)


solver.AddConstraint(
    (routing.ActiveVar(2) == 0)
    or
    (order_dimension.CumulVar(2) <= order_dimension.CumulVar(4))
)
solver.AddConstraint(
    (routing.ActiveVar(3) == 0)
    or
    (order_dimension.CumulVar(3) <= order_dimension.CumulVar(4))
)

# routing.AddPickupAndDelivery(1, 2)
# routing.AddPickupAndDelivery(1, 3)
# routing.AddPickupAndDelivery(2, 4)
# routing.AddPickupAndDelivery(3, 4)

routing.CloseModelWithParameters(search_parameters)
assignment = routing.SolveWithParameters(search_parameters)

if assignment is not None:
    print('cost: ' + str(assignment.ObjectiveValue()))
    route = []
    index = routing.Start(0)
    while not routing.IsEnd(index):
        route.append(routing.IndexToNode(index))
        index = assignment.Value(routing.NextVar(index))
    for node in route:
        print(' - {:2d}'.format(node))
else:
    print('nothing found')
4

1 に答える 1

1

@furnon github で、github-issues リストを介して私の質問に答えました: https://github.com/google/or-tools/issues/252#issuecomment-249646587

まず、制約プログラミングは制約が厳しいほどパフォーマンスが向上します。いくつかのものは徹底的に検索されると思います。特に、注文次元を制限する必要がありました。

routing.AddDimension(order, int(1e18), int(1e18), True, "order")

より適切に制約されます

routing.AddDimension(order, len(distance) + 1 ,len(distance) + 1, True, "order")

その後、2または3がアクティブかどうかのチェックは必要ないため、次のように順序制約を単純化できます。

solver.AddConstraint(order_dimension.CumulVar(1) <= order_dimension.CumulVar(2))
solver.AddConstraint(order_dimension.CumulVar(1) <= order_dimension.CumulVar(3))
solver.AddConstraint(order_dimension.CumulVar(2) <= order_dimension.CumulVar(4))
solver.AddConstraint(order_dimension.CumulVar(3) <= order_dimension.CumulVar(4))

インライン バージョンでは既に行いましたが、すべてのコード バージョンでは行いませんでした。これで実行可能な解が返されました。

于 2016-09-27T07:33:17.050 に答える