Разработка алгоритма маршрутизации транспортных средств / планирования ресурсов

Question

Мой первый пост здесь - надеюсь, что вы можете помочь мне с разработкой алгоритма, который я уже некоторое время рассматриваю - не уверен, какой подход выбрать (VRPTW или планирование ресурсов или что-то еще полностью!?)

Чтобы привести это в реальный пример, у нас есть много садовых отходов в небольшом количестве мест (обычно менее 5). Все отходы должны быть перевезены в другие места в течение определенного периода времени. Для перемещения садовых отходов у нас есть прицепы, которые необходимо буксировать на автомобилях. Садовые отходы могут быть сброшены на склад отходов только в определенное время (временные окна). В некоторых местах мы можем скинуть трейлер, чтобы люди там его заправили или опорожнили, но в других местах водитель автомобиля должен сделать это сам, а машина должна оставаться там. Все сроки могут быть рассчитаны (то есть время загрузки / выгрузки, время транзита и т. Д.). Автомобили могут перемещаться между участками без прицепа, прицепы могут буксироваться пустыми, но прицепы не могут перемещаться между местами.

Наша цель - обеспечить перевозку всех отходов прицепа, пока

• сведение к минимуму количества используемых прицепов и легковых автомобилей
• соблюдение всех временных окон для сброса отходов
• «балансировка» трейлеров - то есть в конце дня у нас в каждом месте столько же трейлеров, сколько было в начале дня

Я думал о том, чтобы подходить к этому как к алгоритму планирования ресурсов, но я не уверен, как справиться с «балансировкой» трейлеров.

Еще один метод, который я рассмотрел, - это сначала рассмотреть автомобили. Затем я мог бы выбрать самую раннюю задачу и построить график всех выполнимых задач после этого. Если бы я тогда выбрал самый длинный путь на графике, который бы обслуживал максимальное количество грузовых прицепов. Затем я могу удалить эти задачи из списка задач и повторять, пока все задачи не будут обслужены. Затем мне нужно будет просмотреть список загруженных прицепов, чтобы определить необходимое количество прицепов.

Будем благодарны за любые мысли о подходе!

Answer 1

Я согласен с Джири ... вам нужен эвристический алгоритм, который достаточно быстро приближается к приемлемому решению, а затем уточняет.

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

1. [Начало] Генерация случайной популяции из n хромосом (подходящие решения для проблемы)
2. [Пригодность] Оцените пригодность f (x) каждой хромосомы x в популяции

3. [Новая популяция] Создайте новую популяцию, повторяя следующие шаги, пока новая популяция не будет завершена

   [Выбор] Выберите две родительские хромосомы из популяции в зависимости от их пригодности (чем лучше приспособленность, тем больше шансов быть отобранным)

   [Кроссовер] С вероятностью кроссовера пересекают родителей, чтобы сформировать новое потомство (детей). Если кроссовер не проводился, потомок является точной копией родителей.

   [Мутация] С вероятностью мутации мутировать новое потомство в каждом локусе (положение в хромосоме).

   [Принятие] Поместить нового потомства в новую популяцию

4. [Заменить] Использовать новую сгенерированную популяцию для дальнейшего запуска алгоритма
5. [Тест] Если конечное условие удовлетворено, остановите и верните лучшее решение из текущей совокупности
6. [Петля] Перейти к шагу 2

Хитрость в этом заключается в том, чтобы кодировать ваши ограничения в «хромосому» и писать функцию «пригодности». Функция пригодности должна принимать входные данные о результатах потенциального решения и выводить оценку того, насколько хорошим является решение, или выбрасывать его, если оно нарушает какое-либо из ограничений.

Как упомянул Jiri, преимущество этого решения состоит в том, что оно дает работоспособный, хотя, возможно, и не лучший, ответ очень быстро, и чем дольше вы позволяете ему работать, тем лучше становится решение.

Answer 2

Мы, безусловно, говорим здесь полный алгоритм NP, за исключением некоторого количества автомобилей и трейлеров, это не будет задачей, в которой вы найдете лучшее решение из всех возможных решений, а затем сможете отказаться от него и пойти снова. чтобы избежать самого длинного пути, как вы предлагаете. Если вы разрабатываете свой алгоритм таким образом, очень вероятно, что однажды вы добавите немного больше автомобилей и трейлеров, и он никогда не закончит вычислять решение.

