Задача маршрутизации с разными стартами и финишами

В соседних статьях Задача маршрутизации транспорта и Задача маршрутизации с грузоподъёмностью рассмотрены кейсы, где все транспортные средства стартуют и финишируют в одной общей точке. Эта статья показывает естественное обобщение: у каждого ТС своя стартовая точка, а финиш у всех общий. Такая постановка встречается, когда машины ночуют в разных районах или у водителей индивидуальные места старта смены, а пункт сбора (гараж, центральный склад) один.

Помимо разных стартов, к модели добавляется ограничение на длину каждого маршрута (не более 2000 единиц) и коэффициент балансировки пробега между всеми маршрутами. Это выравнивает нагрузку между ТС и не даёт одному маршруту слишком сильно выбиваться по длине.

Условия задачи

Задан набор из 17 точек с фиксированной матрицей расстояний — те же данные, что в классических примерах TSP и VRP. Узел 0 — общий финиш: все четыре транспортных средства завершают маршрут в этой точке. Стартовые точки разные:

ТС1 стартует в узле 1;
ТС2 стартует в узле 2;
ТС3 стартует в узле 15;
ТС4 стартует в узле 16.

Каждый узел (включая стартовые) должен быть посещён ровно одним транспортным средством. Длина любого маршрута не может превышать 2000 единиц. Целевая функция состоит из двух частей: суммарная длина всех маршрутов плюс 100-кратный штраф за разброс длин маршрутов между ТС — решатель стремится одновременно укоротить общий пробег и выровнять длины маршрутов.

Решение задачи

1. Выбор модели

Применяется модель маршрутизации. Отдельной модели для VRP с разными стартами не требуется: построитель параметров позволяет задать индивидуальные стартовые и конечные узлы для каждого ТС через тот же метод ДобавитьТранспортноеСредство.

2. Создание модели

Модель собирается через построитель параметров. В отличие от предыдущих статей, где первая пара аргументов ДобавитьТранспортноеСредство была (0, 0) для всех ТС, здесь стартовые узлы разные, а конечный одинаковый.

// Создаём построитель параметров модели маршрутизации
Построитель = О2.Модели()
    .МодельМаршрутизации()
    .СоздатьПостроительПараметровМодели();

// Добавляем 17 узлов
КоличествоУзлов = 17;
Для К = 0 По КоличествоУзлов - 1 Цикл
    Построитель.ДобавитьУзел("Узел" + К);
КонецЦикла;

// Добавляем 4 транспортных средства с разными стартами и общим финишем
Построитель.ДобавитьТранспортноеСредство(1, 0, "ТС1");
Построитель.ДобавитьТранспортноеСредство(2, 0, "ТС2");
Построитель.ДобавитьТранспортноеСредство(15, 0, "ТС3");
Построитель.ДобавитьТранспортноеСредство(16, 0, "ТС4");

// Фиксируем состав модели
Модель = Построитель.СоздатьМодель();

3. Ввод данных

Матрица расстояний 17 × 17 задаётся явно — она симметричная, с нулями по диагонали. Для компактности каждая строка собирается из текстового представления через утилиту МассивЧиселИзСтроки, а затем копируется в двумерный массив.

// Матрица расстояний 17 × 17 (классический пример TSP/VRP)
Расстояния = О2.Утилиты().Массив2DИзвестногоРазмера(КоличествоУзлов, КоличествоУзлов);

СтрокиМатрицы = Новый Массив();
СтрокиМатрицы.Добавить("0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662");
СтрокиМатрицы.Добавить("548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210");
СтрокиМатрицы.Добавить("776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754");
СтрокиМатрицы.Добавить("696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358");
СтрокиМатрицы.Добавить("582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244");
СтрокиМатрицы.Добавить("274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708");
СтрокиМатрицы.Добавить("502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480");
СтрокиМатрицы.Добавить("194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856");
СтрокиМатрицы.Добавить("308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514");
СтрокиМатрицы.Добавить("194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468");
СтрокиМатрицы.Добавить("536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354");
СтрокиМатрицы.Добавить("502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844");
СтрокиМатрицы.Добавить("388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730");
СтрокиМатрицы.Добавить("354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536");
СтрокиМатрицы.Добавить("468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194");
СтрокиМатрицы.Добавить("776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798");
СтрокиМатрицы.Добавить("662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0");

Для К = 0 По КоличествоУзлов - 1 Цикл
    Ряд = О2.Утилиты().МассивЧиселИзСтроки(СтрокиМатрицы[К]);
    Для К1 = 0 По КоличествоУзлов - 1 Цикл
        Расстояния[К][К1] = Ряд[К1];
    КонецЦикла;
КонецЦикла;

