Практическое применение алгоритма решения задачи коммивояжера

Рассматривается возможность снижения логистических затрат на транспортировку посредством решения задачи коммивояжера. Предлагается алгоритм решения задачи с использованием вычислительной мощности надстройки «Решатель» OpenOffice Calc. На основании предложенного алгоритма прорешивается практическая ситуация и составляется оптимальный маршрут для ООО «Молоко Зауралья».

Ключевые слова: логистика, логистический подход, задача коммивояжера, задача странствующего торговца, NP-сложная задача, оптимальный маршрут, оптимизация перевозок, минимизация транспортных расходов, OpenOffice Calc, надстройка «Решатель».

Первоочередной задачей любого предприятия является поиск резервов снижения затрат на осуществляемую деятельность и как следствие повышение собственной конкурентоспособности и рентабельности. В современных условиях поиск таких резервов строится на основе логистического подхода, что связано с расширением содержания логистики, превращающейся из вспомогательного элемента, обеспечивающего реализацию хозяйственных процессов, в важный инструмент организации и ведения хозяйственной деятельности [1]. При этом одним из приоритетных направлений совершенствования с точки зрения логистического подхода является оптимизация перевозок. Это связано в первую очередь со структурой логистических затрат, значительную долю в которых (20−40% и более) составляют именно расходы на транспортную составляющую [2].

Существуют различные теоретические алгоритмы оптимизации таких затрат, но они довольно трудоемки и долговременны, а современный уровень развития техники и технологий открывает новые возможности решения различного рода задач. Поэтому мы предлагаем решить задачу странствующего торговца, или коммивояжера (ЗК) посредством использования программы OpenOffice Calc. Задача коммивояжера заключается в нахождении оптимального маршрута, который проходит через все указанные пункты (города) хотя бы по одному разу с последующим возвращением в исходный пункт (город). В условиях задачи задаются критерий оптимальности маршрута (кратчайший, дешевый и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. [3] Задачу странствующего торговца начали изучать еще в XVIII веке математик из Ирландии сэр Уильям Р. Гамильтон и британский математик Томас П. Киркман. Считается, что общая формулировка задачи коммивояжера впервые была изучена Карлом Менгером в Вене и Гарварде. Позже проблема исследовалась Хасслером, Уитни и Мерриллом в Принстоне [4]. За многие годы исследований было предложено множество вариантов решения ЗК, среди которых выделяют: алгоритм полного перебора, метод ветвей и границ, метод включения дальнего, BV-метод, генетический алгоритм, «Система муравьев» и некоторые другие [5]. Современный уровень развития технологий предлагает более широкие возможности для решения ЗК и определения наилучшего маршрута. Тем не менее, классическая задача коммивояжера относится к числу NP-сложных задач и требует для решения значительных вычислительных ресурсов [6]. Требуемое для решения задачи время пропорционально (n-1)! (где n — количество пунктов), в связи с чем можно сделать вывод о нецелесообразности попытки решения задачи странствующего торговца с числом городов более 50, т.к. для нахождения оптимального маршрута потребуется вычислительная мощность компьютеров всего мира [7]. Однако при более «скромном» количестве пунктов, в которых необходимо побывать, решение ЗК посредством компьютерных вычислительных мощностей представляется наиболее эффективным, в частности в данной статье предлагается использовать надстройку OpenOffice Calc «Решатель» для целей минимизации затрат предприятия ООО «Молоко Зауралья» на доставку продукции.

Практическая ситуация: ООО «Молоко Зауралья» осуществляет поставку собственной продукции, общее количество пунктов 19, необходимо решить задачу коммивояжера для ответа на вопрос является ли принятый на предприятии маршрут оптимальным.

Т.к. количество пунктов доставки не слишком велико для решения задачи воспользуемся возможностями надстройки «Решатель» программы OpenOffice Calc, который после задания ему условий задачи осуществит полный перебор всех возможных вариантов решения с целью планирования наилучшего маршрута. Алгоритм решения задачи коммивояжера посредством использования программного продукта OpenOffice Calc представлен на рис. 1 (на основании источника [8]).

Рис. 1. — Алгоритм решения задачи коммивояжера с использованием надстройки «Решатель» OpenOffice Calc

ООО «Молоко Зауралья» (обозначим как пункт № 1) осуществляет поставку продукции для следующих учреждений: ЗАО «Одиссей» (№ 2), школа № 7 (№ 3), дом ребенка (№ 4), продовольственный магазин «Трио» (№ 5), ООО «Вира» (№ 6), детские сады 116 (№ 7), 122 (№ 8), 124 (№ 9), 126 (№ 10), 127 (№ 11), 129 (№ 12), 130 (№ 13), 131 (№ 14), 133 (№ 15), 134 (№ 16), 135 (№ 17), 138 (№ 18), 141 (№ 19). На основании данных сайта 2Гис (Курган) [9] была составлена матрица расстояний Cij (в км) между перечисленными выше пунктами (табл. 1 и табл. 2).

Таблица 1 — Матрица расстояний, в км (пункты 1−9).

Таблица 2 — Матрица расстояний, в км (пункты 1−19).

На предприятии принят следующий маршрут движения между пунктами: 1) ООО «Молоко Зауралья»; 2) детский сад 127; 3) детский сад 131; 4) детский сад 138; 5) детский сад 141; 6) детский сад 133; 7) продовольственный магазин «Трио»; 8) детский сад 135; 9) детский сад 134; 10) ООО «Вира»; 11) детский сад 130; 12) ЗАО «Одиссей»; 13) детский сад 116; 14) детский сад 129; 15) детский сад 126; 16) дом ребенка; 17) детский сад 124; 18) детский сад 122; 19) школа № 7; 20) ООО «Молоко Зауралья». Протяженность принятого маршрута составляет 28,28 км.

