Я нахожу чтение всех значений присваивания, полученного из
assignment = routing.SolveWithParameters(search_params)
Проблем маршрутизации с временными окнами довольно сложно. Прежде всего, это узлы и индексы. Я получаю индексы транспортного средства (маршрута) через
index = routing.Start(vehicle)
indices = [index]
while not routing.IsEnd(index):
index = assignment.Value(routing.NextVar(index))
indices.append(index)
и соответствующие узлы получаются
nodes = [routing.IndexToNode(x) for x in indices]
Для конкретной задачи маршрутизации с 5 остановками и depot=0
решатель находит назначение со следующими индексами и узлами:
vehicle: 0
indices: [0, 1, 6]
nodes: [0, 1, 0]
vehicle: 1
indices: [5, 4, 3, 2, 7]
nodes: [0, 4, 3, 2, 0]
Таким образом, индексов на три больше, чем узлов, потому что каждое транспортное средство начинается и заканчивается в депо. Я определил стоимость 1 для каждого транзита и прочитал значения стоимости через
cost_dimension = routing.GetDimensionOrDie("cost")
cost_vars = [cost_dimension.CumulVar(x) for x in indices]
costs = [assignment.Value(x) for x in cost_vars]
кажется, работает:
vehicle: 0
indices: [0, 1, 6]
nodes: [0, 1, 0]
costs: [0, 1, 2]
vehicle: 1
indices: [5, 4, 3, 2, 7]
nodes: [0, 4, 3, 2, 0]
costs: [0, 1, 2, 3, 4]
Но когда я добавляю ограничения по времени, я сталкиваюсь с проблемами. Давайте сначала посмотрим на код, определяющий проблему. Единица времени - минуты.
def time_function(x,y):
return 30
evaluator = time_function
slack_max = 40
capacity = 24*60
fix_start_cumul_to_zero = False
name = "time"
routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)
time_dimension = routing.GetDimensionOrDie("time")
time_windows = [(7*60, 8*60),(9*60, 10*60),(9*60, 10*60),
(9*60, 10*60),(9*60, 10*60)]
for node, time_window in enumerate(time_windows):
time_dimension.CumulVar(node).SetRange(time_window[0], time_window[1])
routing.AddToAssignment(time_dimension.SlackVar(node))
Таким образом, каждая поездка занимает 30 минут, автомобили могут простаивать на остановке в течение 40 минут (slack_max=40
), а каждую остановку следует обслуживать с 9:00 до 10:00. Ограничения диапазона, которые вводятся через time_windows[0]
, предназначены для определения времени начала каждой утренней поездки. Но поскольку депо является первой и последней остановкой каждого маршрута, их также можно интерпретировать как вечернее время прибытия.
Итак, вот моя первая трудность с временными окнами: депо появляется дважды на каждом маршруте, но ограничение диапазона определяется на узлах. Я предполагаю, что модель маршрутизации не рассчитана на два окна для депо?
Позвольте мне перейти ко второй части моего вопроса. Я установил fix_start_cumul_to_zero = False
, чтобы маршруты могли начинаться в любой момент. Также обратите внимание, что routing.AddToAssignment(time_dimension.SlackVar(node))
должен предоставить мне доступ к переменным Slack позже. Теперь, когда я проверяю значения времени для каждого индекса с помощью
time_vars = [time_dimension.CumulVar(x) for x in indices]
times.append([assignment.Value(x) for x in time_vars])
сформированный с помощью datetime, я получаю разумные результаты:
vehicle: 0
indices: [0, 1, 6]
nodes: [0, 1, 0]
costs: [0, 1, 2]
times: ['7:50:00', '9:00:00', '9:30:00']
vehicle: 1
indices: [5, 4, 3, 2, 7]
nodes: [0, 4, 3, 2, 0]
costs: [0, 1, 2, 3, 4]
times: ['7:50:00', '9:00:00', '9:30:00', '10:00:00', '10:30:00']
Решатель явно предпочитает раннее время отправления. Учитывая максимальный резерв в 40 минут, каждое транспортное средство также может заводиться немного позже, например в 8 часов утра.
Проблема начинается, когда я пытаюсь прочитать переменные Slack через
slack_vars = [time_dimension.SlackVar(x) for x in indices]
slacks = [assignment.Value(x) for x in slack_vars]
Программа вылетает с сообщением:
SystemError: вернул NULL без установки ошибки
что говорит о том, что time_dimension
не имеет переменной резерва для каждого индекса. Это правильно? Почему нет?
Спасибо, что прочитали этот чрезмерный пост. Вот два вопроса:
- Можно ли определить временные окна прибытия и отправления для депо?
- Как правильно читать слэки временных окон для всех узлов, включая депо?