Вы, вероятно, хотите использовать алгоритм, который может достаточно быстро генерировать достаточно хорошее решение проблемы. Убедитесь, что вы создали метрику для качества решения, у вас есть хороший способ оценить значение метрики для идеального решения, а затем задайте себе несколько процентов, в пределах которых вы хотите, чтобы ваше решение было идеальным решением, и просто возьмите первое решение, которое имеет метрику в пределах. Это дает дополнительное преимущество: если этот алгоритм занимает слишком много времени для вычисления и вы прерываете его, вы все равно можете использовать решение с наименьшей вычисленной метрикой, даже если оно не находится в ожидаемых пределах.

Я не уверен, какой подход к решению проблемы, хотя сам. Я бы предложил прочитать несколько статей после поиска на acm portal . Я бы предположил, что у UPS и Fedex, вероятно, есть похожие проблемы, если вы добавите их в качестве ключевых слов в поиск в Google, вы можете получить более полезные результаты.

Answer 3

Локальный поиск является альтернативой генетическим алгоритмам. В International Timetabling Competition 2007 алгоритмы локального поиска (такие как поиск по табу и имитация отжига) явно превосходят записи генетического алгоритма (1–4-е место для LS по сравнению с 5-м местом для GA на дорожке 1 из 80) конкуренты IIRC).

Кроме того, взгляните на некоторые библиотеки, такие как OptaPlanner (Поиск по Табу, Имитация отжига, Позднее принятие, с открытым исходным кодом, Java), JGap (генетические алгоритмы, с открытым исходным кодом, Java) ), OpenTS (Поиск по Табу, ...

Answer 4

Общий подход:

Поскольку проблема невелика, я бы предложил подход, при котором вы добавляете автомобили и трейлеры до тех пор, пока не получите приемлемое решение, а не пытаетесь минимизировать количество автомобилей и трейлеров.

Решение:

Я имел меньший успех на GA с ограничениями и еще меньше на GA с ограничениями на целочисленные переменные (например, количество трейлеров в локации). Может оказаться, что программирование с ограничениями является лучшим подходом, поскольку вы просто хотите сгенерировать выполнимое решение для заданного количества автомобилей и прицепов, а не пытаться минимизировать пройденное расстояние.

Замечание:

Вы решаете проблему в сети, где последними ходами может быть перемещение пустого трейлера.

Удачи!

Answer 5

Я склонен согласиться с Робертом. Для меня это звучит как действительно хороший кандидат на метод эволюционной оптимизации, такой как реализация Генетического алгоритма, которую он описывает.

У меня также был очень хороший успех по определенным проблемам с Оптимизацией роя частиц (PSO). По сути, вы можете думать о каждом геноме как о частице в неком многомерном пространстве. Координаты частицы являются параметрами вашего расчета (фитнес-функция). Каждая частица запускается случайным образом со случайной скоростью. Для каждой итерации моделирования вы обновляете положение каждой частицы с помощью ее текущего вектора перемещения, а затем добавляете компоненты других векторов, такие как: направление на лучшую частицу на данный момент, направление на лучшую частицу за всю историю, направление на локальную группу лучший и т.д ...

Поначалу может показаться довольно сложным реализовать GA или PSO, но я уверяю вас, что легко написать небольшую структуру, которая абстрагирует алгоритм (GA / PSO) от фактической проблемной области, которую вы пытаетесь оптимизировать. Вы всегда можете обратиться к Википедии за подробной информацией об алгоритмах.

После того, как у меня есть фреймворк, я обычно начинаю с проблемы с 2 параметрами (возможно, это упрощение вашей проблемы, или расположения X и Y на изображении), так что я могу легко визуализировать и настроить алгоритм, чтобы получить хороший результат. роящееся поведение. Затем я масштабирую его до большего размера.

Мне нравится этот подход, потому что он позволяет мне легко оптимизировать задачи, которые имеют довольно сложные и запутанные детали для фактической постановки задачи (например, автомобили и прицепы).

Кроме того, почему эволюционные методы привлекательны, потому что вы можете посвятить определенную часть времени моделированию и получить наилучший ответ, когда решите остановиться.

По моему опыту, вы тратите столько времени на настройку параметров для GA или PSO (как только у вас есть реализация), чем на написание жестко закодированного эвристического решения, но выгода в том, что вы меняете стратегию поиска решение обычно требует только изменения параметров или замены очень хорошо определенных алгоритмов с другой реализацией, в отличие от кодирования совершенно другой стратегии для решения проблемы эвристически с нуля.

Пожалуйста, напишите мне, если вам нужно руководство по разработке общих структур для любого из двух алгоритмов. Я должен отметить, что вы также получаете несколько хороших бесплатных сторонних фреймворков. Иногда мне нравится кодировать свои собственные, потому что я понимаю каждый аспект алгоритма и знаю, где я могу изменить стратегию.