Задача про кільцевий маршрут

Зміст задачі про кільцевий маршрут: треба обійти т точок, у кожній з яких необхідно побувати тільки один раз; маршрут має бути кільцевим. Витрати на перехід від і -ї до -ї точки відомі і дорівнюють величинам . Знайти кільцевий маршрут з мінімальними сумарними витратами.

До цієї задачі можна звести задачі оптимального використання транспортних засобів (наприклад, бензозаправник, молокорозвізник та інше), знаходження послідовності обробки деталей верстатами, обробка замовлень агрегатами (чи цехами) з точки зору мінімізації простоїв агрегатів за причиною їх переналагодження та інші задачі повного обходу множини точок.

Якщо згідно з вимогами перехід від і -ї до -ї точки неможливий (тобто має місце заборона -зв’язку) то відповідне значення .

Математична модель задачі про кільцевий маршрут наступна:

– цільова функція

,

– обмеження

– умова тільки одного входу та одного виходу з

точки;

– умова тільки двох станів змінних: 0 та 1;

– умова виключення петель з маршруту;

маршрут у вигляді замкнутого контуру.

За нашого часу найефективнішим методом розв’язування задачі є метод розгалужень і меж, який подалі розглядається.

Цей метод передбачає знаходження оптимального варіанта за кілька етапів, причому на кожному етапі ведеться оцінка означеної множини допустимих варіантів, з яких визначають найперспективніші. Таке зменшення кількості допустимих варіантів дозволяє уникнути повного перебору варіантів.

Метод розгалужень і меж включає наступні етапи розв’язування:

– знаходження нижньої оцінки цільової функції для множини допустимих варіантів;

– складання можливих варіантів розгалужень пошуків кільцевих маршрутів;

– знаходження оцінок знайдених розгалужень маршрутів і вибір з них перспективного напрямку пошуку;

– складання продовження розгалуження перспективного напрямку допустимих варіантів;

– вибір оптимального варіанта кільцевого маршруту.

Вперше цей метод був застосований у 1960 р. до задач цілочислового програмування, у 1963 р. – відповідно до задачі кільцевого маршруту.