Практическое применение ГИС: решение задачи коммивояжера
Известна классическая задача исследования операций, которая в различных модификациях решается для оптимизации процессов 119 в логистике, при сплошном обследовании населенных пунктов в каком-либо регионе в связи с экономическими, экологическими или медицинскими проблемами, а также в зонах чрезвычайных ситуа ций. Она получила название «задачи коммивояжера». Рассмотрим две практические разновидности этой задачи, решение которых невозможно без применения ГИС. П р и м е р 2. Постановка задачи коммивояжера с привязкой к до рожной сети. В регионе с развитой сетью дорог имеются: • множество М населенных пунктов; • множество N перекрестков (развилок) вне населенных пулктов; • множество К участков дорог. Участком дороги назовем дорогу от пункта А до пункта Б, причем Л, Б - это населенный пункт или перекресток. Необходимо составить такой маршрут посещения населенных пун ктов, чтобы длина маршрута, включая суммарные повторные пробеги по участкам дорог, была минимальной. В данной постановке учитывается то обстоятельство, что из-за ко нечных возможностей дорожной сети возникают повторные посещения населенных пунктов и возвраты к перекресткам (развилкам) дорог. Одна ко не существует метода, который сразу мог бы привести к оптимально му маршруту при такой постановке: любой метод, включая алгоритмы динамического программирования, дает тупиковые псевдооптимальные решения, из которых методом перебора нужно отыскать наилучший. При чем нет гарантии, что найден весь набор решений, среди которых есть и оптимальное. Поэтому если есть компьютер большой мощности и есть время для ожидания результата (оно может быть довольно большим), то на ком пьютере реализуется алгоритм полного «тупого» перебора вариантов. Но «тупой» перебор не имеет универсального алгоритма. Поэтому необходимо написать довольно сложную расчетную программу, учиты вающую правила движения по данному региону. П р и м е р 3. Постановка задачи коммивояжера для выполнения вер толетных работ. В регионе имеется множество Л/ населенных пунктов. Необходимо составить такой алгоритм посещения этих пунктов, кото рый удовлетворял бы следующим требованиям: • каждый пункт необходимо посетить только один раз; • длина маршрута должна быть минимальной; • при определении отрезков маршрута учитывается, что поверх ность Земли - эллипсоид; • на маршруте могут работать один или два вертолета (если два - то они движутся навстречу один другому). 120 Известен «алгоритм двух вертолетов», который подходит для прак тического использования как для действий с привязкой к dopojtciiou сети, так и вертолетных работ, а по качеству решений может уступить толь ко «тупому» перебору, так как в этом случае нет гарантии того, что сре ди набора псевдооптимальных решений имеется расписание движения по оптимальному маршруту. Введем два определения и сформулируем одну теорему (без доказа тельства). Предположим, что нужно составить полетное расписание для вертолета, который вылетает из Санкт-Петербурга в Москву, причем он должен пролететь по кратчайшему маршруту над одиннадцатью промежу точными населенными пунктами (см. табл). Траектория маршрута показа на на рис. 4. Плавск Рис. 4 Определение L Под корректировкой понимается такое исправление маршрута следования, которое приводит к его сокращению без исклю чения каких-либо населенных пунктов из маршрутного расписания. Корректировка выполняется на основе графической траектории движе ния, изображенной на карте, и с использованием опыта руководителя движения. 121 На рис. 4 пунктирным контуром 1 выделен неоптимальный участок, где установлен следующий порядок движения (полета): Рига-^Вильнюс->Балтийск—>Минск. Корректировка, проведенная экипажем, заключается в изменении порядка посещения (пролета). Оптимальным будет (это заметно на ри сунке) маршрут: Рига-^Балтийск^Вильнюс-^Минск. Определение 2. Петлей называется траектория движения по маршру ту, имеющая замкнутый контур из ломаных линий, причем один угол такого контура находится вне перекрестка или населенного пункта. На рис. 4 пунктирным контуром 2 выделен участок, имеющий ха рактерную петлю. Точка А (угол Пинск-А-Хойники на пересечении тра екторий Минск—>Хойники и Пинск—>Новозыбков) действительно нахо дится за пределами населенных пунктов, через которые проходит маршрут. Теорема (без доказательства). Независимо от метода, с по мощью которого определяется минимальный маршрут коммивоя- э/сера, необходимым условием оптимизации пути является отсут ствие петель в траектории. Исходя из этой теоремы, участок маршрута внутри контура 2 на рис. 4 неоптимален. На нем установлен порядок: Минск—>Хойники^Киев-^Пинск->Новозыбков. После корректировки порядок изменится, а длина траектории умень шится: Минск—>Пинск->Киев-^Хойники-^Новозыбков. В результате двух выполненных корректировок из исходного (псев дооптимального) полетного расписания получено расписание полета по оптимальному маршруту (см. таблицу).
Ви переглядаєте статтю (реферат): «Практическое применение ГИС: решение задачи коммивояжера» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
