Skip to main content

Login for students

Login for employees

Publication detail

Metodika řešení svozně-rozvozných úloh s obsluhou hran - heuristický přístup
Authors: Vízner Filip
Year: 2009
Type of publication: článek ve sborníku
Name of source: Úlohy diskrétní optimalizace v dopravní praxi : Telematika v distribučních a svozných úlohách
Publisher name: Univerzita Pardubice
Place: Pardubice
Page from-to: 105-117
Titles:
Language Name Abstract Keywords
cze Metodika řešení svozně-rozvozných úloh s obsluhou hran - heuristický přístup Tento článek popisuje základní metody řešení svozně-rozvozných úloh s obsluhou hran, dále jen SRÚOH. Mezi SRÚOH patří např. svoz komunálního odpadu, údržba komunikací, rozvoz zboží, doručování pošty atd. Problém spočívá v nalezení tahu, resp. sledu, optimální délky na grafu sítě tak, aby došlo k obsloužení všech požadovaných hran, přičemž tah by měl začínat a končit v témže vrcholu. Obecně z heuristického hlediska se tento problém řeší nalezením Eulerovského tahu na upraveném grafu. Výsledné řešení nebývá optimální, proto se používají další subheuristiky na jeho vylepšení. V tomto článku je celý postup popsán. Tento problém je možno řešit i pomocí metod lineárního programování, s tím, že se snažíme minimalizovat počet dodatečně přidaných hran do grafu, aby bylo možné provézt Eulerovský tah. UCARP, URPP, ARP
eng