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

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

Як завжди, це було як сніг на голову. В когось антибіотики скінчились акурат посередині курсу, до лікаря запис через 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

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