Комментарии 10
Странно у меня этот код находит только такое решение:
Objective: 5454
Route for vehicle 0:
0 -> 2 -> 4 -> 5 -> 6 -> 14 -> 10 -> 11 -> 15 -> 16
Time of the route: 101 minutes
Route for vehicle 1:
1 -> 3 -> 7 -> 8 -> 9 -> 12 -> 13 -> 17
Time of the route: 68 minutes
Maximum of the route: 101 minutes
Интересный момент, возможно играет роль версия библиотеки. У меня установлена версия 9.5.2237. Я отредактировал полный код для удобства копирования. Возможно, при копировании появилась оишбка.
import ortools
print("ortools version %s"%ortools.__version__)ortools version 9.6.2534
Сделай даунгрейд. Просто странно, что у меня решение лучше нашлось.
ortools version 9.5.2237
Objective: 5454
Route for vehicle 0:
0 -> 2 -> 4 -> 5 -> 6 -> 14 -> 10 -> 11 -> 15 -> 16
Time of the route: 101 minutes
Route for vehicle 1:
1 -> 3 -> 7 -> 8 -> 9 -> 12 -> 13 -> 17
Time of the route: 68 minutes
Maximum of the route: 101 minutesНичего не поменялось. От версии не зависит с 9.8.3296 точно так же.
Вы точно не делали изменений в коде? Я просил воспроизвести данное решение на разных os и оно совпадает с моим.
Незначительные, только что бы оно запустилось на python 3.8.10
from typing import Any
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver.pywrapcp import (
DefaultRoutingSearchParameters, RoutingDimension, RoutingIndexManager,
RoutingModel,
)
import ortools
print("ortools version %s"%ortools.__version__)
def create_data_model():
data = {}
data["time_matrix"] = [
[0, 6, 0, 6, 5, 6, 7, 6, 8, 2, 9, 2, 4, 9, 9, 4, 9, 9],
[6, 0, 6, 0, 2, 2, 2, 1, 3, 3, 4, 3, 7, 11, 4, 4, 12, 12],
[0, 6, 0, 6, 5, 6, 7, 6, 8, 2, 9, 2, 4, 9, 9, 4, 9, 9],
[6, 0, 6, 0, 2, 2, 2, 1, 3, 3, 4, 3, 7, 11, 4, 4, 12, 12],
[6, 0, 6, 0, 0, 2, 3, 2, 4, 4, 5, 3, 7, 10, 5, 3, 12, 12],
[9, 4, 9, 4, 3, 0, 1, 2, 1, 6, 3, 6, 9, 12, 3, 6, 14, 14],
[8, 4, 8, 4, 3, 2, 0, 1, 2, 5, 2, 5, 9, 12, 2, 5, 14, 14],
[7, 2, 7, 2, 2, 0, 1, 0, 1, 4, 3, 4, 8, 11, 3, 4, 13, 13],
[9, 4, 9, 4, 4, 2, 0, 2, 0, 6, 2, 6, 10, 13, 2, 6, 14, 14],
[2, 5, 2, 5, 5, 4, 5, 4, 5, 0, 7, 3, 3, 10, 7, 6, 11, 11],
[8, 4, 8, 4, 3, 2, 0, 1, 2, 5, 0, 5, 9, 12, 0, 5, 14, 14],
[3, 4, 3, 4, 4, 4, 5, 4, 6, 2, 7, 0, 5, 9, 7, 3, 10, 10],
[1, 7, 1, 7, 6, 6, 7, 6, 7, 2, 9, 4, 0, 9, 9, 5, 9, 9],
[10, 11, 10, 11, 11, 13, 14, 13, 14, 10, 16, 10, 11, 0, 16, 9, 6, 6],
[8, 4, 8, 4, 3, 2, 0, 1, 2, 5, 0, 5, 9, 12, 0, 5, 14, 14],
[7, 5, 7, 5, 4, 6, 6, 5, 7, 5, 8, 4, 9, 9, 8, 0, 10, 10],
[10, 12, 10, 12, 12, 14, 15, 14, 14, 10, 17, 10, 12, 4, 17, 10, 0, 0],
[10, 12, 10, 12, 12, 14, 15, 14, 14, 10, 17, 10, 12, 4, 17, 10, 0, 0],
]
data["num_vehicles"] = 2
data["starts"] = [0, 1]
data["ends"] = [16, 17]
data["pickups_deliveries"] = [(10, 11), (12, 13), (14, 15)]
data["obligations"] = [
0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, None, None, 0, 1
]
data["demands"] = [
0, 0, 3, 3, -1, -1, -1, -1, -1, -1, 1, -1, 1, -1, 1, -1, 0, 0
]
data["vehicle_capacities"] = [8, 8]
data["point_types"] = [
"start", "start", "onboard", "onboard", "delivery", "delivery",
"delivery", "delivery", "delivery", "delivery", "pickup", "delivery",
"pickup", "delivery", "pickup", "delivery", "finish", "finish",
]
data["time_windows"] = [
(0, 0), (0, 0), (0, 0), (0, 0), (0, 9), (0, 11), (0, 11), (0, 4),
(0, 4), (0, 10), (8, 15), (0, 23), (9, 17), (0, 32), (4, 30), (9, 45),
(0, 79), (0, 119),
]
data["disjunction"] = [(14, 15)]
data["initial_routes"] = [[2, 4, 6, 5, 10, 11], [3, 8, 7, 9, 12, 13]]
return data
def add_time_dimension(
data,# : dict[str, Any],
manager: RoutingIndexManager, routing: RoutingModel
) -> RoutingDimension:
def time_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
#return data["time_matrix"][from_node, to_node]
return data["time_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_callback)
routing.AddDimension(
evaluator_index=transit_callback_index,
slack_max=8 * 60, # allow waiting time
capacity=8 * 60, # maximum time per vehicle
fix_start_cumul_to_zero=False, # force start cumul to zero
name="Time",
)
time_dimension = routing.GetDimensionOrDie("Time")
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
time_dimension.SetSpanCostCoefficientForAllVehicles(100)
return time_dimension
def get_index(
manager: RoutingIndexManager,
ind: int,
routing: RoutingModel,
obligations #: list[int | None],
) -> int:
if manager.NodeToIndex(ind) != -1:
index_node = manager.NodeToIndex(ind)
else:
index_node = routing.End(obligations[ind])
return index_node
def time_window_constr(
data, #: dict[str, Any],
manager: RoutingIndexManager,
routing: RoutingModel,
time_dimension: RoutingDimension,
penalty: int = 10000
) -> None:
for ind, (pt, tw) in enumerate(zip(data["point_types"], data["time_windows"])):
index = get_index(manager, ind, routing, data["obligations"])
if pt not in ("delivery", "finish"):
time_dimension.SetCumulVarSoftLowerBound(index, tw[0], int(10e6))
time_dimension.SetCumulVarSoftUpperBound(index, tw[1], penalty * 2)
def disjunction_constr(
data, #: dict[str, Any],
manager: RoutingIndexManager,
routing: RoutingModel,
penalty: int = 10000
) -> None:
for pickup, delivery in data["disjunction"]:
node_ids = [manager.NodeToIndex(pickup), manager.NodeToIndex(delivery)]
routing.AddDisjunction(node_ids, penalty, 2)
def pickup_delivery_constr(
data, #: dict[str, Any],
manager: RoutingIndexManager,
routing: RoutingModel,
time_dimension: RoutingDimension,
) -> None:
for pickup, delivery in data["pickups_deliveries"]:
pickup_index = get_index(manager, pickup, routing, data["obligations"])
delivery_index = get_index(manager, delivery, routing, data["obligations"])
# Ускоряет оптимизацию
routing.AddPickupAndDelivery(pickup_index, delivery_index)
# pickup и delivery на одной машине и активны
routing.solver().Add(
routing.ActiveVar(pickup_index) * routing.VehicleVar(pickup_index)
== routing.ActiveVar(delivery_index) * routing.VehicleVar(delivery_index)
)
# pickup меньше или равен delivery по времени
routing.solver().Add(
time_dimension.CumulVar(pickup_index)
<= time_dimension.CumulVar(delivery_index)
)
def capacity_constr(
data, # : dict[str, Any],
manager: RoutingIndexManager,
routing: RoutingModel
) -> None:
def demand_callback(from_index):
from_node = manager.IndexToNode(from_index)
return data["demands"][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
evaluator_index=demand_callback_index,
slack_max=0, # null capacity slack
vehicle_capacities=data["vehicle_capacities"], # vehicle maximum capacities
fix_start_cumul_to_zero=True, # start cumul to zero
name="Capacity",
)
def obligation_constr(
data, #: dict[str, Any],
manager: RoutingIndexManager,
routing: RoutingModel
) -> None:
for node_idx, obligation in enumerate(data["obligations"]):
index = get_index(manager, node_idx, routing, data["obligations"])
if obligation is not None:
routing.VehicleVar(index).SetValue(obligation)
def get_search_params() -> DefaultRoutingSearchParameters:
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = 8
search_parameters.local_search_metaheuristic = 2
search_parameters.solution_limit = 500
search_parameters.time_limit.seconds = 3
return search_parameters
def print_solution(data, manager, routing, solution):
print(f"Objective: {solution.ObjectiveValue()}")
max_route_distance = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
while not routing.IsEnd(index):
plan_output += f" {manager.IndexToNode(index)} -> "
index = solution.Value(routing.NextVar(index))
route_distance += assignment.Min(time_dimension.CumulVar(index))
plan_output += f"{manager.IndexToNode(index)}\n"
plan_output += f"Time of the route: {route_distance} minutes \n"
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print(f"Maximum of the route: {max_route_distance} minutes")
if __name__ == "__main__":
data = create_data_model()
manager = pywrapcp.RoutingIndexManager(
len(data["time_matrix"]), data["num_vehicles"], data["starts"], data["ends"]
)
routing = pywrapcp.RoutingModel(manager)
# constraints
time_dimension = add_time_dimension(data=data, manager=manager, routing=routing)
time_window_constr(
data=data,
manager=manager,
routing=routing,
time_dimension=time_dimension,
)
pickup_delivery_constr(
data=data, manager=manager, routing=routing, time_dimension=time_dimension
)
capacity_constr(data=data, manager=manager, routing=routing)
obligation_constr(data=data, manager=manager, routing=routing)
disjunction_constr(data=data, manager=manager, routing=routing)
# solutions
search_parameters = get_search_params()
# Применяем все объявленные параметры для поиска решения
routing.CloseModelWithParameters(search_parameters)
initial_solution = routing.ReadAssignmentFromRoutes(
data["initial_routes"], True
)
assignment = routing.SolveFromAssignmentWithParameters(
initial_solution, search_parameters
)
print_solution(data, manager, routing, assignment)У вас абсолютно правильный код, это я допустил ошибку в методе
add_time_dimension. Ваш вариант правильный:
return data["time_matrix"][from_node][to_node]
До этого еще я поправил функцию print_solution сейчас она должна быть правильной.
Замените ее и получите правильное решение. Спасибо вам за внимательность!
Спасибо за материал! Проводили тестирование производительности библиотеки?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Ortools — библиотека для решения задачи VRP