Пример бизнес процесса выполняемого специалистом по составлению маршрутов

Пусть имеется 5 городов, расположенных как показано на рис. 2.3.

Рис. 2.3 Пример расположения городов

Построим выпуклый многоугольник с минимальной площадью, включающий все точки. Для этого сначала выберем начальную точку. В качестве нее возьмем крайнюю левую точку и будем соединять точки последовательно, образуя многоугольник. Каждая следующая точка выбирается по принципу:

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

Рис. 2.4 Углы между условной осью ординат, расположенной слева, и условными линиями

Из рисунка видно, что минимальным является угол между осью ординат и условной линией, соединяющей точки 1 и 2. Следовательно, отрезок 1−2 включается в периметр выпуклого многоугольника.

Рис. 2.5 Условная линия, угол между которой и линией, проходящей через предыдущий отрезок периметра многоугольника минимальный

Минимальный будет угол между линией, проходящей через точки 1−2, и условной линии, проходящей через точки 2−3. Следовательно, отрезок 2−3 включается в периметр многоугольника. Аналогичным образом достроим выпуклый многоугольник (рисунок 2.6).

Рис. 2.6 Выпуклый многоугольник

В периметр многоугольника вошли все точки, кроме точки 4. Ее соединим следующим образом: найдем ребро, ближайшее к этой точке (рисунок 2.7), и соединим точку 4 с вершинами выбранного ребра (рисунок 2.8).

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

Рис. 2.7 Нахождение ближайшего ребра к точке 4

Как видно из рисунка 2.7 в данном случае минимальную длину имеет перпендикуляр до ребра 3−4. Следовательно, соединим рассматриваемую точку с вершинами этого ребра (рисунок 2.8).

Рис. 2.8 Соединение точки 4 с вершинами ребра 3−5

Далее заменим ребро 3−5 на два новых ребра: 3−4 и 4−5 (рисунок 2.9).

Рис. 2.9 Замена ребер

Так как все точки включены в периметр многоугольника, то примем его за оптимальный маршрут. Длина пути при этом равна периметру многоугольника, то есть сумме всех его отрезков.

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

Трудоемкость работы можно измерить количеством выполняемых операций, из Сценария видно, что для нахождения пути инженеру необходимо выполнить 8 операций, мы же попытаемся уменьшить их количество.