4. Регистрация матрицы транзитов

Матрица расстояний регистрируется в модели как транзит. Ссылка на созданный транзит сохраняется в переменную МатрицаТранзита и используется на следующих шагах для привязки целевой функции и ограничения.

// Регистрируем матрицу расстояний как транзит
МатрицаТранзита = Модель
    .Транзиты()
    .ДобавитьМатрицу(Расстояния, "Расстояние");

5. Ограничение длины маршрута

Длина каждого маршрута ограничивается 2000 единицами. Для этого заводится ресурс маршрутизации Пробег, который накапливает пройденное расстояние по ходу маршрута. Параметры метода Модель.Ресурсы().Добавить(...):

первый аргумент — транзит, по которому накапливается ресурс (МатрицаТранзита);
максимальный резерв на узле — 0: ресурс растёт ровно на величину расстояния между узлами, без запаса;
ёмкость — 2000: верхний предел накопленного расстояния для каждого ТС;
признак накопления с нуля — Истина: на стартовой точке ресурс равен нулю;
имя ресурса — "Пробег": метка для доступа к накопленному значению из решения.

// Ограничение длины маршрута: каждое ТС не проезжает больше 2000 единиц
Модель
    .Ресурсы()
    .Добавить(МатрицаТранзита, 0, 2000, Истина, "Пробег");

6. Описание целевой функции

Целевая функция состоит из двух слагаемых. Первое — суммарная длина всех маршрутов (коэффициент транзита равен 1). Второе — штраф за разброс длин маршрутов между ТС. В модели маршрутизации это достигается через коэффициент балансировки ресурса: метод УстановитьКоэффициентБалансировки добавляет в целевую функцию слагаемое, пропорциональное разнице между максимальным и минимальным суммарным пробегом по маршрутам. Чем больше коэффициент, тем сильнее решатель стремится выровнять длины маршрутов.

// Минимизируем суммарную длину маршрутов
Модель
    .ЦелеваяФункция()
    .УстановитьКоэффициентТранзита(МатрицаТранзита);

// Дополнительно штрафуем за разброс длин маршрутов (коэффициент балансировки = 100)
Модель
    .ЦелеваяФункция()
    .УстановитьКоэффициентБалансировки("Пробег", 100);

7. Решение модели

Для получения решения достаточно вызвать метод Решить. Модель сама подбирает маршруты с учётом разных стартов, общего финиша, ограничения расстояния и двухкомпонентной целевой функции.

// Решение модели
Решение = Модель.Решить();

8. Вывод результатов

Каждый маршрут итерируется по остановкам. Помимо имени ТС и пути, на каждой остановке выводится накопленное расстояние — оно доступно через поле Остановка.Ресурсы["Пробег"]. После пути выводится итоговая длина маршрута. Максимальное расстояние среди всех маршрутов определяется вручную при итерации.

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=0; ЧН=0; ЧГ=0";

    Сообщение = СтрШаблон("Задача маршрутизации с разными стартами (%1 ТС, %2 вершин, max 2000)%3", 4, КоличествоУзлов, Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Значение целевой функции: %1%2", Формат(Решение.ЗначениеЦелевойФункции(), ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;

    МаксимальноеРасстояние = 0;
    Для Каждого Маршрут Из Решение.Маршруты() Цикл
        ПунктыПути = Новый Массив();
        НакопленноеРасстояние = 0;
        Для Каждого Остановка Из Маршрут.Остановки Цикл
            НакопленноеРасстояние = Остановка.Ресурсы["Пробег"];
            ПунктыПути.Добавить(СтрШаблон("%1 (%2)", Остановка.Узел, Формат(НакопленноеРасстояние, ФорматВывода)));
        КонецЦикла;
        Путь = СтрСоединить(ПунктыПути, " → ");

        МаксимальноеРасстояние = Макс(МаксимальноеРасстояние, НакопленноеРасстояние);

        Сообщение = Сообщение + СтрШаблон(
            "Маршрут %1 (длина %2): %3%4",
            Маршрут.ИмяТранспортногоСредства,
            Формат(Маршрут.Стоимость, ФорматВывода),
            Путь,
            Символы.ПС
        );
    КонецЦикла;

    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Максимальное расстояние маршрута: %1", Формат(МаксимальноеРасстояние, ФорматВывода));

    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());
КонецЕсли;

Полный код решения задачи

Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.

// Создаём построитель параметров модели маршрутизации
Построитель = О2.Модели()
    .МодельМаршрутизации()
    .СоздатьПостроительПараметровМодели();

// Добавляем 17 узлов
КоличествоУзлов = 17;
Для К = 0 По КоличествоУзлов - 1 Цикл
    Построитель.ДобавитьУзел("Узел" + К);