Для решения задачи странствующего торговца сформируем все необходимые данные на листе OpenOffice Calc. На основании табл. 1 и 2 составим матрицу расстояний Cij (B3:T21, рис. 2), которая является симметричной. При этом расстояния между конкретным пунктом и им самим (например между ООО «Молоко Зауралья» и ООО «Молоко Зауралья») равняется 0. Но, в случае, если в матрицу будут добавлены нулевые значения программа сочтет их наиболее рациональными маршрутами и решение окажется неверным. Чтобы предотвратить такой расклад необходимо задать программе ограничение, при котором такие расстояния не будут учитываться. Для этого проставим вместо нулевых значений числовые значения значительно превышающие самое большое из расстояний задачи. В нашей практической ситуации самое большое числовое значение, характеризующее расстояние между пунктами, не превышает 10 км. Поэтому в качестве ограничительного числа предлагается взять 999 км. Под матрицей оставим место для дополнительных переменных U (C22:T22, рис. 2), количество которых на 1 меньше общего числа пунктов, т. е. применительно к данной задаче — 18. Дополнительные переменные нужны для определения порядка, в котором будет осуществляться маршрут, а значение на единицу меньше общего количества пунктов связано с тем, что предприятие заранее знает откуда будет начинаться маршрут (ООО «Молоко Зауралья») и соответственно, где он будет заканчиваться.

Рис. 2. — Матрица расстояний и дополнительные переменные

Добавим на лист матрицу переменных, размер которых повторит матрицу расстояний — 19 на 19 пунктов (B26:T44, рис. 3). Под матрицей добавим строку «Входят» (B45:T45, рис. 3) и справа дополнительный столбец «Выходят» (U26:U44, рис. 3), с использованием которых будет прописано ограничение того, что коммивояжер въезжает и выезжает из каждого пункта только 1 раз. Для соблюдения подобного ограничения пропишем формулу, которая будет суммировать значения по строкам (для столбца «Выходят») и по столбцам (для строки «Входят»), сумма должна будет равняться единице для соблюдения ограничения 4.1 алгоритма. Скопируем данные формулы для всех 19 пунктов.

После построения матриц расстояний и переменных пропишем целевую функцию (ячейка D47, рис. 3). Цель задачи сводится к минимизации расстояний, для нахождения протяженности маршрута необходимо перемножить представленные выше матрицы, для этих целей в OpenOffice Calc предусмотрена функция SUMPRODUCT.

