OKRUŽNÍ DOPRAVNÍ PROBLÉM A APROXIMAČNÍ METODY PRO JEHO ŘEŠENÍ

24.09.1999 | Odborné konference

Circular transport problem and apperoximation methods for its solving

Petr Kučera

Adresa autora:

Petr Kučera, katedra operační a systémové analýzy, PEF ČZU Praha

Anotace:

Okružní dopravní problém patří mezi tzv. NP-úplné problémy. To znamená, že neexistuje efektivní algoritmus, který by našel přesné matematické optimum tohoto problému. Existuje však řada aproximačních metod (heuristik), jejichž výsledky lze považovat za ekonomické optimum. Cílem tohoto příspěvku je především podat o těchto metodách stručnou informaci a dále zjistit zájem účastníků sekce o konkrétní otázky týkající se okružního dopravního problému a zohlednit je při přípravě příspěvků na toto téma na příští vědecké konference.

Summary:

The traveling salesman problem belongs to so called NP-complete problems. It means, there exists no effective algorithm finding a strict mathematical optimum of this problem. Fortunately, great number of heuristics (approximation methods) are known, using them one can obtain solutions, that may be considered economic optima. The aim of this contribution is to give a brief information on these methods. An interest of members of the section in some special matter may influence the preparation of contributions for next conferences.

Klíčová slova: okružní dopravní problém (problém obchodního cestujícího), aproximační metoda (heuristika), matematické optimum, ekonomické optimum.

Key words: traveling salesman problem, heuristics (approximation methods), mathematical optimum, economic optimum

Celý tento přehled se bude týkat pouze jednookruhového okružního problému (problému obchodního cestujícího).Ten lze stručně formulovat takto: Je dáno n měst a vzdálenosti (sazby) mezi každou dvojicí měst (uspořádané do matice sazeb). Je třeba najít trasu procházející okružním způsobem všechna města a vracející se do města, odkud vyšla, tak, aby byla co nejkratší.

Příspěvek se skládá ze dvou částí. Prvá z nich se snaží roztřídit aproximační metody pro řešení problému obchodního cestujícího do skupin a stručně charakterizovat vlastnosti těchto jednotlivých typů metod. Ve druhé části jsou potom vytypovány třídy úloh, u nichž je uvedeno, jaká přesnost je zaručena (matematicky dokázána) při jejich řešení.

Příspěvek byl sestaven převážně na základě studia matematické literatury. Pro čtenáře tohoto sborníku, kteří jsou většinou mnohem více obeznámeni s aplikačně zaměřenou literaturou, může být zajímavá konfrontace jejich informací s fakty zde uvedenými.

Typy metod

Metody pro řešení okružního problému lze především rozdělit na dvě skupiny podle toho, zda konstruují výsledné řešení od začátku (začínají “na zelené louce”) nebo požadují výchozí řešení, které vylepšují postupnými iteracemi.

1) Metody konstruující výsledné řešení od počátku lze rozdělit na několik dalších podskupin:

1. Metody založené na přístupech fungujících pro širší třídy distribučních úloh: Sem patří např. Vogelova metoda nebo metody založené podobně jako Habrova metoda na diferencích křížových součtů pro čtveřice sazeb. Výhodou těchto metod je, že dávají relativně dobré výsledky pro úlohy s nesymetrickou maticí sazeb, nevýhodou je, že pro ně není znám žádný odhad přesnosti řešení, a to ani pro některou speciální třídu úloh.

2. Kombinatorické metody (či metody teorie grafů) tvoří asi nejširší skupinu, kterou lze ještě dále rozdělit:

1.2.1) Hladové metody (greedy methods) jsou takové, které do výsledného řešení v celém průběhu jeho konstrukce přidávají vždy v daném okamžiku ten nejvýhodnější prvek (“nejlepší sousto”) a v dalším postupu se k již vytvořené části řešení nevracejí. Tyto metody kromě toho, že jsou velmi rychlé (vlastně nejrychlejší možné), jsou i až překvapivě přesné. Konkrétně pro úlohy se symetrickou maticí sazeb, které navíc splňují trojúhelníkovou nerovnost, tj. přímá vzdálenost mezi dvěma městy není nikdy delší než trasa přes některé další město, dává většina z těchto metod řešení s hodnotou účelové funkce nejvýše dvakrát větší než matematické optimum. Jsou ovšem poměrně obtížně formulovatelné pro úlohy s nesymetrickou maticí sazeb. Vyjímkou mezi těmito metodami je metoda nejbližšího souseda, která nezaručuje výše uvedenou přesnost řešení, ale naopak pro úlohy s nesymetrickou maticí sazeb ji lze snadno použít.

