English version VrpPd Vehicle Routing Software(in English)

Программа "Задача Коммивояжёра в городе"

И не только в городе,и не только коммивояжера.

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

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

Для решения подобной задачи и предлагается программа "Задача коммивояжера в городе". Она абсолютно бесплатна. Требует для своей работы , чтобы на компьютере была установлена версия DotNet не ниже 4.0.

Ссылка на архив с программой - ниже а этой странице.

(Если вас интересует программа, которая просто решает задачу коммивояжера - вам сюда ATspCalc.)

Рассмотрим на примере как она работает.

1.Ввод расстояний между участками (точками).

Перед использованием программы необходимо вести план вашего города (района,страны - что для вас актуально). Это делается один раз.В будущем в этот план можно вносить коррекции,если это потребуется. Для этого нужно разделить город на небольшие участки.В центре каждого участка выбрать точку. Затем нужно узнать расстояние между этими точками.В общем случае оно не будет равно туда и обратно, т.к. в любом городе существуют односторонние улицы, объезды и т.д.Расстояния, в зависимости от ваших задач, могут быть и в единицах расстояния и в единицах времени и в денежных единицах. Архив программы включает в себя тестовые даные (файл spsl.mdb).Этот файл должен располагаться в том же каталоге, что и сама программа (spsl.exe).В нём хранится описание вашей "карты".При удалении этого файла, программа создаст новый, пустой.Тестовые данные позволяют вам попробовать как работает программа без всяких усилий. Этот файл - в формате Microsoft Access.Поэтому вы можете заполнять его как через интерфейс программы,так и с помощью любой подходящей внешней программы - структура данных тривиальна.


В версии 1.0.1.5 добавлен режим импорта данных из файла с GPS координатами точек. Главное меню => Дополнительные команды => Импортировать данные (GPS).Файл - обычный текстовый , (в кодировке UTF-8) следующего формата :

[Наименование точки] табуляция [Доп.Информация] табуляция [Широта] табуляция [Долгота]

Образец такого файла Metro.txt включён в архив с программой.

При импорте, программа читает точки с указанными координатами из файла, строит все возможные соединения между ними,затем оставляет только те соединения, которые входят в минимальное остовное дерево и те, длина которых < 0.588 средней длины соединений, входящих в остовное дерево.После этого вы можете откорректировать полученные данные вручную.(Если этого не делать - у вас получится слишком много лишних соединений.)

Это может значительно облегчить построение вашей карты.

В версии 1.0.1.6 добавлены два новых режима импорта : Импортировать данные (XYZ) - - текстовый файл (в кодировке utf-8) формата :

[Наименование точки] табуляция [Доп.Информация] табуляция [X-коорд.] табуляция [Y-коорд.] табуляция [Z-коорд.]

Остальное - как в предыдущем режиме.

Импортировать текстовые данные - текстовый файл (в кодировке utf-8) формата :

[Наименование точки 1] табуляция [Наименование точки 2] табуляция [расстояние от точки 1 до точки 2] табуляция [расстояние от точки 2 до точки 1]

Если расстояние от точки 1 до точки 2,например ,не задано - поле должно быть пустым.


Итак, при запуске программы вы увидите первое окно предназначенное для ведения/коррекции данных вашей "карты":

Окно ввода точек

В этом окне, вы можете добавить, удалить, или изменить информацию о точках. После любых изменений точек вы должны сохранить изменения в БД (кнопка "Сохранить"). Номер точки должен быть уникален. Если вы не хотите сохранять изменения просто выйдите из программы и войдите ещё раз.(Внимание : Если вы удаляете точку - удаляются и все, связанные с ней расстояния.) После этого вы можете задать расстояния от конкретной точки до всех остальных точек - кнопка "Расст.от" у конкретной точки.(Расст.до - рассояния в обратном направлении - от других точек , до данной ). После её нажатия вы увидите такое окно:

Окно установки рассояний

Автоматически появляются все возможные точки,до которых можно задать расстояние. Корректируется только одно поле - "Расстояние".Если прямой связи в данную точку нет, то поле должно быть пустым.Расстояние обязательно должно быть больше или равно 0. При нажатии на Ok - изменения сохраняются, Cancel или закрыть окно - изменения теряются.