Рис. 3. — Матрица переменных и целевая функция

Для соблюдения ограничения пункта 4.2.2 алгоритма необходимо составить дополнительную матрицу, в которую прописываются ограничения замкнутости маршрута. Т.к. количество переменных U = 18, то размер матрицы также будет 18 на 18 (C51:T68, рис. 4). Формула из пункта 4.2.2 также представлена на рис. 4.

Рис. 4. — Замкнутость маршрута

После того как данные задачи сформированы на листе OpenOffice Calc воспользуемся надстройкой «Решатель». Для этого в меню выберем Сервис — Решатель. Заполненное окно «Решателя» представлено на рис. 5.

Рис. 5. — Надстройка «Решатель», заполненная данными

В целевую ячейку подставляется адрес ячейки, в которой прописана целевая функция SUMPRODUCT (D47). Результат стремится к минимуму, т.к. нашей целью является наиболее короткий маршрут. В строке «Изменяя ячейки» указываются два набора данных — матрица переменных Xij (ячейки В26: Т44) и дополнительные переменные U (ячейки С22: Т22). В задаче 4 ограничительных условия: 1) суммы, рассчитываемые по строке «Входит» должны быть равны единице (первое ограничение в «Решателе»); 2) суммы, рассчитываемые по столбцу «выходит» должны равняться единице (второе ограничение); 3) матрица переменных Xij представляет собой булевы числа (третье ограничение); 4) полученные по формуле, прописанной в матрице «Замкнутость маршрута», значения не должны превышать общее количество пунктов задачи, уменьшенное на единицу, т. е. 18 (четвертое ограничение). Существует еще одно дополнительное ограничение, проставить которое возможно, выбрав Параметры «Решателя». Нужно поставить галочку у пункта «Принять переменные как неотрицательные» для того, чтобы дополнительные переменные U могли принимать значения большие или равные нулю. По нажатию на кнопку «решить» программа начнет подсчет всех возможных вариантов решения задачи и выведет для пользователя оптимальный (рис. 6).

Рис. 6. — Результаты решения задачи коммивояжера для ООО «Молоко Зауралья»

Согласно полученному решению оптимальный, т. е. наиболее короткий маршрут составит всего 23,59 км. В сравнении с принятым на сегодняшний день маршрутом, на предприятии при вводе нового экономия времени составит 16,6%, что доказывает целесообразность использования надстройки «Решатель» для целей формирования наилучшего пути движения транспортных средств. Для того, чтобы определить порядок посещения пунктов доставки необходимо посмотреть на переменные U, их значения (ячейки С22: Т22, рис. 6) приняли значения от 0 до 17, тем самым показывая конкретный маршрут движения, который представит собой: 1) ООО «Молоко Зауралья»; 2) детский сад 131; 3) детский сад 127; 4) детский сад 138; 5) детский сад 141; 6) продовольственный магазин «Трио»; 7) детский сад 135; 8) детский сад 134; 9) школа № 7; 10) ЗАО «Одиссей»; 11) детский сад 130; 12) ООО «Вира»; 13) детский сад 116; 14) детский сад 129; 15) детский сад 122; 16) детский сад 124; 17) детский сад 126; 18) дом ребенка; 19) детский сад 133; 20) исходный пункт, с которого начиналось движение ООО «Молоко Зауралья».

В процессе решения стоял выбор между программными продуктами Microsoft Excel и OpenOffice Calc. Программы обладают сходными функциями и возможностями и довольно распространены. Однако в процессе решения было выяснено, что надстройка «Поиск решения» (Excel) устанавливает жесткие рамки на количество ограничений решаемой задачи. В частности в MS Excel удобно решать задачи с небольшим количеством пунктов (до 10), общее количество формульных ограничений в которых не превысит 100. В «Решателе» подобных ограничений нет, но с добавлением каждого дополнительного пункта в задачу программе требуется все большее количество времени на нахождение оптимального маршрута [8]. Кроме того, OpenOffice является бесплатным программным продуктом, что обеспечивает дополнительную экономию средств при его использовании.

