Matematické Fórum

Zdravím všechny,

protože jsem si nebyl jistý, kam umístit můj dotaz, dle nápovědy jej směřuji sem. Můj problém se týká skutečné situace z praxe, nicméně vyřešit jej může zřejmě jen matematik.



Představte si, že máte zajistit autobusové spojení mezi třemi obcemi A, B a C. Vzdálenosti obcí jsou uvedeny černě na obrázku, autobus tyto vzdálenosti urazí za dobu označenou zeleně (s indexem C). Autobusové spoje mají na konečných zastávkách minimální obratový čas (na obrázku zeleně s indexem O), který musí být dodržen. Vzhledem k tomu, že poptávka po spojích není pravidelná, mohou autobusy vykonávat i režijní jízdy - přejezdy mezi konečnými bez cestujících (na obrázku červeně s indexem T). Přejezd je včetně obratových časů.

Jsou dány tyto spoje (číslo spoje: čas odjezdu (z obce) -> čas příjezdu (do obce)):

S1:    8:00 (A) -> 8:20 (B)
S2:    8:03 (B) -> 8:23 (A)
S3:    8:30 (A) -> 8:50 (B)
S4:    8:32 (B) -> 8:52 (A)
S5:    9:02 (B) -> 9:16 (C)
S6:    9:02 (A) -> 9:22 (B)
S7:    9:26 (A) -> 9:42 (C)
S8:    9:32 (C) -> 9:48 (A)
S9:    9:49 (C) -> 10:05 (A)
S10:    9:53 (A) -> 10:13 (B)
S11:    10:15 (C) -> 10:31 (A)
S12:    10:21 (B) -> 10:35 (C)
S13:    10:43 (B) -> 10:53 (A)
S14:    10:47 (A) -> 11:07 (B)
S15:    11:19 (A) -> 11:37 (C)

Podmínky jsou tyto:
- Obratový čas může být delší než je zadaná hodnota (řidič může na konečné déle čekat).
- Spoj S(i) začínající na konečné, kde skončil spoj S(i-1), nesmí odjet dřív než přijel spoj S(i).
- Pokud spoj S(i) začínající na konečné, kde skončil spoj S(i-1), má odjezd dřívější než příjezd, musí být nasazen další autobus (-> nový turnus).
- Spoj S(i+1) může začínat na jiné konečné, než kde skončil spoj S(i). Podmínkou je, že čekání na konečné musí být delší než přejezd mezi konečnými.

Výsledkem by měl být určitý počet turnusů T, přičemž každý turnus obsahuje posloupnost spojů, např. T1: S1 -> S4 -> S8 -> S14 -> S15 i s přejezdy. Z toho vyplývá, že každý spoj musí mít svého předchůdce (kromě prvního) a svého následovníka (kromě posledního).

Tyto spoje by měly zajišťovat dva autobusy (čili dva turnusy), protože jsem celou úlohu naplánoval odzadu a mým cílem je se k tomuto výsledku nějakým logickým a početním způsobem dopracovat. Z uvedeného seznamu spojů za zadaných podmínek bych chtěl obdržet posloupnost spojů. V praxi by to fungovalo tak, že si z internetu vytáhnu všechny spoje (kde jsou známé konečné i časové polohy, přejezdy mezi konečnými se dají dopočítat), které jsou provozované v jednom určitém dni, a program by mi z těchto spojů měl složit nejmenší potřebný počet turnusů. Z toho by logicky měla vyplynout i finanční úspora na počtu využitých autobusů. Vzhledem k tomu, že v některá velká města provozují i více než 1500 spojů, je v matici 2,25 milionu buněk, na což už je potřeba sofistikovanější program.

Nějaká řešení jsem už zkoušel. Napadla mě maďarská metoda, všechno jsem si uspořádal do matice a posuzoval vzájemné kombinace. Jenže jsem vyhořel na tom, že Řešitel v Excelu nedokázal pracovat s 289 měněnými buňkami a jiný software na řešení velkých matic jsem bohužel nenašel. Bohužel nerozumím matematice tolik, abych úlohu vyřešil sám. V některých metodách jen zhruba orientuju, ale doposud jsem na nic rozumného nepřišel.

Děkuji Vám všem za odpovědi a pokud by někdo byl z Prahy nebo Brna, nebráním se případné osobní konzultaci.