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

StackOverflow https://stackoverflow.com/questions/1925439

Вопрос

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

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

Наша цель – обеспечить транспортировку всех прицепов с отходами при

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

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

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

Любые мысли о подходе будут оценены по достоинству!

Это было полезно?

Решение

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

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

  1. Start] генерируйте случайную популяцию n хромосом (подходящие решения для проблемы)
  2. Фитнес] Оценить пригодность F (x) каждой хромосомы x в популяции

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

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

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

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

    Принимая] поместите новое потомство в новое население

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

Основной подход:

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

Решение:

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

Наблюдение:

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

Удачи !

Локальный поиск являются альтернативой генетическим алгоритмам. в Международный соревнование по расейным срокам 2007, локальные алгоритмы поиска (такие как поиск в табу и моделируемый отжиг) четко превзошли записи генетического алгоритма (от 1 до 4 -го места для LS против 5 -го места для GA в треке 1 из примерно 80 конкурентов IIRC).

Кроме того, взгляните на некоторые библиотеки, такие как Optaplanner (Поиск табу, смоделированный отжиг, позднее принятие, открытый исходный код, Java), JGAP (генетические алгоритмы, открытый исходный код, Java), Opents (Tabu Search, ...

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top