Формирвоание маршрутов можно свести к решению задачи коммивояжера с дополнительными ограничениями. Давайте поставим задачу.
Дано:
- Некоторое количество торговых точек (ТТ), обычно 50-500
- Вес товара, который необходимо доставить в каждую ТТ
- Некоторое количество машин с ограниченными вместимостью 1500 кг и ограниченными человеческими ресурсами - не более 15 магазинов в день
Необходимо:
Найти оптимальный маршрут с минимальным количеством машин и минимальнцым расстоянием доставки (пробегом)Существует несколько способов решения этой задачи
- Традиционный - деление по районам
- Перебор - для 100 точек потребуется 100! итераций, а это ОЧЕНЬ много
- Жадный алгоритм - вседа выбираем ближайшую точку, к сожалению, алгоритм дает иногда самый не оптимальный вариант
- Генетический алгоритм
- Алгоритм муравьиной колонии
-
Краткое описание алгоритма
Описание структуры данных:
Популяция состоит из Генов - возможные решения. Каждый Ген имеет стоимость, стоимость состоит из расстояния, пройденного машиной и весом, который эта машина перевозит.
- Формируем начальную популяцию. Можно формировать случайно, по районам или по жадному алгоритму
- Запускаем цикл (чем больше итераций тем лучше).
- Генерируем потомков только у лучших генов
- Сортируем по возрастанию стоимости
- "Элита" остается, остальные "умирают"
Сходимость решения во многом зависит от начальной выборки и параметров алгоритма. Значения параметры получены экспериментальным путем, возможно для кого-то существуют более оптимальные...
Добавлено разделение ТТ по районам и расстояния между районами.
P.S. Огромная благодарность рябятам создавшим и развивающим проект 1С++!!! Так держать! Вы молодцы!
