Я считаю, что чтение всех значений присвоения, полученных из
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_vars = [time_dimension.SlackVar(x) for x in indices]
slacks = [assignment.Value(x) for x in slack_vars]
Сбой программыс сообщением:
SystemError: возвратил NULL без установки ошибки
, что говорит о том, что time_dimension не имеет переменной слабины для каждого индекса.Это правильно?Почему бы и нет?
Спасибо за чтение этого чрезмерного поста.Вот два вопроса:
- Можно ли определить временные окна прибытия и отправления для депо?
- Как правильно прочитать слабые места для временных окон для всех узлов, включаяДепо?