Если информация о точках и расстояниях между ними вас устраивает,вы нажимаете кнопку "Вперёд". Появится окно, в котором вы можете выбрать точки для посещения и количество транспортных средств.

2.Окно выбора точек для посещения и количества транспортных средств.

Окно выбора точек для посещения и количества транспортных средств

С левой стороны вы можете выбираете необходимые точки маршрута. Когда вы нажмёте на кнопку "->" и они переместятся в правый список точек для посещения. Внимание - первая точка в правом списке считается началом маршрута. Именно из неё транспортные средства отправляются в путь и в неё же должны вернуться. Если вы хотите убрать точку из уже выбраных - выделите её в правом списке и нажмите кнопку "<". В поле "Число тр.ср-в." - задаётся число транспортных средств,которые планируется использовать для объезда точек.

Режимов оптимизации три - (имеет смысл только, если тр.ср-в. больше одного): "Мин.маршрут для всех тр.с-в." - в этом режиме производится поиск маршрута обхода заданных точек с минимальной суммарной длиной маршрута всех тр.ср-в. При этом длины пути каждого из транспортных средств могут довольно сильно отличаться. В режиме "Мин.маршрут для каждого тр.с-в." - критерий оптимизации несколько иной - ищется минимум суммы квадратов путей,проходимых каждым из транспортных средств.При этом,общий путь всех транспортных ср-в может быть несколько больше, чем в предыдущем режиме, но длины пути для каждого из транспортных средств могут отличаться намного меньше.Т.е.программа старается выровнять длину маршрута для каждого тр.ср-ва. В режиме "Выровнять к-во точек" - программа старается проложить маршруты так, чтобы количество посещаемых каждым тр.ср-вом. точек - совпадало.

Вообще,в случае одного тр.ср-ва - задача эквивалентна "Задаче коммивояжёра"(TSP). В случае нескольких тр.ср-в - это уже одна из разновидностей задачи маршрутизации тр.ср-в. (английская аббревиатура VRP - Vehicle routing problem).

Итак,если хотите вернуться к первому экрану - жмёте "Назад". Для продолжения работы жмёте кнопку "Вперёд". И попадаете на следующее окно.

3.Окно результатов.

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

Окно результатов

Т.е. будет виден список пунктов маршрута,расстояния между ними и промежуточные участки маршрута, для каждого транспортного средства.

А в буфер обмена (Clipboard) будет скопирован следующий текст - это даёт возможность скопировать его в любую внешнюю программу, откорректировать и распечатать.

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

Вы можете вернуться в окно выбора точек нажав кнопку "Назад", изменить условия и повторить расчёт. Это поможет вам быстро подобрать приемлемый для вас вариант.Скорость работы вы можете оценить сами. Программа работает следующим образом.Вначале ищутся кратчайшие пути между выбранными вами точками, в том числе,и через промежуточные точки на вашей "карте". Затем производится поиск кратчайшего пути обхода выбранных точек по этим путям( используется техника "имитации отжига" и локальный поиск ),c учётом заданных критериев поиска.Но перед поиском кратчайшего маршрута, программа ищет любой маршрут, проходящий через все заданные точки,чтобы в дальнейшем его оптимизировать.Она делает это последовательно проверяя все возможные варианты. И если программа "виснет" - скорее всего у вас недостаточно расстояний между точками,чтобы построить такой маршрут.

Вы можете загрузить архив программы с тестовыми данными : spsl.zip (версия 1.2.0.0) на свой компьютер, (при условии, что вы согласны, что автор не отвечает за работоспособность программы и полученные с помощью неё результаты,кроме того эта версия программы-исключительно для некоммерческого использования.) Скопировав архив в любой каталог на своём компьютере, распакуйте его. Получится два файла : spsl.exe - собственно сама программа,spsl.mdb - тестовые данные. В этой версии максимальное количество точек , которые можно выбрать для посещения - 56 , а максимальное количество транспортных средств, которые можно задать - 8.(Дальше - за деньги :)).

Демонстрация работы

© 2010-2015 Если у вас есть предложения, пожелания,отзывы, заказы - пишите на shobb@narod.ru

SoftNew.ru  
Rambler's Top100