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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение:

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

Наблюдение:

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

Удачи !

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

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