Obchodný cestujúci - 2.diel

Úvod

Tento článok je venovaný súhrnu, výskumu problému obchodného cestujúceho. V článku nájdete originálne riešenie tohto problému. Metódu popísanú v článku nie je možné kopírovať a vydávať za svoj vlastný nápad, bez odkazu na originálny článok. Túto metódu je možné naprogramovať, pre efektívne hľadanie optimálnej cesty. Problém obchodného cestujúceho má široké uplatnenie v doprave a v priemysle (napr. CNC stroje). Riešenie ponúka široké uplatnenie v rôznych oblastiach. Výsledkom je úspora času a financií. V dnešnej dobe existujú rôzne algoritmy na riešenie obchodného cestujúceho, ale vždy ich efektivita výrazne klesá s pribúdajúcim počtom bodov/uzlov.

Zhrnutie užitočných vlastnosti

1. B/E, Begin – End si je možné zvoliť ľubovoľne, pretože trajektória je uzavretá. Čo znamená, že v podstate jedno odkiaľ začíname.

2. Veľkosť optimálnej dráhy, teda približnej dráhy pre kontrolu výsledku vypočítame, podľa Problém obchodný cestujúci – I. Diel.

3. Každý uzol má minimálne dve spojnice, kde spája predchádzajúci uzol a nasledujúci uzol.

4. Aby sme dosiahli, čo najkratšiu dráhu musíme minimalizovať uzly, ktoré majú viac ako dve spojnice.

5. Ak chceme mať, čo najkratšiu dráhu nesmieme trasy krížiť, iba výnimočné, ak to nie je možné urobiť inak, neexistuje iná alternatíva.

6. Musíme maximalizovať taký druh spojníc uzlov, ktoré sú najkratšie pre každé okolie i-teho uzla. Teda musíme mať, čo najkratšie spojnice medzi uzlami, aby sme minimalizovali celkovú trasu.

Systémové riešenie problému obchodného cestujúceho

A, Obvodová technika

V prípade, že je uzlov malo, dostatočne od seba vzdialených je možné použiť obvodovú techniku. viď. obrázok č.13, č.14, komentovať to netreba ide o jednoduchú vlastnosť. Dráha tvorí uzavretú krivku. Základ tejto metódy je ten, že hľadáme obvodovú krivku s čo najmenšou veľkosťou. Pri tejto metóde musíme využiť kombinačné schopnosti počítačov. Jednoduché použitie ukazuje obrázok č. 13 a obr. 14.

Obr. 13 Príklad jednoduchej obvodovej techniky, zdroj: vlastný obrázok.

Obr. 14 Príklad jednoduchej obvodovej techniky, zdroj: vlastný obrázok.

B) Metóda Zig - Zag, Cik - Cak

1. Rolovanie cik - cak -vodorovne.
2. Rolovanie cik - cak - zvislo.
3. Rolovanie cik- cak - kombinované.

Na obrázkoch je technika, ako postupovať systematicky v spájaní uzlov. Voľba cik - caku závisí hlavne od toho, ako sú rozmiestnené uzly. Pokiaľ napríklad sú vodorovné vzdialenosti medzi susednými uzlami menšie ako zvislé, volíme vodorovný cik- cak. V prípade, že je to naopak volíme zvislý cik – cak. Pokiaľ sa to, ale mení miesto od miesta použijeme kombinovaný cik cak. Zelenou farbou je nakreslená obvodová technika s ktorou sa dostaneme: od Begin (je najnižší uzol naľavo) na najvrchnejší uzol napravo. Od tohto miesta volíme konkrétnu metódu cik – cak.

Príklady pre lepšie pochopenie

1. Symetricky rozmiestnené uzly.
2. Asymetricky rozmiestené uzly.

Na obrázku č.18 je použitý vodorovný cik - cak. Zelená čiara predstavuje obvodovú techniku, kde sme sa od začiatku B (begin) dostali na najvrchnejší uzol. Všimneme si, že to nie je priama čiara, ale tvorí kľukatú čiaru, pretože vzdialenosti sú po tejto kľukatej dráhe menšie medzi uzlami. Samozrejme v tomto prípade sme mohli zvoliť aj zvislý cik - cak, či kombinovaný.

Príklad asymetricky rozmiestených uzlov:

Obr. 19 Obvodová technika, asymetrické uzly, zdroj: Vlastný obrázok.

Na obrázku č. 19 je použitá len obvodová technika (obvodový cik - cak), pre nedostatok uzlov vnútorný cik - cak nebol použitý.

Obr. 20 Kombinovaný cik- cak, zdroj: vlastný obrázok.

