Самовывоз и доставка ВСП с точками агрегации

Я пытаюсь решить простую VRP по вывозу и доставке только для одного автомобиля с помощью or-tools. Я следил за документами https://developers.google.com/optimization/routing/pickup_delivery, и кажется, что все работает, как ожидалось, когда все точки приема и высадки отличаются друг от друга. Массив pickups_deliveries выглядит так:

data['pickups_deliveries'] = [
        [1, 6],
        [2, 10],
        [4, 3],
        [5, 9],
        [7, 8],
        [15, 11],
        [13, 12],
        [16, 14],
    ]

Однако предположим, что есть точки агрегации, где нужно забрать более одной посылки, а у курьера неограниченное пространство. Я пытался изменить приведенный выше пример, чтобы использовать один и тот же индекс получения в нескольких парах получения / доставки:

data['pickups_deliveries'] = [
        [1, 6],
        [2, 10],
        [2, 3],
        [2, 9],
        [1, 8],
        [1, 11],
        [2, 12],
        [2, 14],
    ]

Результатом, которого я ожидал, было всего 2 остановки и 8 доставок, но, к сожалению, когда я запускаю решатель, он возвращает None.

solution = routing.SolveWithParameters(search_parameters) # returns None

Есть ли способ обойти это или я упускаю что-то более важное? Я новичок в этой библиотеке, поэтому любые указания были бы очень признательны.


python or-tools vehicle-routing
person user1013607    schedule 25.06.2021    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы должны продублировать узел 2, чтобы он участвовал только в одном P&D.

Обратите внимание, что каждое место можно посетить только один раз!

person Mizux    schedule 26.06.2021
comment
Спасибо, это пролило свет на мою проблему! Я обошел это, создав фиктивные узлы, содержащие те же координаты, и после запуска решателя сопоставил индексы результатов с коллекцией, из которой были получены входные данные. У последнего есть дополнительные метаданные, поэтому я могу отфильтровать все, что угодно. - person user1013607; 28.06.2021