Данные и методология

№.

Контрагент.

Начало.

Конец.

Прибытие.

Отбытие.

Разгрузка.

Простой.

Опоздание.

ООО «Фабрика еды».

;

;

11:00.

11:00.

;

;

;

Ресторан Нефертити.

11:00.

19:00.

11:09.

11:16.

00:07.

;

;

Кафе «Корица» .

11:00.

19:00.

11:19.

11:27.

00:08.

;

;

Ресторан «Горький» .

11:30.

12:00.

11:32.

11:36.

00:04.

;

;

ИП Ахметова Н.П.

11:00.

12:00.

11:56.

12:04.

00:08.

;

;

Ресторан «Кама-Фиш».

12:00.

12:30.

12:23.

12:29.

00:06.

;

;

ООО «ТД» .

12:00.

13:00.

12:46.

12:54.

00:08.

;

;

ООО «Веселый пекарь» .

11:00.

14:00.

13:09.

13:15.

00:06.

;

;

Ресторан «Пармезан» .

12:30.

15:30.

13:23.

13:31.

00:08.

;

;

ООО «Море рыбы» .

12:00.

16:00.

13:38.

13:44.

00:06.

;

;

Продуктовый магазин.

12:00.

16:00.

13:54.

14:03.

00:09.

;

;

Ресторан «Тсуру» .

11:00.

19:00.

14:06.

14:11.

00:05.

;

;

Ресторан «Casa Mia».

13:00.

17:00.

14:13.

14:21.

00:08.

;

;

Кафе «Сковородка» .

14:00.

16:00.

14:24.

14:28.

00:04.

;

;

Бар «Лаундж» .

11:00.

19:00.

14:30.

14:35.

00:05.

;

;

Ресторан «Casa Mia» .

11:00.

20:00.

14:40.

14:43.

00:03.

;

;

Кафе «Кредо» .

14:00.

18:00.

14:49.

14:56.

00:07.

;

;

ООО «Гарант плюс» .

15:00.

16:30.

15:00.

15:03.

00:03.

;

;

ИП Кусакин А.В.

15:00.

16:30.

16:46.

16:53.

00:07.

;

00:16.

ТЦ «Евразия» .

15:30.

19:30.

18:21.

18:27.

00:06.

;

;

Продуктовый магазин.

16:00.

19:00.

18:36.

18:45.

00:09.

;

;

Столовая «Забава» .

15:00.

19:00.

18:55.

19:00.

00:05.

;

;

Пиццерия «Pizzaman» .

17:00.

19:30.

19:03.

19:06.

00:03.

;

;

ООО «Заполье» .

17:00.

19:30.

19:13.

19:18.

00:05.

;

;

ООО «Микс — Семья» .

15:00.

22:00.

19:31.

19:40.

00:09.

;

;

Продуктовый магазин.

18:00.

21:00.

19:46.

19:55.

00:09.

;

;

ООО «Компания ЦВР» .

11:00.

21:00.

20:05.

20:08.

00:03.

;

;

ООО «Фабрика еды».

;

;

20:15.

20:15.

;

;

00:15.

№.

Контрагент.

Начало.

Конец.

Прибытие.

Отбытие.

Разгрузка.

Простой.

Опоздание.

ООО «Фабрика еды».

;

;

11:00.

11:00.

;

;

;

Столовая «Тарелка № 1» .

11:00.

11:30.

11:12.

11:19.

00:07.

;

;

Столовая «Тарелка № 2» .

11:00.

12:00.

11:25.

11:28.

00:03.

;

;

Столовая «Тарелочка» .

11:00.

12:00.

11:37.

11:45.

00:08.

;

;

Ресторан «Хуторок» .

12:30.

13:00.

12:20.

12:33.

00:03.

00:10.

;

Кафе «Ритм».

11:00.

19:00.

13:03.

13:09.

00:06.

;

;

ОАО «ЭР-Телеком».

12:30.

13:30.

13:11.

13:14.

