Приклад узагальненої задачі комівояжера

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Нещодавно наші урядовці вирішили поборотись з надмірним споживанням антибіотиків.

Як завжди, це було як сніг на голову. В когось антибіотики скінчились акурат посередині курсу, до лікаря запис через 3 доби, а тре на вечір. Та й не факт, що новий папірець від лікаря буде «катити», бо виданий три дні до впровадження нововведення в першій-ліпшій аптеці чомусь не «катить»)

Що робити? Як завжди, тре оббігти ближні аптечні мережі, щоб знайти ту, котра ще чомусь продає (або вже «порішала»). При цьому аптеки однієї мережі можна вважати як такі, що працюватимуть однаково: якщо аптека № 1 мережі А відмовляє у продажі, то будь-яка інша аптека мережі А теж відмовить.

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

Ця задача відноситься до класу NP-складних задач. Розв’язок — повний перебір.

Поділюсь використанням відкритих даних openstreetmap та наявних бібліотек мови Python:

1. Виберемо всі аптеки поблизу

from pyrosm import OSM, get_data
osm = OSM(get_data("kiew"))
сustom_filter = {'amenity': True, "pharmacy": True}
pois = osm.get_pois(custom_filter=custom_filter).query("amenity=='pharmacy'").query("lat <= 50.4625").query("lat >= 50.4425").query("lon <= 30.4833").query("lon >= 30.4633");

2. Маємо такі аптечні мережі

pois['name'].value_counts()
Аптека Доброго Дня        5
Аптека оптових цін        4
Аптека спеціальних цін    1
Фармація                  1
Екостатус                 1
Жолдифарм                 1
Аптека 03                 1
Аптека №52                1
Космо                     1
Аптека приємних цін       1
Аптека оптових ц..        1
Аптека №6                 1
Домашня аптека            1
Аптека 911                1

3. Обчислимо відстані між аптеками.

Функція визначення найкоротшого шляху:

import osmnx as ox
import networkx as nx
def get_rl(G, src, dst):
    origin_node, do = ox.nearest_nodes(G, src["lon"], src["lat"], True)
    destination_node, dd = ox.nearest_nodes(G, dst["lon"], dst["lat"],True)
    route = nx.shortest_path(G, origin_node, destination_node)
    return round(sum(ox.utils_graph.get_route_edge_attributes(G, route, 'length') ), 1)

Йтиму пішки:

G = ox.graph_from_point((50.4525, 30.4733), dist=3000, network_type='walk')

Розрахуємо матрицю вартостей переходу:

dm = []
for i in range(len(pois)):
    dm.append([0] * len(pois))
    for x in range(len(pois)):
       for y in range(len(pois)):
           dm[x][y] = get_rl(G4, pois.iloc[x], pois.iloc[y])

4. Найдовший маршрут між всіма аптечними мережами має протяжність у 18 км

Намалюю його:

def print_route(G, pois, route):
    proutes = []
    for idx in range(len(route) - 1):
        origin_node, do = ox.nearest_nodes(G, pois.iloc[route[idx]]["lon"], pois.iloc[route[idx]]["lat"], True)
        destination_node, dd = ox.nearest_nodes(G, pois.iloc[route[idx+1]]["lon"], pois.iloc[route[idx+1]]["lat"],True)
        proutes.append(nx.shortest_path(G, origin_node, destination_node))
    ox.plot_graph_routes(G, proutes, route_alpha=0.8, route_linewidth=10, route_colors=['r','#FFA500','b','r','#FFA500','b','r','#FFA500','b','r','#FFA500','b','r']);print_route(G4, pois, [20, 0, 1, 2, 3, 5, 7, 8, 9, 13, 14, 15, 16, 17])

Рис. 1. Найгірший (найдовший маршрут)

5. Інтуітивно я вибрав маршрут що відповідає розв’язку жадібного алгоритму. Це досить простий алгоритм, та й обчислюється швидко.

def find_tsp_naive(processedidx, processedsets, dm, pois, currentlen):
    if len(processedidx) == len(pois['name'].value_counts()):
       return currentlen
    pd = pois.iloc[0]
    plen = sys.maxsize
    for d in range(len(pois)):
       if d in processedidx:
            continue
       if pois.iloc[d]["name"] in processedsets:
           continue
       if dm[processedidx[-1]][d] >= plen:
           continue
       plen = dm[processedidx[-1]][d]
       pd = d
    return find_tsp_naive(processedidx + [pd], processedsets + [pois.iloc[pd]["name"]] , dm, pois, currentlen + plen)find_tsp_naive([20], [pois.iloc[20]["name"]], dm, pois, 0)

Жадібний алгоритм за кілька секунд знайшов шлях довжиною 5 км 600 м.

Рис.2. Маршрут, отриманий жадібним алгоритмом

5. Знайдемо найкращий маршрут. Для цього доведеться використати повний перебір. Це досить довго, є певні евристики, але, на жаль, вони не дають 100% кращий результат. Що дає 100% результат та легко імплементувати то покращення методів гілок та меж.

def find_tsp(processedidx, processedsets, dm, pois, currentlen, minlen, vc):
    if len(processedidx) == vc:
        return currentlen
    for d in range(len(pois)):
       if currentlen + dm[processedidx[-1]][d] >= minlen:
           continue
       if d in processedidx:
          continue
       if pois.iloc[d]["name"] in processedsets:
         continue
       minlen = min(find_tsp(processedidx + [d], processedsets + [pois.iloc[d]["name"]] , dm, pois, currentlen + dm[processedidx[-1]][d], minlen, vc), minlen)
  return minlen
