Особенности усовершенствованного метода Кларка–Райта для решения задачи маршрутизации

УДК 338.2

В.М. Никоноров, В.К. Тютюкин

ОСОБ Е ННОСТИ УСО В Е Р Ш ЕНСТВОВАН Н О ГО М ЕТОДА КЛАР КА- РАЙТА ДЛЯ РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ

В предыдущей статье («Реализация усовершенствованного метода Кларка—Райта для решения задачи маршрутизации в случае автомобильных мелкопартионных перевозок») мы рассмотрели возможность улучшения метода Кларка—Райта и вкратце описали полученные этим методом маршруты [3].

Подробное описание усовершенствования метода Кларка—Райта также приведено в предыдущей статье.

Идея усовершенствования достаточно проста — предварительная оптимизация расстояний методами Флойда—Уоршелла и Дейкстры, вслед за тем решение задачи методом Кларка—Райта [1].

После того, как мы отыщем кратчайшие расстояния между любой парой получателей и узнаем сами пути, остается задействовать алгоритм Кларка—Райта, который сформирует оптимальные маршруты.

Цели исследования: оценить экономический эффект от применения усовершенствованного метода Кларка—Райта; оценить экономическую эффективность этого метода.

Актуальность исследования заключается в том, что усовершенствование метода решения задачи маршрутизации мелкопартионных перевозок позволяет разработать инструментарий для формирования наиболее рациональных маршрутов и повысить эффективность мелкопартионных перевозок.

Для реализации усовершенствованного алгоритма Кларка—Райта нами создана соответствующая программа. Решение программы реализовано — на С++, интерфейс на С#. При создании программы задействовано объектно- ориентированное программирование [2].

На главной форме расположено меню для управления выбираемыми алгоритмами, таблицами и окнами (см. рисунок).

В соответствии с меню выбирается вектор спроса и матрица расстояний. После того как вектор спроса и матрица расстояний импортированы в программу, выбирается алгоритм решения — «Классический Кларк—Райт» или «Усовершенствованный Кларк—Райт». Соответственно, подключается программа — решатель «Классический Кларк—Райт» или «Усовершенствованный Кларк—Райт».

После решения появляются следующие окна:

1) маршруты, с указанием длины, времени, числа лотков;

2) развернутые маршруты;

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

4) распределение маршрутов по машинам.

Произведем оценку эффективности усовершенствованного метода Кларка—Райта. Рассмотрим, какова экономическая эффективность от внедрения компьютерной программы.

Для этого сравним суммарную длину маршрутов получателей Петроградского района СПб ОАО Хлебный завод «Арнаут», полученных тремя методами: методом Кларка— Райта, усовершенствованным методом Кларка—Райта, методом ручной маршрутизации.

Сравним результаты классического и усовершенствованного методов Кларка—Райта.

Применение усовершенствованного метода Кларка—Райта в среднем позволяет сократить протяженность маршрутов получателей Петроградского района СПб на 5,9 %. Для того чтобы понять, много это или мало, оценим результат на примере ОАО Хлебный завод «Арнаут». Прежде сравним километраж, полученный посредством ручной обработки маршрутов, с километражом, получаемым по методу Кларка—Райта.

Научно-технические ведомости Санкт-Петербургского государственного политехнического университета Экономические науки 6' 2012

1-1

Рис. 1. Меню программы усовершенствованного метода Кларка—Райта

Таблица 1

Сравнение классического и усовершенствованного методов Кларка—Райта

Таблица 3

Сравнение усовершенствованного метода Кларка—Райта и ручной маршрутизации

Показатель Длина маршрутов, Время маршрутов, Число машин

км ч:мин:с

Метод Кларка— 108,351 39:20:00 5

Райта

Усовершенство - 101,996 38:55:00 5

ванный метод

Кларка—Райта

Экономия, км 6,355 00:25:00 0

Экономия, % 5,9 1,1 0,0

Показатель Длина маршрутов, км Время маршрутов, ч:мин:с Число машин

Ручная маршру- 116,465 42:15:00 6

тизация

Метод Кларка— 101,996 38:55:00 5

Райта

Экономия, км Экономия, % 14,469 12,4 03:20:00 7,9 1 16,7

Таблица 2

Сравнение метода Кларка—Райта и ручной маршрутизации

Применение метода Кларка—Райта уже дает 7 % экономии по сравнению с ручной маршрутизацией и сокращает количество транспортных единиц на 16,7 %. Сравним результаты ручной маршрутизации и усовершенствованного метода Кларка— Райта.

Применение усовершенствованного метода Кларка—Райта позволяет сократить протяженность маршрутов получателей ОАО Хлебный завод «Арнаут» Петроградского района СПб на 12,4 % и, соответственно, на 7,9 % время маршрутов. Экономия по времени позволяет вместо шести машин заказать

Показатель Длина маршрутов, км Время маршрутов, ч:мин:с Число машин

Ручная марш- 116,465 42:15:00 6

рутизация

Метод Кларка— 108,351 39:20:00 5

Райта

Экономия, км Экономия, % 8,114 7,0 02:55:00 6,9 1 16,7

Таблица 4

Результат сокращения транспортных затрат при применении усовершенствованного метода Кларка—Райта

Показатель Ручная маршрутизация Метод Кларка—Райта Усовершенствованный метод Кларка—Райта

Средняя цена 1 км, руб. 18,5 18,5 18,5

Километраж, км 3 135 135 2 915 675 2 743 650