00:03.

;

;

Кафе «Паста Гранде» .

12:00.

13:30.

13:19.

13:28.

00:09.

;

;

ЗАО «Пермторгтехника» .

13:00.

14:00.

13:34.

13:39.

00:05.

;

;

Кафе «Правила» .

11:00.

14:00.

13:48.

13:51.

00:03.

;

;

ООО «Паритет» .

14:00.

15:00.

13:55.

14:05.

00:05.

00:05.

;

Ресторан «Охотничий» .

13:30.

15:30.

14:08.

14:15.

00:07.

;

;

Ресторан «Сакартвело» .

13:30.

17:30.

14:20.

14:28.

00:08.

;

;

Ресторан «Халва» .

14:00.

20:00.

14:35.

14:43.

(20).

где: — вероятность перехода муравья под номером k из вершины i в вершину j;

и параметры модели (если, алгоритм вырождается в «жадный», если, муравьи реагируют только на количество феромона).

Знаменатель формулы позволяет вероятности находиться в пределах единицы (Индекс — множество еще не посещенных муравьями вершин, смежных с i. Таким образом, муравьи предпочитают выбирать каждую последующую вершину, исходя только из меры актуальности и количества феромона. После расчета вероятности перехода из одной вершины в другую, в алгоритме используется генератор случайных чисел от 0 до 100. Если найденная вероятность больше, чем случайное число, муравей передвигается в данную вершину, если нет, то рассматривается следующая вершина из еще не использованных в маршруте. Когда муравей проходит каждую последующую точку, количество феромона уменьшается. После прохождения всего маршрута одним из муравьев используется правило обновления феромона:

(21).

где: — случайное число, отвечающее за интенсивность испарения феромона (0<<1);

t — момент времени.

Алгоритм муравьиной колонии находит решение либо через фиксированное количество итераций, либо через определенное количество времени. Важным моментом в решении задачи муравьиным алгоритмом является связь расстояния и времени, которая будет моделироваться через параметр — актуальность посещения каждой конкретной вершины (разница между правой границей временного окна i-го покупателя и текущим моментом времени) (Лебедев, 2012):

(22).

где:, является шириной временного интервала до начала обслуживания покупателя j;

— текущий момент прохождения маршрута, и — левая и правая граница временного окна у покупателя под номером j;

— время проезда от контрагента i к j;

— коэффициент штрафующий за не включение j-ой вершины в маршрут (с экономической точки зрения показывает приоритет обслуживания j-го покупателя).

Заметим, что муравьиным алгоритмом невозможно решить одновременно или последовательно целую задачу маршрутизации транспорта в современных программных пакетах: необходимо вершины графа разбить каким-то образом между транспортными средствами. Так, в работе будет использован простейший алгоритм разбивки (кластеризации) данных, который реализован в программном пакете «Муравьиная логистика». С точки зрения экономической теории существует огромное количество способов разбить один массив данных более чем на две части. В исследовании будет представлена кластеризация вершин графа (точек на карте г. Пермь) при помощи алгоритма минимального остовного дерева (Schneider, et al., 2010). Принцип метода основан на «жадном» алгоритме: между всеми покупателями (за исключением фирмы-поставщика) будет найдены наименьшие расстояния. Таким образом, удастся получить путь с началом в самое удаленной точке на карте и концом в противоположной части г. Пермь. Затем, установив ограничение на «центры масс» кластеров (в исследовании необходимо разбить ЗМТ на две части) не менее чем 25 точек, удастся распределить массив покупателей между двумя водителями, назначив каждому случайный кластер. Отметим, что кластеры будут сформированы на основе расстояния между покупателями, не учитывая временной критерий. С практической точки зрения, любое торговое предприятие может самостоятельно выбрать необходимый критерий кластеризации. Только после распределения покупателей между двумя водителями каким-либо математическим методом, можно применить алгоритм муравьиной колонии. В зависимости от оптимальности полученного решения, имеет смысл решить задачу без разбивки ее на кластеры, использовав алгоритм поиска с запретами, который может учесть вышеизложенный факт. Проанализируем данный метод решения ЗМТ в деталях.

Используемый в исследовании алгоритм одновременного решения задачи (без деления на отдельные задачи коммивояжера для каждого водителя), является метаэвристическим и основан на алгоритме имитации отжига, а также механизмах функционирования краткосрочной памяти человека. На данный момент, эмпирически доказано, что поиск с запретами является наиболее эффективным методом решения описываемой задачи, а именно, он позволяет найти решение за наименьшее время (в сравнении с другими метаэвристиками) (Wiener, et al., 2009). Поиск с запретами начинает решать задачу с первоначального маршрута (, найденного, к примеру, «жадным» методом. На каждой итерации (t), алгоритм (путем случайной перестановки последовательности вершин графа) улучшает решение (), минимизируя целевую функцию. Итерации продолжаются до тех пор, пока не будет выполнен критерий остановки (конечное количество этапов алгоритма, либо заданное время). Метод поиска с запретами очень похож на алгоритм имитации отжига, следовательно необходимо описать последний для выявления расхождений.

В методе имитации отжига очередная последовательность вершин (точек на карте) также формируется случайным образом, путем незначительного изменения предыдущего маршрута. Один из самых распространенных в литературе вариантов изменения — перестановка двух случайно выбранных вершин графа. Если маршрут получился лучше всех предыдущих итераций, то он рассматривается как следующий для улучшения. Если же маршрут получается хуже, то один из вариантов — не использовать его. Придерживаясь описываемой логики, решение задачи может попасть в один из локальных экстремумов (минимумов), которых достаточно много в задаче маршрутизации транспорта. Именно исходя из данных предположений маршрут не отвергается (Лопатин, 2005). Вероятность его принятия рассчитывается по формуле:

(23).

где: — неотрицательная разность между тестируемым и ранее полученным решением;

T — постоянно убывающий параметр, снижение которого происходит, например, по закону полураспада (при коэффициенте «альфа» равном 0,5):. В случае ЗМТ, чем больше параметр T, тем выше вероятность, того, что алгоритм преодолеет локальный минимум. По мере уменьшения данного параметра, алгоритм достигает конечного решения. Метод имитации отжига эффективен для задач с количеством вершин более 15, поскольку он находит приблизительное решение всего с 2% отклонений от оптимального за несколько минут. Основным его недостатком является невозможность учета дополнительных ограничений в задаче, например, времени, пробок, грузоподъемности и др.

Главным отличием алгоритма поиска с запретами от метода имитации отжига является то, что последним нельзя решить ЗМТ из-за слишком большого количества локальных минимумов, в то время как алгоритм поиска с запретами обладает краткосрочной памятью и имеет свойство «выходить» из локальных оптимумов задачи с помощью «листа табу», в который заносятся маршруты, сформированные на предыдущих итерациях после достижения одного из локальных экстремумов (Чеблоков, Ченцов, 2005). Таким образом, у алгоритма появляется возможность «не возвращаться» в предыдущие локальные оптимумы, а итерационно двигаться к следующему, вне зависимости от того, лучше он или нет. Наличие краткосрочной памяти позволяет алгоритму поиска с запретами запоминать все найденные экстремумы и на последней итерации выбирать тот, в котором значение целевой функции задачи маршрутизации транспорта минимальное. Описываемый алгоритм позволяет решить ЗМТ с различными ограничениями быстро и эффективно, по сравнению с другими методами нахождения оптимального маршрута. Более того, на данный момент, поиск с запретами — один из немногих алгоритмов, который имеет программное обеспечение и привязан к геоинформационным системам (ГИС), что позволяет решить задачу еще эффективнее. Таким образом, после обработки данных и выявления наиболее приемлемых как с теоретической, так и практической/программной точки зрения алгоритмов решения ЗМТ, рассмотрим вышеизложенную методологию в разрезе результатов исследования.