Есть ли эффективный алгоритм оптимизации многокритериальной транспортной задачи?
Добрый день! Подскажите какой наиболее эффективный алгоритм для решения транспортной задачи с многими критериями, т.е. есть несколько складов в разных точках города и несколько заказчиков, также есть несколько разных машин, есть временные рамки и прочие критерии, соответственно надо развести все грузы машинами оптимально.
Пока пробую генетический алгоритм, но что-то не очень получается. Может есть более подходящий алгоритм для решения такой задачи?
Извините, но - генетический алгоритм.
Занимался (в составе коллектива) примерно такой же задачей.
Динамическое программирование позволяло решить оптимально субзадачу примерно в четверть от требовавшегося объема.
Соответственно имелась возможность сверять ошибку генетического алгоритма от оптимального только на уменьшенном объеме - выходило в диапазоне от 0.5% до 2%. При этом по скорости такая субзадача решалась динамическим программированием за 2 часа на 1 сервере (очень много вычислений шло в swap), генетический же алгоритм стабилизировался (с указанной выше ошибкой) примерно через минуту.
А какие скрещивание и мутацию использовали? Fitness функция была составлена для 1 параметра или сразу для всех. Нагуглил, что при нескольких критериях, запускаются в несколько потоков, при чем в каждой оптимизируется только по 1 параметру.
Наши условия были специфическими. Если перекладывать на Ваши термины (боюсь, что что-то из этого у Вас будет по-другому), то хромосомы кодировали для каждого дня в ближайшем месяце или квАртале, повезут или нет конкретный груз (пара "отправитель-получатель") и каким курьером. Соответственно, мутации - изменения 1-2-3 дней/курьеров, скрещивания - "продольное" (обмен курьерами (естественно с некоторой эвристикой) внутри группы из нескольких пар "отправитель-получатель") и "поперечное" (обмен курьерами (естественно с некоторой эвристикой) между всеми парами, но в рамках небольшого периода времени (1-10 дней)).
нафиг эту генетику, "имитация отжига" посмотрите книгу Скиены "Алгоритмы. Руководство по разработке." Там есть справочник с кучей ссылок на литературу, алгоритмы, реализации.
@sim3x, " Я лично никогда не сталкивался ни с одной задачей, для решения которой генетические алгоритмы оказались бы самым подходящим средством. Более того, я никогда не встречал никаких результатов вычислений, полученных посредством генетических алгоритмов, которые производили бы на меня положительное впечатление." цитата С.Скиены из этой книги, есть в Википедии:
