PROGRAM PRO SNADNÉ ŘEŠENÍ ÚLOHY OBCHODNÍHO CESTUJÍCÍHO S DESETI BODY A JEHO VYUŽITÍ Josef Košťálek ÚVOD Předmětem tohoto příspěvku je popis fungování a využití programu EDITA 4, který jsem sestavil pro potřeby řešení Okružního dopravního problému, někdy rovněž označovaného jako Úloha obchodního cestujícího (Traveling Salesman Problem) a to v rozsahu 1 až 10 míst. Úloha obchodního cestujícího spočívá v nalezení nejkratší trasy na množině vytyčených bodů tak, aby trasa končila v tom bodě, ve kterém začala. Tento a podobné problémy jsou velice frekventované v logistice včetně vnitropodnikové logistiky, ale lze se s nimi setkat rovněž v odvětvích jako je výroba čipů, kde se plánuje nejkratší trasa pohybu laseru. Logistika je obor, který se díky intenzitě obchodování a raketovému vývoji telekomunikačních i přepravních technologií velice dynamicky rozvijí, takže lze konstatovat, že se jedná o problematiku vysoce aktuální. Zejména v kontextu dozvuků krize a rostoucí konkurence, kdy je třeba hledat úspory ve všech zbytečně vynaložených nákladech lze spořit také pomocí optimalizací logistických tras, což šetří nejen peníze, ale také čas. Co představovaný program EDITA 4 dokáže? Jak bylo řečeno počet míst, které spojuji trasou lze libovolně měnit v mezích jedna až deset. Program funguje ve snadno dostupném prostředí MS Excel. A mou snahou bylo, aby způsob zadávání požadovaných míst byl co nejjednodušší a totéž platí i pro interpretaci výsledné trasy.
1 ÚLOHA OBCHODNÍHO CESTUJÍCÍHO JAKO JEDEN Z MATEMATICKÝCH PROBLÉMŮ TISÍCILETÍ Ačkoliv se jedná o velice jednoduše zadaný úkol (najít nejkratší spojnici množiny bodů tak, aby obchodní cestující navštívil každý bod právě jednou a vrátil se zpět do bodu, ze kterého vyjel), jeho řešení je dodnes limitováno počtem zadaných bodů. Jak uvádí ([4], s. 8) roku 1900 se v Paříži konal II. mezinárodní matematický kongres a mimo jiných na něm vystoupil německý profesor z göttingenské univerzity David Gilbert s příspěvkem týkajícím se 23 vybraných důležitých matematických problémů, jejichž řešení nebylo známo. O sto let později r. 2000 bylo na univerzitě College de France v Paříži konstatováno, že z původních dvaceti tří problémů byla většina z nich vyřešena nebo vyvrácena, ale 7 problémů stále čeká na řešení. Dále bylo prohlášeno, že kdo některý z těchto sedmi problémů vyřeší obdrží odměnu milion dolarů. Prostředky na odměny poskytne Clayův matematický ústav univerzity Cambridge v USA. Mecenášem a zakladatelem tohoto ústavu zaměřeného na propagaci a rozvoj matematického výzkumu je majitel investičních fondů Landon Clay. Zajímavostí je, že jeden z těchto sedmi problémů byl v nedávné době prohlášen za vyřešený. Jednalo se o dokázání Poincareho domněnky v oblasti topologie (obor geometrie zabývající se vlastnostmi povrchů a obecných útvarů). Jak uvádí ([2], s. 94-95), přesvědčivý důkaz podal r. 2002 Grigorij Perelman ze Steklovova matematického institutu v Petrohradě. Trvalo několik let, než byl tento důkaz prohlášen světovou matematickou komunitou za nezvratný. Po té byl vydán souhlas s vyplacením odměny milion dolarů, ovšem geniální matematik peníze odmítl s tím, že je nepotřebuje. Nejdůležitější informací je fakt, že úloha obchodního cestujícího je stále jedním ze šesti nevyřešených matematických problémů považovaných za problémy tisíciletí. Jak by mělo vypadat řešení tohoto problému? Jak uvádí ([1], s. 20-22), hledá se ,,dobrý“ algoritmus, který dokáže určit za všech okolností nejkratší cestu pro sebe vyšší počet bodů. Jaký je rozdíl mezi ,,špatným“ a ,,dobrým“ algoritmem? Určujícím kritériem je spotřeba času v závislosti na počtu míst, pro která bude trasa hledána. Přitom se časová spotřeba uvažuje přímo úměrná počtu kroků, kterými algoritmus dojde k optimálnímu řešení tj. nejkratší trase. U dobrého algoritmu je počet kroků, resp. časová spotřeba závislá na počtu míst (n) vyjádřena lineární nebo mocninou funkcí. Potom hovoříme o polynomiálním čase a polynomiálních algoritmech jako dobrých viz vzorec 1 a 2.
T = n k ; kde k ∈ N ;
(1)
T = a • n k 1 + b • n k 2 + c • n k 3 ... kde k 1, k 2, k 3... ∈ N
(2)
Příklad ,,špatného“ algoritmu je např. řešení spočívající ve vyzkoušení všech kombinací a výběru té nejlepší tj. té dávající nejkratší trasu. Pokud má cestující navštívit 5 míst a stojí v místě č. 1 má při volbě prvního kroku na výběr z devíti možností. Vybere si např. místo č. 2, v dalším kroku se výběr o jedno místo sníží o místo, které v předchozím kroku vybral a to se stále opakuje. Příklad situace ilustruje schéma. 1. Schéma 1: Celkový počet kombinací
Zdroj: Vlastní Pokud se bude řešení hledat pomocí prozkoumání všech kombinací časová spotřeba bude faktoriálně růst v závislosti na počtu míst jak popisuje vzorec 3.
T = (n − 1)!
(3)
Stejně špatným algoritmem je pokud dojde ke změně z mocninné resp. polynomiální závislosti na exponenciální závislost, kterou znázorňuje vzorec 4.
T = k n ; kde k ∈ N
(4)
Rozdíl mezi ,,dobrým“ (polynomiálním) a ,,špatným“ (jiným než polynomiálním) algoritmem je dobře patrný z hodnot v tab. 1, kde je hodnota koeficientu k = 3. Na její hodnotě nezáleží nejde o výsledek jde o rychlost růstu. Tempo růstu implikuje časovou náročnost takového rozsahu, že pro jisté vysoké hodnoty počtů míst n se problém stává neřešitelným. Tab. 2: Příklady časové náročnosti podle funkční závislosti algoritmů na počtu míst (n)
Zdroj: Vlastní
2
POPIS PROGRAMU
Pro potřeby řešení výše popisované Úlohy obchodního cestujícího jsem sestavil program, který jsem pojmenoval Edita 4. Limitem tohoto programu je 10 míst, ale výpočet je zobecněn tak, že počet
míst lze měnit, stejně jako polohy jednotlivých bodů. Zadávání polohy bodů je vstupem do tohoto programu. Zde jsem usiloval o jeho co nejvyšší jednoduchost. Prvním krokem je výběr režimu zadávání hodnot (polohy bodů). Body lze zadat pomocí souřadnic nebo zakreslením bodů do tabulky. Obr. 3: Výběr režimu zadávání hodnot
Zdroj: Vlastní – Program Edita 4 První možností je zadat do připravené tabulky souřadnice a názvy bodů (zadaný bod se zakreslí jako tečka) viz obr. 2. Obr. 2: Souřadnicové zadávání bodů
Zdroj: Vlastní – Program Edita 4 Pokud se tento způsob zadávání nejeví jako vhodný je připravena možnost zadat polohu bodů do souřadnicového systému o velikosti (0 až 9) x (0 až 9) jednotek viz obr. 3. Pokud jde o zvýšení rozlišovací schopnosti tohoto souřadnicového systému je možné použít tytéž principy fungující pro 0 až 9 bodů také pro 0 až 50 nebo 0 až 100 bodů. Tabulka může představovat např. montážní halu, ve které jsem se rozhodl najít nejkratší vzdálenost mezi deseti pracovišti.
Obr. 3: Zadání bodů zakreslením
Zdroj: Vlastní – Program Edita 4 Tím je dána množina bodů, pro kterou je hledána nejkratší spojnice. Je zde uvažována rovnost mezi vzdáleností z bodu 1 do bodu 2 a vzdáleností z bodu 2 do bodu 1. V praxi tato rovnost nutně platit nemusí, v případě potřeby by bylo možné program o tuto eventualitu rozšířit. Nejdůležitější částí programu je výstup, který dává přehled o optimálním pořadí zadaných bodů tak, aby trasa, která jimi prochází a vrací se do výchozího místa byla tou nejkratší. Proto jsem věnoval velký význam jednoduchosti a srozumitelnosti finálních výsledků. Matematické výsledky v podobě jedniček a nul jsou transformovány do grafické interpretace bodů očíslovaných v pořadí tvořícím optimální trasu. Navíc se názvy jednotlivých bodů (např. označení pracovišť) vypíší rovněž v pořadí tvořícím optimální trasu. Celou situaci ilustruje obr. 4, na kterém je vidět nejkratší spojnice osmi bodů. Tyto představují sklad, ze kterého je třeba vyjet vynásobit 7 pracovišť a do skladu se opět vrátit. Z bodu, který má být navštíven jako osmý a tedy poslední se okruh uzavírá přesunem do bodu 1. Obr. 4: Výsledná trasa
Zdroj: Vlastní – Program Edita 4
2.1
FUNGOVÁNÍ PROGRAMU
Samotný výpočet probíhá vždy pro 10 bodů a principu zobecnění pro nižší počty bodů jsem docílil pomocí zavádění tzv. fiktivních bodů, které stojí na místě nezadaných bodů. Pokud je zadáno např. pouze 8 bodů znamená to, že se automaticky nastaví 2 fiktivní body, takže celkový počet bodů je vždy 10. Na myšlenku fiktivního bodu mě přivedla možnost místa např. města nebo pracoviště, které by vedle skutečného bodu obsahovalo ještě jeden nebo více fiktivních bodů. Fiktivní bod nebo body se směrem ke zbývající množině bodů chová stejně jako bod č. 1 jak popisuje obrázek č. 5. Celkový počet bodů se tak redukuje, ale výsledek bude stejný, jako v případě, kdyby byl celý výpočet přestavěn např. na zmiňovaných 8 bodů. Obr. 5: Princip fiktivních bodů
Zdroj: Vlastní – Program Edita 4 Fiktivní body ,,a“ a ,,b“ tvoří s bodem č. 1 ,,shluk“ chovající se jako jediný bod a z toho vyplívají vlastnosti popsané tabulkou vedle obrázku 5: 1.) Vzdálenost fiktivního bodu a bodu, se kterým je sloučen je nulová. 2.) Vzdálenosti dvou fiktivních bodů je nulová. Neboť v obou případech se jedná o integraci do jediného bodu. 3.) Vzdálenost fiktivního bodu od okolního bodu je stejná jako vzdálenost tohoto bodu a bodu, se kterým tvoří pomyslný shluk. Na tomto principu je postaveno řešení problému pro jakýkoliv počet bodů menší rovno 10 s výpočetním aparátem stavěným na přesně deset bodů. Samozřejmě po nalezení optimální trasy je třeba fiktivní body z této trasy vyloučit, což je úprava zápisu nikoliv samotné trasy ani její délky, neboť vzdálenost mezi bodem a fiktivním bodem je nulová. Vyloučení těchto bodů je provedeno kombinací logických a vyhledávacích funkcí programu MS Excel, tak aby výstup představoval opravdovou trasu. Obr. 4 ilustruje výstup s osmi body a je vidět, že tabulka, ve které jsou vypsány názvy bodů – pracoviště a sklad má ve spodní části ještě místo pro případ, že výsledná trasa bude obsahovat všech 10 bodů. Po zadání vstupních hodnot jsou k dispozici souřadnice bodů, ze kterých se snadno pomocí Pythagorovi věty určí vzájemné vzdálenosti všech bodů. Tyto hodnoty potom slouží jako vstupní hodnoty pro výpočet, který převede celou situaci (množina bodů, každý smí být navštíven právě jednou, návrat do výchozího bodu) na matematický model. Ten je následně matematickými operacemi řešen. Výsledná trasa má podobu nul a jedniček. Tento výsledek je následně transformován do komfortnější podoby jak ukazoval obr. 4. Prvním krokem k matematickému popsání situace je označení všech možných spojnic bodů pomocí proměnných viz obr. 6. Pokud výsledná cesta vede např. z bodu 1 do bodu 2 hodnota proměnné X1_2 = 1, v opačném případě je hodnota X1_2 = 0. Proměnná X2_1 označuje tutéž spojnici ovšem v opačném směru. Tím je přesně určen systém značení trasy a jde o to hledat hodnoty jednotlivých proměnných. Obr. 6: Systém značení cest mezi body
Zdroj: Vlastní
Obecný tvar matematického modelu řešící Úlohu obchodního cestujícího je dán vztahy 5 až 8, jak uvádí např. ([3], s. 23 – 24). n
n
F=∑
∑ c ⋅x
i =1
j =1
ij
ij
= min .
(5)
Vzorec 5 představuje účelovou funkci vyjadřující délku výsledné trasy, při matematickém řešení problému se hledají takové hodnoty proměnných, aby délka trasy byla minimální (min. této fce.). Koeficient c12 představuje vzdálenost mezi bodem 1 a 2 např. 101 km, pokud hodnota X1_2 vyjde 1 vzdálenost 101 km bude započítána do výsledné trasy, pokud tato hodnota vyjde nula vzdálenost se nezapočítá (101 • 0 = 0). Tímto způsobem jsou zaznamenány všechny vzdálenosti na množině bodů. n
∑ x
ij
i =1
= 1, i = 1,2, ... n
(6)
Vzorec 6 je matematickou interpretací podmínky říkající, že cestující smí z každého uzlu právě jednou vyjet. n
∑ x j =1
ij
= 1,
j = 1,2, ... n
(7)
Vzorec 7 představuje podmínku, že cestující smí do každého bodu právě jednou přijet.
δ i −δ j + n ⋅ x
ij
≤ n − 1,
(8)
i = 1,2,...n j = 1,2,...n Vzorec 8 zabezpečí, že výsledná trasa bude tvořit souvislý okruh. Jak bylo výše zmíněno, každá neznámá může nabývat pouze hodnot 0 nebo 1. Nyní jde o to hledat hodnoty proměnných tak, aby účelová funkce vyjadřující délku výsledné trasy byla minimální (hledá se extrém této funkce.) a přitom musí být dodrženy veškeré další podmínky ze vzorců 6, 7 a 8. Celý matematický zápis situace obsahuje pro 10 bodů 92 rovnic a nerovnic, ve kterých vystupuje 99 neznámých. Nyní ovšem stojíme před problémem matematického výpočtu všech proměnných. Jedná se o hledání vázaného extrému, což situaci komplikuje a nelze použít výpočet pomocí derivací. Jedním z možných východisek je matematická aplikace lineární programování, jde o algoritmus, který v konečném počtu kroků nalezne hodnoty proměnných tohoto matematického zápisu. Jak popisuje ([3], s. 109), MS Excel je vybaven nástrojem řešitel, který umí úlohy Lineárního programování řešit a hlavně dokáže řešit řadu jejich modifikací, z nichž zde použijeme bivalentní lineární programování což je výpočet s ohledem na podmínku, že výsledná hodnota může být pouze nula nebo jedna. Aby bylo možné nástroj bivalentní lineární programování použít je třeba přepsat vztahy 5 až 8 do tvaru, se kterým bude Excel umět pracovat. Jedná se o obdobu normovaného tvaru při používání simplexové metody u jednodušších úloh klasického lineárního programování. Po té co tento nástroj vypočítá hodnoty proměnných do předem nastavených buněk, je třeba provést zaokrouhlení. Hodnoty totiž nemusí být zcela přesné a např. hodnota 0 může být ve skutečnosti hodnotou 0,000000002, což by narušilo fungování logických funkcí programu Excel typu: když je hodnota výsledné buňky větší než nula přiřaď hodnotu 1. Kombinací řady zejména logických a vyhledávacích funkcí je přes řadu pomocných hodnot a mezi výpočtů dosaženo výpisu výsledné trasy. V programu omezeném na 10 míst funguje tento výpočet bez problémů. Ovšem s rostoucím počtem míst prudce roste počet proměnných i počet omezujících podmínek tj. rovnic a nerovnic. Nástroj programu MS Excel dokáže řešit úlohu Lineárního programování maximálně pro 200 neznámých, pro zajímavost matematický zápis tohoto problému hledající trasu pro 13 míst obsahuje 198 neznámých. Za prudkým nárůstem proměnných stojí podmínka popsaná vzorci 8, kde se navíc zavádí vazby mezi pomocnými proměnnými ui a uj.
Tomuto problému se věnuji dlouhodobě a poprvé jsem tento výpočet naprogramoval, aby řešil problém s deseti body, ale jejich počet byl neměnný. Čili jedinou jeho předností byla možnost zadávat libovolné vzdálenosti mezi jednotlivými body. Pro jiný problém nebylo nutné psát a programovat rovnice, ale počet bodů mohl být pouze 10. Tento program jsem nazval Edita 1. Program Edita 2 dokázal pomocí výše popsaného principu fiktivních bodů plánovat trasu pro počet bodů 1 až 10. Dalším postupem bylo zvýšení horní hranice bodů, pro které je trasa plánována na 13, což odpovídá zmíněným 198 proměnným a tím se možnosti řešení v prostředí MS Excel vyčerpávají. Tento program jsem nazval Edita 3, ovšem pro praktické použití se příliš nehodí, protože hledání takového počtu hodnot proměnných se obvykle pohybovalo v čase převyšujícím hodinu. Přitom pro 10 míst se doba řešení pohybovala okolo dvou minut. Jako velká překážko pro efektivní využití tohoto programu jako praktický nástroj se ukázala nutnost zjišťování nebo dopočítání a zdlouhavého zadávání vzájemných vzdáleností mezi jednotlivými body. Edita 4 je vlastně vylepšeným programem Edita 2 o automatický dopočet požadovaných vzdáleností ze zadaných bodů. Zadat 10 bodů je mnohem jednoduší než zadávat všechny vzájemné vzdálenosti mezi deseti body. Další cíle spočívají mimo jiné v hledání metod dávajících přibližná řešení (suboptimální trasy) pro více než 13 bodů při rozumném čase potřebném k řešení.
ZÁVĚR V příspěvku jsem se snažil představit program Edita 4, který je schopný určit optimální pořadí množiny míst s ohledem na jejich nejkratší možnou trasu, která začíná i končí v bodu 1. Také jsem, alespoň průřezově pojednal o principech, na kterých funguje. Praktické využití tohoto nástroje lze nalézt při řešení logistických problémů typu rozvoz zboží, svoz odpadů, návštěva a kontrola poboček apod. Stejně tak dobře je možné pomocí tohoto nástroje řešit úlohy vnitropodnikové logistiky jako zásobování jednotlivých nepravidelně rozmístěných pracovišť komponenty. Výhodou je, že při změně pracoviště nebo pobočky na plánované trase lze tento bod snadno předefinovat a vypočítat novou optimální trasu. Celý program je sestaven v rozšířeném a snadno dostupném prostředí MS Excel, čili není spojen se softwarovými a hardwarovými nároky a více náklady (každý si ho může okamžitě pustit v kanceláři). Stejně tak je koncipován se snahou o co nejjednodušší obsluhu a právě velice zjednodušené ovládání ho odlišuje od svých předchůdců Edita 2 a Edita 3. Tento příspěvek vznikl za podpory grantu SGS s názvem: Optimalizační algoritmy rozvrhování strojírenské výroby, číslo SGS13/191/OHK2/3T/12, ČVUT v Praze, Fakulta strojní.
LITERATURA [1] [2] [3] [4]
COOK, W., J. Po stopách obchodního cestujícího. Matematika na hranicích možností. 1. vyd. Praha: Dokořán, 2012. ISBN 978-80-7363-412-4. CRILLY, T. Matematika 50 myšlenek, které musíte znát. 1. vyd. Praha: Slovart, 2010. ISBN 97880-7391-409-7. JABLONSKÝ, J.: Programy pro matematické modelování. 1. vyd. Praha: VŠE, 2007. ISBN 97880-245-1178-8 TESAŘÍK B. Matematikou k milionům aneb Po stopách obchodního cestujícího. Technický týdeník, 2013, roč. 61, č. 19, s. 8. ISSN 004-1064
Adresa autora: Ing. Josef Košťálek, ČVUT v Praze, Fakulta strojní, Ústav řízení a ekonomiky ústavu,
[email protected]
PROGRAM FOR EASY SOLUTION TRAVELING SALESMAN PROBLEM WITH TEN POINTS AND ITS USE Abstract My paper describes the program Edita 4, which can give a solution for Traveling salesman problem with 10 points. Traveling salesman problem is name of very important and very dificult mathematical problem and its solution is an optimal route among some points. In this program the situation is
overwritten on a mathematical model that is mathematically solved using linear programming algorithm with bivalent values. The resulting values are transformed to a result which is plotting points and marking the correct order. The practical use of this tool can be found in solving logistical problems such as goods delivery, waste collection, visit and inspection offices, supply individual components irregularly spaced sites etc.
Key words Traveling salesman problem, optimal route, algorithms, binary linear programming, input values, output values.
JEL Classification C610
