В практической деятельности разработчика 1С периодически возникают сложные оптимизационные задачи. Это может быть расчет оптимального маршрута доставки товаров, минимизация пробега автотранспорта или даже упорядочивание очереди производственных заданий для сокращения времени переналадки оборудования (например, при переходе с одного цвета краски на другой на конвейере). С математической точки зрения все эти задачи сводятся к классической задаче коммивояжера (Travelling Salesperson Problem, TSP).
Суть задачи проста: необходимо найти самый выгодный (кратчайший, быстрейший или наиболее дешевый) замкнутый маршрут, проходящий через все заданные пункты по одному разу с возвратом в исходную точку. Одним из наиболее точных математических методов решения этой задачи является алгоритм Литтла, который представляет собой специализированный вариант метода ветвей и границ. В этой статье мы подробно разберем, как реализовать этот алгоритм на платформе 1С, с какими трудностями производительности можно столкнуться и какие альтернативные подходы существуют.
Прежде чем переходить к коду, давайте кратко вспомним математическую суть алгоритма. Алгоритм Литтла работает с матрицей расстояний (или стоимостей) между точками. Главная его задача — последовательно разбивать множество всех возможных маршрутов на подмножества (ветви) и оценивать снизу стоимость маршрутов в этих подмножествах (границы), чтобы отсекать заведомо невыгодные пути.
Процедура состоит из следующих повторяющихся шагов:
Для реализации алгоритма нам понадобится структура данных для хранения матрицы расстояний. Использовать стандартный объект ТаблицаЗначений для частых математических вычислений в циклах не рекомендуется из-за накладных расходов платформы. Гораздо быстрее будет работать двумерный массив — массив массивов.
Рассмотрим пример инициализации матрицы расстояний на встроенном языке 1С:
// Инициализируем двумерный массив размерности N x N
Функция СоздатьМатрицуРасстояний(КоличествоТочек)
Матрица = Новый Массив;
Для ИндексСтроки = 0 По КоличествоТочек - 1 Цикл
СтрокаМатрицы = Новый Массив;
Для ИндексСтолбца = 0 По КоличествоТочек - 1 Цикл
// Для диагональных элементов (переход из точки в саму себя)
// устанавливаем условную бесконечность
Если ИндексСтроки = ИндексСтолбца Тогда
СтрокаМатрицы.Добавить(Неопределено); // Неопределено будет играть роль бесконечности
Иначе
СтрокаМатрицы.Добавить(0);
EndЕсли;
КонецЦикла;
Матрица.Добавить(СтрокаМатрицы);
КонецЦикла;
Возврат Матрица;
КонецФункции
При реализации вычислений нам часто придется искать минимальные элементы в строках и столбцах, игнорируя неопределенные значения (бесконечность). Разберем, как сделать процедуру редукции строк:
Процедура РедукцияСтрок(Матрица, НижняяГраница)
КоличествоСтрок = Матрица.Количество();
КоличествоСтолбцов = Матрица[0].Количество();
Для ИндексСтроки = 0 По КоличествоСтрок - 1 Цикл
Минимум = Неопределено;
// Поиск минимума в строке
Для ИндексСтолбца = 0 По КоличествоСтолбцов - 1 Цикл
ТекущееЗначение = Матрица[ИндексСтроки][ИндексСтолбца];
Если ТекущееЗначение = Неопределено Тогда
Продолжить;
КонецЕсли;
Если Минимум = Неопределено Или ТекущееЗначение < Минимум Тогда
Минимум = ТекущееЗначение;
КонецЕсли;
КонецЦикла;
// Если минимум найден и он больше нуля, вычитаем его
Если Минимум <> Неопределено И Минимум > 0 Тогда
Для ИндексСтолбца = 0 По КоличествоСтолбцов - 1 Цикл
Если Матрица[ИндексСтроки][ИндексСтолбца] <> Неопределено Тогда
Матрица[ИндексСтроки][ИндексСтолбца] = Матрица[ИндексСтроки][ИндексСтолбца] - Минимум;
КонецЕсли;
КонецЦикла;
НижняяГраница = НижняяГраница + Минимум;
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Встроенный язык «1С:Предприятия» является интерпретируемым и оптимизирован прежде всего для работы со структурами баз данных, бизнес-логикой и интерфейсом, но не для тяжелых математических расчетов. При работе с алгоритмом Литтла на чистом 1С вы неизбежно столкнетесь со следующими ограничениями:
Для преодоления этих ограничений в реальных проектах разработчики используют несколько обходных путей:
.dll. В 1С загружается эта компонента, ей передается матрица расстояний, а обратно мгновенно возвращается готовый массив индексов оптимального пути.ПолеHTMLДокумента. Внутрь него загружается легковесный JS-код, выполняющий расчеты. Движок рендеринга (например, WebKit или Chromium, встроенный в платформу) выполняет подобные циклы на JS значительно быстрее, чем интерпретатор встроенного языка 1С.Если вам требуется рассчитывать маршруты для реальной логистики (где количество точек доставки часто превышает 50–100 адресов), то точные методы вроде алгоритма Литтла неприменимы из-за временных ограничений. В таких случаях программисты 1С используют эвристические методы, которые находят решение, близкое к оптимальному (с погрешностью в 1–3%), но делают это практически мгновенно.
Проанализируем основные альтернативные подходы:
В тиражных решениях уровня КОРП (таких как «1С:TMS Логистика. Управление перевозками» или «Транспортная логистика и управление автотранспортом» от Рарус) задача коммивояжера перерастает в гораздо более масштабную задачу — VRP (Vehicle Routing Problem, задача маршрутизации транспорта). В ней нужно не просто объехать точки по очереди, но и распределить их по разным машинам с учетом их грузоподъемности, временных окон доставки у клиентов, графиков работы водителей и текущей дорожной ситуации.
Для решения промышленных задач в 1С применяются гибридные схемы:
МаршрутныйЛист.Таким образом, если перед вами стоит задача оптимизации простых процессов (например, упорядочивание 10-15 операций на производстве), смело используйте алгоритм Литтла, реализованный на чистом коде 1С, взяв за основу готовую внешнюю обработку (например, публикацию на Инфостарт под номером 816169). Если же масштаб задачи шире, а точек больше 20, рекомендуем сразу переходить к эвристическим методам или интегрировать базу с картографическими облачными сервисами по API.