Архив форума

Решение задачи комивояжера в Excel  
Ситало Николай Анатольевич работаю в транспортной логистике 5лет в течение этого времени столкнулся с рядом вопросов транспортной логистики, которые необходимо решать или приблизится максимально к оптимальному решению.
 
Речть пойдет о поиске кратчайшего кольцевого маршрута для транспорта, задачу решаем с помощью средств VBA в Excel, которые могут стать неотъемлемой частью в вашей повседневной работе.
 
Задача комивояжера (поиск кратчайшего пути, проходя каждый город только по одному разу). Все знают что задача является NP-трудной, то есть простым перебором она решается (только при малом колличестве n-городов) сложность решения составляет n! факториал.
 
Решать задачу мы будем с помощью алгоритма муравья, автором которого является Марко Дориго. Для создания программы я пользовался обычным VBA и Excel 2007.
 
Функциональное назначение "Engine_Ants"
1. Нахождение кратчайшего маршрута в полном графе.
2. Определение веса точки в маршруте.
3. Создание оптимального маршрутного листа.
4. Создание исходного маршрутного листа.
5. Создание файла отчета.
6. Работа с координатами WGS-84 и Декартовой системой.
7. Расчет отсутствующих расстояний формулами сферической геометрии.
8. Аппроксимирование расчетных расстояний на указанный процент.
9. Объединение и упорядочивание таблиц расстояний.
10.Дробление таблиц расстояний.
11.Позволяет создавать таблицы расстояний в формате заданным пользователем.
 
Программу я использую сам в своей работе, испытанно на 177городах Львовской области, приближенный кратчайший маршрут для одного автомобиля найден, его можно увидеть визуально, отправлю по эл. почте.
 
Простота и удобство в работе гарантированны, какие-то дополнительные знания не требуются.
 
Стоимость своей работы оцениваю в 0$ (договорная).
Торг всегда уместен!!!
Предлагайте, найдем приемлемое решение.
 
 
Пишите, также для начала могу выслать подробный файл справки по "Engine_Ants".
 
Программа развивается постоянно, следующий шаг, кэширование данных при длительной работе алгоритма с целью последующего запуска с места остановки.
 
 
С уважением, Ситало Н.А.
 
Электронный адрес: [email protected]
Контактный телефон: +3(8096) 936 96 70
http://algoexcel.blogspot.com