为了更好地理解 or-tools 路由背后的约束编程,我创建了一个 depot 和 4 个其他节点的玩具示例,配置为允许两条路由。
这个想法是,车辆从仓库行驶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
应该在 after1
和 before访问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-tools 不会交换1
and 2
,即使在明确启用use_swap_active
anduse_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
返回的解决方案附近,但 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')