Экономия, % 7 5,9

Транспортные расходы, тыс. руб. 58 000 53 940 50 758

Увеличение финансового результата, тыс. руб. — 4 060 7 242

Выручка, тыс. руб. 495 000 495 000 495 000

Прирост рентабельности продаж, % 0,0 0,82 1,46

пять. Можно сказать, что возникает синэрге-тический эффект.

Оценим экономический эффект от применения усовершенствованного метода Кларка—Райта.

Прежде всего, учтем экономический эффект от сокращения транспортных расходов. Для этого воспользуемся данными ОАО Хлебный завод «Арнаут» за 2011 г.

Применив данные ОАО Хлебный завод «Арнаут» за 2011 г., мы получим оценку экономического эффекта от сокращения транспортных затрат в размере 7 242 тыс. р. в год. Соответственно эффективность деятельности (рентабельность продаж) вырастет на 1,46 %.

Для достижения данного эффекта следует осуществить ряд следующих мероприятий:

1) провести микрорайонирование с учетом требований программы. Разбить получателей по административным районам города;

2) для каждого района составить матрицу расстояний;

3) составить векторы спроса по каждому району;

4) в случае добавления в район нового получателя (получателей) требуется увеличивать матрицу расстояний и вектор спроса;

5) следует обучить персонал работе с новой программой. Ожидается существенное сокращение трудозатрат. Это позволит высвободить часть персонала отдела логистики. По предварительной оценке это высвобождение

может оставить до 50 % от численности персонала отдела логистики.

По результатам проведенного исследования можно сделать следующие выводы.

1. Усовершенствованный метод Кларка— Райта позволяет оптимизировать логистические показатели мелкопартионных перевозок следующим образом.

Таблица 5

Оптимизация логистических показателей при применении усовершенствованного метода Кларка—Райта

Сравнение методов Экономия протяженности маршрутов, % Экономия времени маршрутов, %

Усовершенствованный метод Кларка—Райта по отношению к ручной маршрутизации 12,4 7,9

Усовершенствованный метод Кларка—Райта по отношению к методу Кларка—Райта 5,9 1,1

2. Применение усовершенствованного метода Кларка—Райта в условиях ОАО Хлебный завод «Арнаут» дает экономический эффект (предварительная оценка) в размере 7242 тыс. р. в год и позволяет повысить экономическую эффективность (рентабельность продаж) на 1,5%.

Научно-технические ведомости Санкт-Петербургского государственного политехнического университета ^ Экономические науки 6' 2012

СПИСОК ЛИТЕРАТУРЫ

1. Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. — 2-е изд. — М.: Изд. дом «Вильямс», 2012. — С. 1296.

2. Павловская, Т.А. С/С++. Программирование на языке высокого уровня [Текст] / Т.А. Пав-

ловская. — СПб.: Питер, 2012. — 461 с.

3. Clark, G. Sheduling of vehicles from a central depot to a number of delivery points [Text] / G. Clark, J. Wright // Operational Research Quarterly. — 1964. — Vol. 12, no. 4. — P. 568—581.

УДК 338.45.69

И.С. Петров

ПРИМЕНЕНИЕ ФАЗОВОГО АНАЛИЗА ПРИ ПРОГНОЗИРОВАНИИ ОБЪЕМОВ ЖИЛИЩНОГО СТРОИТЕЛЬСТВА

Использование фазового анализа динамики ключевых показателей в инвестиционно-строительной сфере позволяет выявлять устойчивые состояния в определенные промежутки времени [2, 3]. Эти данные могут быть использованы для прогнозирования значений этих показателей в будущем. Далее мы представим разработанную нами методику использования фазового анализа в прогнозировании.

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

Построим фазовую кривую коэффициента доступности жилья в Российской Федерации за период с 1998 по 2010 г. Исходными данными для построения фазовой кривой являются сведения о ежемесячных среднедушевых денежных доходах населения, средние цены на первичном и вторичном рынке жилья. Коэффициент доступности жилья согласно Постановлению Правительства РФ № 1050 от 17.12.2010 г. (ред. от 27.12.2011 г.) «О федеральной целевой программе "Жилище" на 2011—2015 годы» определяется как отношение средней рыночной стоимости стандартной квартиры общей площадью

54 м2 к среднему годовому совокупному денежному доходу семьи, состоящей из трех человек. Расчет средней рыночной стоимости стандартной квартиры общей площадью 54 м2 за период с 1997 по 2010 г. в Российской Федерации представлен в табл. 1.

Расчет коэффициента доступности жилья в Российской Федерации за период с 1997 по 2010 г. представлен в табл. 2.

Используя данные, полученные в табл. 2, составим таблицу данных, необходимых для построения фазовой кривой коэффициента доступности жилья в Российской Федерации за период с 1998 по 2010 г. (табл. 3).

Фазовая кривая, построенная по данным табл. 3, представлена на рис. 1.

На рисунке можно выделить один аттрактор, на котором система находилась с 2000 по 2010 г.: среднее значение коэффициента доступности жилья в этот период составило 4,81. В 2010 г. значение коэффициента составило 4,3 [1]. Согласно Постановлению Правительства РФ № 1050 от 17.12.2010 г. целевое значение на 2011 г. — 4,3. В целом по Российской Федерации программа «Жилище» по целевому показателю доступности выполняется. В связи с тем, что фазовая кривая имеет только один аттрактор, построение прогноза осуществим на основе анализа показателя уровня обеспеченности населения жильем.