Na obrázku č.20  sú rozmiestnené uzly s rôznou dĺžkou medzi sebou, použili sme obvodovú techniku nakreslené zelenou, hrubou čiarou a kombinovaný cik - cak. V tomto prípade, už bolo nutné použiť kombinovaný cik - cak, pretože vzdialenosti medzi uzlami sa menili. Je tu nakreslené len jedno riešenie, ale riešení je viac. Všimnime si 4 ostrovčeky uzlov v rohoch. Pokiaľ by napríklad boli vzdialené od stredu ostrova uzlov viac, potom riešime každý ostrov uzlov samostatne. Pre dopravu, kde je napríklad diaľnica medzi mestami sa potom môže stať, že sa vraciame po tej istej dráhe späť. V tomto prípade však lepšie riešenie, kratšie je pospájané na obrázku. Samozrejme pri počítači sa bude dať nájsť aj kratšie riešenie (vďaka kombináciám, ktoré môže preveriť).

Obr. 21 Kombinovaný cik - cak, zdroj: vlastný obrázok.

Príklad - asymetrické uzly - metóda kombinovaný cik - cak. Z B=E v ľavom dolnom rohu sme sa cez obvodovú techniku (obvodový cik - cak) dostali do pravého, horného rohu, odkiaľ je použitý vnútorný, kombinovaný cik - cak.

Obr. 22 Kombinovaný cik- cak, zdroj: vlastný obrázok.

Príklad - asymetrické uzly - metóda kombinovaný cik - cak. Z B=E v ľavom dolnom rohu sme sa cez obvodovú techniku (obvodový cik - cak) dostali do pravého, horného rohu, odkiaľ je použitý vnútorný, kombinovaný cik - cak, nosné rolovanie je vodorovný cik - cak. Toto je rýchly nástrel riešenia človekom, pričom ide už o zložitý problém.

Príklady Mapy - vzdušná čiara, obvodová technika + obvodový cik- cak, malá množina na vnútorné cik- caky.

Obr. 23 Obvodový cik- cak Afrika, zdroj: vlastný obrázok.

Toto je ukážka obvodovej techniky vytvorená človekom. Pričom nie je použitý vnútorný cik - cak, pretože obsahuje málo bodov, body sa koncentrujú po obvode.

Dôkaz správnosti systémového riešenia

Ten dôkaz je prostý a jednoduchý. V každom tu uvedenom riešení príkladu sú dodržané metódy z kapitoly: Užitočné vlastnosti (viď. vyššie). Trasy sú blízke optimu, pretože sme dodržali a splnili všetky dôležité zistenia. Pre počítač, ak má systémové riešenie implementované je maličkosť optimalizovať tie dráhy do, čo najkratšej. Zároveň táto metóda ukazuje silu pri veľmi veľkom počte uzlov.

TSP Solver

TSP Solver je program určený na hľadanie optimálnej trasy tzv. problému obchodného cestujúceho (TSP- Travelling Salesman Problem). TSP Solver je program napísaný v jazyku Python. TSP je známy kombinatorický problém, ktorý sa snaží nájsť najkratšiu možnú cestu, ktorú by mal prejsť obchodný cestujúci, keď navštívi určený počet miest a vráti sa späť do východzieho bodu.

Problém obchodného cestujúceho má široké uplatnenie v rôznych oblastiach, vrátane dopravy, logistiky, výroby a optimalizácie trás. Jeho výskyt sa dá vysledovať až do 18. storočia, keď bol prvýkrát formulovaný matematikmi a počítačovými vedcami. Odvtedy sa stal výzvou pre mnohých výskumníkov a programátorov, ktorí sa snažia nájsť efektívne algoritmy a riešenia.

TSP Solver je nástroj, ktorý môže byť využitý v rôznych odvetviach a aplikáciách, kde je potrebné optimalizovať trasu. Pomocou tohto programu je možné nájsť efektívne riešenia pre problém obchodného cestujúceho a zlepšiť tak výkonnosť a efektivitu rôznych procesov a aktivít, ktoré vyžadujú šetrenie energie a času pre výrobu produktov, v doprave a pod. Napríklad, môže pomôcť znížiť výrobné náklady, ak sa stanoví najefektívnejší model pre dierovanie otvorov do dosky plošných spojov alebo iných predmetov.

• Program ponúka množstvo užitočných funkcii.
• Program nájde trasu rýchlo aj pre veľký počet bodov.
  
• Program využije každý cestovateľ, firma kde výrobný proces ušetrí čas a náklady v čo najkratšej trase výrobného postupu.

Záver

Publikácia venovaná optimalizácii metódy najbližšieho suseda nájdete :

odkaz: https://robopol.sk/blog/vylep%C5%A1enie-metody-najblizsieho-suseda-tsp-problem