Чтобы лучше понять программирование по программированию позади или инструментами, я создал игрушечный пример депо и 4 других узла, настроенных чтобы разрешить два маршрута.Перенастройка OR-инструментов не позволяет найти «тривиальное» оптимальное решение при наличии ограничений порядка
Идея заключается в том, что транспортное средство движется из депо 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]?
EDIT:
Soft-сдерживая заказ-ограничение, удаляя их и добавляя к 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. Поэтому я удивляюсь, почему или-инструменты не будут меняться 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')