0
爲了更好地理解背後的約束編程或工具路由，我創建了一個配置庫的玩具示例，並配置了4個其他節點允許兩條路線。OR-tools routing在訂單約束條件下無法找到'瑣碎的'最佳解決方案
的想法是，在車輛從倉庫0到1行進，那麼無論挑選2或3，繼續4並返回到倉庫0;車輛選擇綠色或紅色路徑。我的實際問題比較複雜，有多個車輛，但也有類似的限制。
在這個例子中，我創建了成本歐幾里得距離函數：
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和3應該1後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懲罰不允許的順序，結果。所以我想知道爲什麼or工具不會交換1和2，即使明確啓用use_swap_active和use_relocate_neighbors在search_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附近，但或工具呢找不到它。爲什麼？
所有代碼：
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')