1.2.2) Dále si všimněme metod vycházejících z řešení přiřazovací úlohy s toutéž maticí sazeb. Klasická patching method postupně “sešívá” kratší cyklické trasy určené řešením přiřazovací úlohy v jednu procházející všemi městy, zatímco metoda publikovaná v [3] (nazývejme ji Švastovou metodou) zavádí během řešení prohibitivní sazby tak, aby zmíněné kratší cykly nevznikaly. Svými vlastnostmi jsou tyto metody podobné skupině 1.1). Švastova metoda dosud nebyla v matematických kruzích prakticky vůbec zkoumána.

1.2.3) Ostatní kombinatorické metody již nelze dobře rozčlenit do skupin, v nichž by byly metody velmi si blízké svou podstatou, a tudíž mají i různé vlastnosti. Patří sem ještě jedna důležitá metoda, a to Christofidova metoda. Lze ji formulovat pouze pro úlohy se symetrickou maticí sazeb. Pro úlohy, které kromě toho splňují trojúhelníkovou nerovnost, dává řešení, které je nejvýše 1,5-krát horší než matematické optimum.

3. Existují i metody, které jsou kombinací skupin 1.1) a 1.2), tj. využívají během výpočtu kombinatorických algoritmů, ale v jisté fázi výpočtu např. řeší určitou dopravní úlohu. Charakterizovat je lze stejnými vlastnostmi jako skupinu 1.1).

4. Ostatní metody, které celé řešení samy konstruují, jsou již značně speciální a svou podstatou i vlastnostmi odlišné. Z nich připomeňme metodu branch and bound a Arorovu metodu, o níž bude ještě dále řeč.

2) K popisu způsobu práce metod vylepšujících dané výchozí řešení použijme terminologii teorie grafů a na trasu obchodního cestujícího pohlížejme jako na cyklus v grafu. Tyto metody v každé iteraci odeberou z cyklu několik hran a nahradí je jinými tak, aby opět vznikl cyklus, ale s nižší hodnotou účelové funkce. Tímto způsobem pracují tak dlouho, dokud jsou schopny nějakou takovou výměnu najít a provést. Jednotlivé metody se mezi sebou liší počtem hran a případně i výběrem skupin hran, jejichž výměny testují a realizují. Nejlepších výsledků dosahuje Linova-Kerninghanova metoda, která dokonce v jednotlivých iteracích uvažuje a provádí výměnu různého počtu hran. Pro tyto iterační metody není znám žádný odhad přesnosti řešení, a je dokonce matematicky dokázáno, že nelze žádný takový odhad nalézt. Přesto je Linova-Kerninghanova metoda považována na základě výsledků jejího použití v praxi za jednu z nejlepších. Iterační metody totiž dávají dobré výsledky zejména pro úlohy velkých rozměrů (100 a více měst), patrně proto, že vyšší počet měst umožňuje více kombinací při záměnách hran, zatímco u metod konstruujících výsledné řešení od počátku obvykle chyba řešení s velikostí dat roste. Nevýhodou iteračních metod jsou poněkud horší výsledky pro úlohy s nesymetrickou maticí sazeb. Při záměnách hran totiž dochází většinou k tomu, že některý úsek původní trasy prochází obchodní cestující v novém řešení v opačném směru, a použití takových záměn tedy vyžaduje symetrickou matici sazeb.

Přesnost řešení pro speciální případy úloh

Nejpřesnější známá metoda byla nedávno objevena pro euklidovský okružní problém: Města jsou body v euklidovském prostoru a sazby jsou euklidovské vzdálenosti mezi nimi. Arorova metoda (viz [1]) umožňuje najít řešení s libovolně malou chybou, kterou si uživatel předem zadá. S menší požadovanou chybou pochopitelně roste doba výpočtu, ale stále závisí polynomiálně na počtu měst. Konkrétně pro euklidovskou rovinu řešení s hodnotou účelové funkce (1+

)-krát větší než matematické optimum algoritmus najde v čase řádově

, kde n je počet měst. Na základě tohoto vztahu a zkušenosti s dobou výpočtu touto metodou na konkrétní výpočetní technice si může uživatel odhadnout, jak se změní doba výpočtu při větším počtu měst nebo vyšší požadované přesnosti a zda je disponibilní technika schopna takový výpočet efektivně realizovat.

Další třídou úloh jsou okružní problémy se symetrickou maticí sazeb splňující trojúhelníkovou nerovnost. Christofidova metoda pro ně dává řešení s účelovou funkcí rovnou nejvýše 1,5-násobku matematického optima.

Pro žádnou širší třídu již není známa aproximační metoda, pro niž by byl znám odhad chyby tohoto typu. V praxi ovšem dávají velmi dobré výsledky i metody, jejichž kvalita není matematicky dokázána (např. Linova-Kerninghanova metoda).

Další informace o metodách, pro které zde nejsou odkazy na literaturu, lze najít v [2].