find_tsp([20], [pois.iloc[20]["name"]], dm, pois, 0, sys.maxsize, len(pois['name'].value_counts()))

За допомогою повного перебору знайдено кращий маршрут довжиною 4 км 900 м. На обрахунок знадобилось приблизно година часу на моєму домашньому ноуті (Dell G3, 8 ГБ ОЗУ, 2.3 Ггц ЦПУ, рік випуску — 2019).

Рис. 3. Найкоротший маршрут, отриманий повним перебором

Різниця між кращим маршрутом (4,9 км) та інтуїтивно обраним (жадібний алгоритм) (5,6 км) порядка 700 м.

В середньому, за годину людина проходить 5 км пішки, тобто за час пошуку розв’язку в середньому людина пройде з 5 км.

Висновок: інколи краще не витрачати час на пошук найкращого рішення, а задовольнитись інтуїтивним .

Богдан Артюшенко, к.т.н., 2022

👍ПодобаєтьсяСподобалось10
До обраногоВ обраному6
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Але справа от у чому: задачі комівояжера не існує у реалі. Це виключно маразм — вчити 100500 методів вирішення того, що ніколи не доведеться вирішувати. Тим більше вирішувати на швидкість.

Обчислювальні задачі існують об’єктивно, незалежно од того, чи зустрічалися вони конкретно Вам чи ні.

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

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

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

Я не кажу що не існує самого класу задач з оптимізації маршрутів. Лише факт, що вони можуть вирішуватися ефективно і неоптимальними алгоритмами. А якщо задача реально має хоча б кілька сотень гілок — от лише тоді і треба дивитися теорію. Таку задачу [одночасно з великим навантаженням, з критичним часом виконання, з необмеженими ресурсами на нормалізацію початкових даних], доведеться вирішувати хіба що 1 на 10 000 програмістів. Замість того щоб зубрити всім усе це лайно.

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

Що реально потрібно знати? Як називається ця задача. Щоб коли (якщо взагалі) реально доведеться мати справу з випадком, близьким до теоретичного [там проблема в підготовці початкових даних, вона недешева та вимагає постійного контролю якості даних] — лише тоді й знайти готове рішення. Не вигадати, не згадати що колись вчив, а тупо знайти готове.

До речі, ти сам помітив, що в тебе самописний варіант. І так буде майже завжди, якщо дійсно готовий робити задачу оптимізації процесу, а не гратися у цяцьки.

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

Ти ж коли планував задачу забору біоматеріалу — напевне забув врахувати ефект пам′яті. Так, в тебе є людина в процесі, людина має виконувати твою задачу із застосуванням або пам′яті, або логіки і пам′яті [з усіма наслідками далеко не оптимального алгоритму видалення та неможливості відокремлювати однорідні дані]. Іншими словами, вирішивши «задачу комівояжера» у чисто машинний спосіб, ти втратиш працездатність комівояжера.

Якщо коротко, то задача не має загального рішення. Лише кілька методів, які допомагають її змоделювати. Важливим є факт, що метод перебору — найефективніший, і якщо задачу вдається кластеризувати на підзадачі — це дозволяє його використати. А ще він є ефективним методом контролю, тобто, застосувавши тимчасово незадіяний обчислювальний ресурс (нічні години) можна проконтролювати ефективність вирішення. Це використовується у реальних high load процесах, а також у логістичних задачах.

Суть підходу — не просто дати єдине вірне рішення, а й запропонувати кілька варіантиів для вирішення людиною. Чому так: у початкових даних не враховані усі фактори, деякі могли з′явитися вже після того, як запрограмований алгоритм. Наприклад: новий водій, йому потрібно вивчити новий маршрут, тому деякі вектори матимуть пріоритет.

В статті 2 реалізації:
1. Жадібний алгоритм.
2. Повний перебір.

Ще є алгоритм Дейкстри. Він трішки складніше, але цікавіший. До речі його вивчають в вишах.

ще є алгоритм флойда уоршелла, він між усіма парами вершин графа вираховує

Дякую. декстра то алгоритм трохи іншої задачі. Нажаль. cs.stackexchange.com/...​avelling-salesman-problem

Почитав. Не зрозумів в чому відмінність. Треба знайти оптимальний шлях і повернутися до старту.

Я його імплементував років 10 тому. Може щось забув.
Повний перебір виконувався дуже довго.

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

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

є ще наближенні методи — використовуючи minimal spanning tree (будується через Prim’s алгоритм) і Christofides алгоритм

ОЛХ поспішає на допомогу!

А что, онлайн-сервисы по продаже лекарств без рецептов еще не появились? Идея для перспективного стартапа, кстати.

Есть, но они ни хрена не работают

Законом заборонено

есть конечно, на каждом третьем заборе пиарятся их телеграм каналы, биткойн — закладки и т.д. вот только 1) цена 2) качество 3) скорость 4) если первые три ок — то 100% торчат волосатье уши. правда чаще по ним продают те безрецептурные медикаменты которые привыкание вызывают и срок дают. антибиотики к ним не так чтоб относились.

Если расскажешь как достичь качества в этих схемах — совершишь революцию. Пока можно тупо сдохнуть от подделки медикамента.

Підписатись на коментарі