Важность решения поставленной задачи определяется тем, что согласно статистическим данным, около 98% от общего времени движения грузов занимает именно их прохождение по логистическим каналам, включая транспортировку [10]. Этим и обусловлена необходимость поиска резервов снижения затрат на перевозки, т. е. определения наилучшего маршрута, что приведет к экономии времени на перевозки, горючего, износа транспортных средств и будет особенно ценно для предприятий, работающих по системе JIT (точно-в-срок).

• 1. Афанасьева И. И. Организационно-экономические проблемы и перспективы формирования логистической системы распределения зерна в России // Инженерный вестник Дона, 2014, № 2 URL: ivdon.ru/ru/magazine/archive/n2y2014/2325
• 2. Дыбская В. В., Зайцев Е. И., Сергеев В. И. и др. Логистика — М.: Эксмо, 2013. — 944 с. — (Полный курс МВА).
• 3. Кочегурова Е. А., Мартынова Ю. А. Оптимизация составления маршрутов общественного транспорта при создании автоматизированной системы поддержки принятия решений // Известия ТПУ. 2013. № 5. С. 79−84.
• 4. Matai R., Singh S.P., Mittal M.L. Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches // URL: cdn.intechopen.com/pdfs-wm/12 736.pdf
• 5. Борознов В. О. Исследование решения задачи коммивояжера // Вестник АГТУ. Серия: Управление, вычислительная техника и информатика. 2009. № 2. С. 147−151.
• 6. Ишков С. А., Ишкова Е. С. Матричный подход в решении задачи маршрутизации с несколькими транспортными средствами // Известия Самарского научного центра РАН. 2011. № 4−1. С. 189−194.
• 7. Applegate D.L., Bixby R.E., Chvбtal V. & Cook W.J. The Traveling Salesman Problem // URL: press.princeton.edu/chapters/s8451.pdf
• 8. Студентова Е. А. Алгоритм решения задачи коммивояжера с использованием Microsoft Excel и Open Office Calc // Современные проблемы науки и образования. 2014. № 6. (приложение «Технические науки»). — C. 40.
• 9. Карта Кургана: улицы, дома и организации города — 2ГИС // URL: 2gis.ru/kurgan/zoom/11
• 10. Макаров Е. И., Ярославцева Ю. И. Социально-экономическая эффективность формирования Воронежской региональной транспортно-логистической системы // Инженерный вестник Дона, 2011, № 4 URL: ivdon.ru/ru/magazine/archive/n4y2011/557

References.

• 1. Afanas’eva I.I. Inћenernyj vestnik Dona (Rus), 2014, № 2 URL: ivdon.ru/ru/magazine/archive/n2y2014/2325
• 2. Dybskaya V.V., Zaytsev E.I., Sergeev V.I. i dr. Logistika [Logistics] M.: Eksmo, 2013. 944 p. (Polnyy kurs MVA).
• 3. Kochegurova E.A., Martynova Yu.A. Izvestiya TPU. 2013. № 5. P. 79−84.
• 4. Matai R., Singh S.P., Mittal M.L. Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches URL: cdn.intechopen.com/pdfs-wm/12 736.pdf
• 5. Boroznov V.O. Vestnik AGTU. Seriya: Upravlenie, vychislitel’naya tekhnika i informatika. 2009. № 2. P. 147−151.
• 6. Ishkov S.A., Ishkova E.S. Izvestiya Samarskogo nauchnogo tsentra RAN. 2011. № 4−1. P. 189−194.
• 7. Applegate D.L., Bixby R.E., Chvбtal V. & Cook W.J. The Traveling Salesman Problem URL: press.princeton.edu/chapters/s8451.pdf
• 8. Studentova E.A. Sovremennye problemy nauki i obrazovaniya. 2014. № 6. (prilozhenie «Tekhnicheskie nauki»). p. 40.
• 9. Karta Kurgana: ulitsy, doma i organizatsii goroda — 2GIS [Kurgan map: streets, houses and town organisations — 2GIS] URL: 2gis.ru/kurgan/zoom/11
• 10. Makarov E.I., Yaroslavtseva Y.I. Inћenernyj vestnik Dona (Rus), 2011, № 4 URL: ivdon.ru/ru/magazine/archive/n4y2011/557