КонецЦикла;

// Добавляем 4 транспортных средства с разными стартами и общим финишем
Построитель.ДобавитьТранспортноеСредство(1, 0, "ТС1");
Построитель.ДобавитьТранспортноеСредство(2, 0, "ТС2");
Построитель.ДобавитьТранспортноеСредство(15, 0, "ТС3");
Построитель.ДобавитьТранспортноеСредство(16, 0, "ТС4");

// Фиксируем состав модели
Модель = Построитель.СоздатьМодель();

// Матрица расстояний 17 × 17 (классический пример TSP/VRP)
Расстояния = О2.Утилиты().Массив2DИзвестногоРазмера(КоличествоУзлов, КоличествоУзлов);

СтрокиМатрицы = Новый Массив();
СтрокиМатрицы.Добавить("0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662");
СтрокиМатрицы.Добавить("548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210");
СтрокиМатрицы.Добавить("776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754");
СтрокиМатрицы.Добавить("696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358");
СтрокиМатрицы.Добавить("582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244");
СтрокиМатрицы.Добавить("274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708");
СтрокиМатрицы.Добавить("502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480");
СтрокиМатрицы.Добавить("194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856");
СтрокиМатрицы.Добавить("308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514");
СтрокиМатрицы.Добавить("194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468");
СтрокиМатрицы.Добавить("536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354");
СтрокиМатрицы.Добавить("502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844");
СтрокиМатрицы.Добавить("388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730");
СтрокиМатрицы.Добавить("354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536");
СтрокиМатрицы.Добавить("468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194");
СтрокиМатрицы.Добавить("776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798");
СтрокиМатрицы.Добавить("662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0");

Для К = 0 По КоличествоУзлов - 1 Цикл
    Ряд = О2.Утилиты().МассивЧиселИзСтроки(СтрокиМатрицы[К]);
    Для К1 = 0 По КоличествоУзлов - 1 Цикл
        Расстояния[К][К1] = Ряд[К1];
    КонецЦикла;
КонецЦикла;

// Регистрируем матрицу расстояний как транзит
МатрицаТранзита = Модель
    .Транзиты()
    .ДобавитьМатрицу(Расстояния, "Расстояние");

// Ограничение длины маршрута: каждое ТС не проезжает больше 2000 единиц
Модель
    .Ресурсы()
    .Добавить(МатрицаТранзита, 0, 2000, Истина, "Пробег");

// Минимизируем суммарную длину маршрутов
Модель
    .ЦелеваяФункция()
    .УстановитьКоэффициентТранзита(МатрицаТранзита);

// Дополнительно штрафуем за разброс длин маршрутов (коэффициент балансировки = 100)
Модель
    .ЦелеваяФункция()
    .УстановитьКоэффициентБалансировки("Пробег", 100);

// Решение модели
Решение = Модель.Решить();

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=0; ЧН=0; ЧГ=0";

    Сообщение = СтрШаблон("Задача маршрутизации с разными стартами (%1 ТС, %2 вершин, max 2000)%3", 4, КоличествоУзлов, Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Значение целевой функции: %1%2", Формат(Решение.ЗначениеЦелевойФункции(), ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;

    МаксимальноеРасстояние = 0;
    Для Каждого Маршрут Из Решение.Маршруты() Цикл
        ПунктыПути = Новый Массив();
        НакопленноеРасстояние = 0;
        Для Каждого Остановка Из Маршрут.Остановки Цикл
            НакопленноеРасстояние = Остановка.Ресурсы["Пробег"];
            ПунктыПути.Добавить(СтрШаблон("%1 (%2)", Остановка.Узел, Формат(НакопленноеРасстояние, ФорматВывода)));
        КонецЦикла;
        Путь = СтрСоединить(ПунктыПути, " → ");

        МаксимальноеРасстояние = Макс(МаксимальноеРасстояние, НакопленноеРасстояние);

        Сообщение = Сообщение + СтрШаблон(
            "Маршрут %1 (длина %2): %3%4",
            Маршрут.ИмяТранспортногоСредства,
            Формат(Маршрут.Стоимость, ФорматВывода),
            Путь,
            Символы.ПС
        );
    КонецЦикла;

    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Максимальное расстояние маршрута: %1", Формат(МаксимальноеРасстояние, ФорматВывода));

    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());
КонецЕсли;

Скачать пример

Условия задачи​

Решение задачи​

1. Выбор модели​

2. Создание модели​

3. Ввод данных​

4. Регистрация матрицы транзитов​

5. Ограничение длины маршрута​

6. Описание целевой функции​

7. Решение модели​

8. Вывод результатов​

Полный код решения задачи​