V prvej časti článku sme sa venovali problému plánovania verejnej dopravy všeobecne, pričom sme tento problem rozdelili na niekoľko podproblémov. Matematicky sme si popísali daný problém a navrhli sme heuristickú metódiu deň-za-dňom. V tejto časti si popíšeme inferenčný mechanizmus pre fuzzy systém, ukážeme si ako problém spracovať pomocou jazyka Phyton a uvedieme dosiahnuté výsledky.

4. Fuzzifikovaná metóda rozpisovania služieb v aktuálny den

Fuzzifikovaná metóda rozpisovania služieb v aktuálny deň (druhý krok algoritmu deň-za-dňom) je postup, ktorý rieši problém priraďovania turnusov T_k ∈ T vodičom V_i ∈ V v aktuálny deň s ∈ D, pomocou aparátu teórie fuzzy množín, fuzzy logiky a inferencie, pričom nedôjde porušeniu žiadnej ťažkej podmienky počas optimalizovania ľahkých podmienok vzhľadom na minulé rozhodnutia R (rozpis služieb v predošlých dňoch). Tieto ťažké a ľahké podmienky, parametre alebo pracovné časy môžu byť interpretované neisto.

V našom prípade je neisté samotné prideľovanie turnusov vodičom v aktuálny deň. Heuristická metóda deň-za-dňom neuvažuje s následkami rozhodnutí, ktoré vznikajú pri rozpisovaní služieb v aktuálny deň. Tento nedostatok metódy vniesol do rozhodnutí, ktorý turnus priradiť ktorému vodičovi, vágnosť. Na riešenie takto zadefinovaného problému, ktorý nie je komplexný, použijeme fuzzy inferenčný systém a polynomiálny algoritmus lineárneho zmiešaného celočísleného matematického programovania, tiež známeho pod menom priraďovacia úloha.

Priraďovacia úloha pozostáva z účelovej funkcie, ktorá je tvorená sumou cien, na základe vykonaných rozhodnutí, ktoré sú binárneho charakteru, respektíve typu priraď alebo nepriraď turnus vodičovi. Tieto ceny (indexy preferencie) spočítame pomocou fuzzy inferenčného systému na základe znalostnej bázy tvorcu rozpisu služieb. Čím vyššia je je hodnota indexu preferencie, tým sme viac presvedčený o tom, že vodič dostane pridelený uvažovaný turnus. To ale platí za predpokladu, že účelovú funkciu maximalizujeme. Ďalej zovšeobecnená priraďovacia úloha pozostáva z niekoľkých obmedzení typu práve jeden a/alebo nanajvýš jeden. Tieto obmedzenia predstavujú niektoré ťažké podmienky, spomínané v úvode článku.

Fuzzy inferenčný systém (FIS) je známi pod menami ako „fuzzy znalostný systém“, „fuzzy expertný systém“ [15], [16], [17]. FIS je časťou fuzzy logických systémov. FIS pozostáva z rozhrania fuzzifikácie, bázy pravidiel, bázy dát (databázy), rozodovacej jednotky a nakoniec s deffuzifikačného rozhrania. Fuzzy inferenčný systém s piatimi funkčnými blokmi je popísaný na obrázku 2.

Nech s-ty deň mesiaca (1 ≤ s ≤ 28) je aktuálnym dňom. Keďže dodržiavame algoritmus deň-za-dňom, i-ty vodič už má priradené turnusy, ktoré začínajú prvý, druhý a (s − 1) deň. Túto informáciu vieme vyčítať z existujúceho rozpisu služieb R. Predpokladajme, že by i-ty vodič mal dostať pridelený l-ty turnus, ktorý začína v s-tý deň.

Obr. 2: Fuzzy inferenčný systém (FIS)

Celkový naakumulovaný denný pracovný čas i-teho vodiča po koniec (s − 1) dňa spočítame ako:

, pre ∀(V_i,T_l)∈V×T.

Ideálny denný pracovný čas i-teho vodiča po koniec dňa s je:

, pre ∀V_i ∈V.

Aby sme mohli navrhnúť fuzzy lingvistické hodnoty fuzzy premennej D, potrebujeme poznať rozsah univerzálnej množiny U = [min^D(s),max^D(s)]. Z prvej definície miery nerovnomernosti vyplýva, že minimálna hodnota, ktorú môže miera nerovnomernosti kumulovaných pracovných časov nadobudnúť je

pre ∀s ∈ D

Nech c_max(s) je doba najdlhšie trvajúceho turnusu, ktorý môže byť odpracovaný v s-ty deň. Jej hodnotu spočítame ako:

, pre ∀s ∈ D.

Nech C = (c_ij×n, potom prvky matice spočítame ako

Nech π = (π₁,π₂,…,π_n) je usporiadaná n-tica permutácií množiny V a Π je množina všetkých permutácií π. Nech C^π je permutačná matica, ktorej element v i-tom riadku a j-tom stĺpci je c_πj(i),j. Nech ψ ∈ Π je n-tica permutácií, pre ktorú platí:

, pre ∀j ∈ D.

Nech je stredná (ideálna) hodnota riadkových súčtov po s-tý deň, ktorú spočítame ako:

, pre ∀s∈D.

Potom maximálnu hodnotu miery nerovnomernosti spočítame ako:

, pre ∀s∈D.

Fuzzy lingvistická premenná D vyjadruje mieru nerovnomernosti kumulovaného reálneho denného pracovného času vodičov autobusov, ktorá nadobúda nasledujúce hodnoty:

• VHI – veľmi veľká hodnota miery nerovnomernosti,
• HI – veľká hodnota miery nerovnomernosti,
• MI – stredná hodnota miery nerovnomernosti,
• LI – malá hodnota miery nerovnomernosti,
• VLI – veľmi malá hodnota miery nerovnomernosti.

Na obrázku 3 sú zobrazené jednotlivé funkcie členstva k predošlým fuzzy množinám.

Obr. 3: Funkcie členstva fuzzy množín VHI, HI, MI, LI, VLI

Prvou vstupnou hodnotou fuzzy inferenčného systému je hodnota štvorca rozdielu kumulovaného reálneho a ideálneho denného pracovného času i-teho vodiča spolu s l-tým kandidátom na priradenie po koniec s-teho dňa:

, pre ∀(V_i,T_l)∈V×T.

Pre tvorcu rozpisu služieb je hodnota d_il(s,R) veľmi dôležitá. Hovorí mu, či má alebo nemá priradiť i-temu vodičovi l-tý turnus v s-tý deň. Čím je hodnota d_il(s,R) bližšie k nule, tým je väčšie uprednostnenie tvorcu rozpisu služieb, aby priradil i-temu vodičovi l-tý turnus na začiatku s-tého dňa.

Teraz chcem navrhnúť fuzzy lingvistické hodnoty fuzzy premennej F. Nech je minimálna hodnota kumulovanej frekvencie rovnakých l-tych turnusov u i-teho vodiča v s-tý deň. Jej hodnotu spočítame ako:

, pre ∀(V_i,T_l)∈V×T.

Nech e_il^*(s) je ideálna kumulovaná frekvencia rovnakých l-tych turnusov u i-teho vodiča v s-tý deň, ktorú zapíšeme ako:

, pre ∀(V_i,T_l)∈V×T.

Nech je maximálna hodnota kumulovanej frekvencie rovnakých l-tych turnusov v s-tý deň, ktorú zapisujeme ako:

, pre ∀(V_i,T_l)∈V×T.

Teraz navrhneme rozsah hodnôt univerzálnej množiny V = [min^F(s), max^F(s)] fuzzy lingvistickej premennej F. Minimálna hodnota, ktorú môže miera nerovnomernosti kumulovaných frekvencií rovnakých turnusov nadobudnúť je:

, pre ∀s ∈ D

Maximálna hodnota, ktorú môže miera nerovnomernosti kumulovaných frekvencií rovnakých turnusov nadobudnúť je:

, pre ∀s ∈ D

Nech F je fuzzy lingvistická premenná vyjadrujúca mieru nerovnomernosti kumulovanej reálnej frekvencie, ktorá nadobúda nasledujúce hodnoty:

• VHF – veľmi veľká hodnota miery nerovnomernosti,
• HF – veľká hodnota miery nerovnomernosti,
• MF – stredná hodnota miery nerovnomernosti,
• LF – malá hodnota miery nerovnomernosti,
• VLF – veľmi malá hodnota miery nerovnomernosti.

Na obrázku 4 sú zobrazené jednotlivé funkcie členstva k predošlým fuzzy množinám.

Obr. 4: Funkcie členstva fuzzy množín VHF, HF, MF, LF, VLF

Nech e_il(s,R) je celková naakumulovaná frekvencia i-teho vodiča spolu s l-tým kandidátom na priradenie po koniec s-tého aktuálneho dňa:

Druhou dôležitou vstupnou hodnotou fuzzy inferenčného systému je hodnota štvorca rozdielu kumulovanej reálnej a ideálnej frekvencie i-teho vodiča spolu s l-tým kandidátom na priradenie po koniec s-teho dňa:

, pre ∀(V_i, T_l) ∈ V × T .

Čím je hodnota väčšia, tým je tvorca rozpisu služieb presvedčenejší o tom, aby priradil i-temu vodičovi l-tý turnus na začiatku s-tého dňa.

Rozsah univerzálnej množiny fuzzy lingvistických premenných D a F je de-
finovaný vzhľadom na aktuálny deň heuristickej metódy day-by-day.

Výstupnou hodnotou fuzzy inferenčného systému je index preferencie p_il(s, R), ktorý vyjadruje uprednostňovanie tvorcu rozvrhu, či priradí i-temu vodičovi l-ty turnus, ktorý začína v s-tý deň. Nech 0 ≤ p_il(s,R) ≤ 100, V_i ∈ V,T_l ∈ T,s ∈ D. Čím je index uprednostnenia väčší, tým je tvorca rozpisu služieb presvedčenejší, že dôjde k priraďovaniu nad uvažovanými vodičmi a turnusmi v aktuálny deň.

Nech P je fuzzy lingvistická premenná vyjadrujúca silu uprednostňovania (preferencie) tvorcu rozpisu služieb, ktorá nadobúda nasledujúce hodnoty:

• VLP – veľmi slabé uprednostňovanie,
• LP – slabé uprednostňovanie,
• MP – stredne silné uprednostňovanie,
• HP – silné uprednostňovanie,
• VHP – veľmi silné uprednostňovanie.

Na obrázku 5 sú zobrazené jednotlivé funkcie členstva fuzzy množín popisujúcich silu uprednostňovania tvorcu rozpisu služieb. Fuzzy lingvistické premenne D, F a P môžeme vo fuzzy inferenčnom systéme nájsť uložené v bloku bázy dát.

Obr. 5: Funkcie členstva fuzzy množín VLP, LP, MP, HP, VHP určujúce index preferencie

Zadefinujme teraz bázu pravidiel. Nech s je aktuálny deň, nech R je rozpis služieb. Zjednodušene zapíšeme výkon vodičov a frekvenciu turnusov ako x₁ = d_il(s, R) a x₂ = f_il(s, R). Ďalej notáciu indexu preferencie zjednodušíme na y = p_il(s,R).

---

Báza pravidiel

• R1: IF x₁ is VLI AND x₂ is {VLF,LF,MF,HF,VHF} THEN y is VLP
• R2: IF (x₁ is VHI AND x₂ is VLF) OR (x₁ is HI AND x₂ is VLF) OR (x₁ is MI AND x₂ is VLF) OR (x₁ is LI AND x₂ is {VLF,LF,MF,HF,VHF}) THEN y is LP
• R3: IF (x₁ is VHI AND x₂ is LF) OR (x₁ is HI AND x₂ is LF) OR (x₁ is MI AND x₂ is {LF,MF,HF,VHF}) THEN y is MP
• R4:IF (x₁ is VHI AND x₂ is MF) OR (x₁ is HI AND x₂ is {MF,HF,VHF}) THEN y is HP
• R5: IF (x₁ is VHI AND x₂ is {HF,VHF}) THEN y is VHP

---

Výstupnou hodnotou fuzzy inferenčného systému je ostrá hodnota y. Defuzzifikáciu robíme pomocou najčastejšie používanej metódy „ťažiska plochy“ (Center of gravity – COG). Teraz vieme spočítať index preferencie pre i-teho vodiča a l-tý turnus.

Obr. 6: Výstupná hodnota fuzzy inferenčného systému

Obrázok 6 zobrazuje výstupnú hodnotu fuzzy inferenčného systému pre kaž- dého vodiča a turnus. V podstate ide o spojité zobrazenie matice P = (p_il)_m×t. Nech R je rozpis služieb, čas ukončenia priradeného turnusu i-teho vodiča v (s − 1)-vý deň vyjadríme ako:

Teraz keď poznáme maticu indexov preferencie, môžeme spočítať pomocou zovšeobecnenej priraďovacej úlohy priradenia turnusov vodičom. Nech s je aktuálnym dňom a r_i = r_i(s−1,R) a nech q_l = w_sl a h_i = v_is a ďalej nech platí, že

ak

S.T.

, T_l∈T,

, V_i∈V,

, (V_i,T_l)∈V×T

Riešením fuzzy metódy rozpisovania služieb v aktuálny deň je optimálny (v
našom prípade skôr vyhovujúci) rozpis služieb pre aktuálny den

, kde (V_i,T_l)∈V×T

Nasledujúca sekcia sa venuje problematike implementovania fuzzifikovanej metódy rozpisovania služieb v aktuálny deň pomocou programovacieho jazyka Python a balíčka pyFuzzy.

5 Implementovanie heuristiky day-by-day

Fuzzifikovaná heuristika je implementovaná v programovacom jazyku Python [18]. Dôvodom jeho výberu je množstvo balíčkov, rýchle prispôsobenie programátora k Pythonu, open source, množstvo dokumentácie a jednoduché paralelne programovanie. V dnešnej dobe existujú pre Python dva balíčky, ktoré implementujú fuzzy množiny a vykonávajú na nich operácie fuzzy logiky. Sú to pyFuzzyLib a pyFuzzy. Balíček pyFuzzy je zvolený z nasledujúcich dôvodov: jednoduché programovanie fuzzy množín a fuzzy pravidiel (v zdrojovom kóde alebo súbor flc); možnosť zobrazovania vstupov a výstupov graficky; možnosť grafického zobrazenia fuzzy pravidiel; množstvo príkladov.

Fuzzy inferenčný systém implementovaný v pyFuzzy je typu MIMO (Multiple Inputs Multiple Outputs). Programátorovi ponúka pyFuzzy veľký výber zo vstupných a výstupných druhov fuzzy čísiel (množín). Ďalej má programátor možnosť výberu z rôznych noriem a konoriem, ktoré môže použiť pri tvorbe pravidiel, agregácií a/alebo konfigurovania defuzzifikácie. V závislosti od ich výberu je programátor schopný vytvoriť rôzne inferenčné metódy (Mamdami, Larsen, [15]). Náš fuzzy inferenčný systém pozostáva z dvoch vstupov, piatich pravidiel a jedného výstupu (MISO – Multiple Inputs Single Output). Nasledujúce kroky vedú k vytvoreniu fuzzy inferenčného systému.

5.1 Vytvorenie fuzzy inferenčného systému

Kód inicializácie systému zapíšeme v Pythone takto:

import fuzzy.System
system = fuzzy.System.System()

Trieda fuzzy.System koordinuje celý fuzzy systém (bázu dát, bázu pravidiel, fuzzifikačné rozhranie, defuzzifikačné rozhranie).

5.2 Definovanie bázy dát fuzzy množín vstupov

Kód definovania bázy dát fuzzy množín vstupov zapíšeme v Pythone takto:

from fuzzy.InputVariable import InputVariable
from fuzzy.Adjective import Adjective
from fuzzy.set.Polygon import Polygon
from fuzzy.set.Triangle import Triangle
from fuzzy.fuzzify.Plain import Plain
h = max_fsqr /6.0
irreg = InputVariable(fuzzify = Plain(), min = 0, max = max_fsqr)
system.variables["irregularity"]=irreg
irreg.adjectives[’VLI’]=Adjective(Polygon([(0.,0.) ,(0.,1.),(h,1.),(2*h,0.)]))
irreg.adjectives[’LI’]=Adjective(Polygon([(h,0.),(2*h,1.),(3*h,0.)]))
irreg.adjectives[’MI’]=Adjective(Polygon([(2*h,0.),(3*h,1.),(4*h,0.)]))
irreg.adjectives[’HI’]=Adjective(Polygon([(3*h,0.),(4*h,1.),(5*h,0.)]))
irreg.adjectives[’VHI’]=Adjective(Polygon([(4*h,0.),(5*h,1.),(6*h,1.),(6*h,0.)]))

Hodnota max_fsqr sa rovná hodnote max^D(s). Podobne píšeme kód aj pre fuzzy premennú „frequency“. Trieda fuzzy.InputVariable implementujúca vstupnú fuzzy premennú, pozostáva z niekoľkých fuzzy hodnôt, ktoré implementuje trieda fuzzy.Adjective. V našom prípade to môže byť napríklad hodnota „VLI“ fuzzy premennej „miera nerovnomernosti kumulovaného reálneho denného pracovného času vodičov autobusov“.

Balík fuzzy.set obsahuje triedy implementujúce fuzzy množiny, ktoré majú napríklad tvar trojuholníka (Triangle()), lichobežníka (Trapez()), ostrej hodnoty (Singleton()), polygónu (Polygon()) a veľa iných. Balík fuzzy.fuzzify pozostáva z tried, ktoré slúžia na určenie stupňa, ktorým jednotlivé vstupy prislúchajú fuzzy množinám definovaných funkciami príslušnosti. Tieto triedy sa starajú o zobrazenie ostrej hodnoty do prislúchajúcej fuzzy množiny.

5.3 Definovanie bázy dát fuzzy množín výstupov

Kód predošlých fuzzy množín výstupu zapíšeme v Pythone takto:

from fuzzy.norm.Min import Min
from fuzzy.norm.Max import Max
from fuzzy.defuzzify.COG import COG
from fuzzy.OutputVariable import OutputVariable
INF, ACC = Min(), Max()
COG = COG(INF=INF, ACC=ACC, failsafe = 0., segment_size=0.5)
pref = OutputVariable(defuzzify = COG, min = 0, max = 100)
system.variables[’preference’] = pref pref.adjectives[’VLP’]=Adjective(Polygon([(0,0),(0,1),(10,1),(30,0)])) pref.adjectives[’LP’]=Adjective(Polygon([(10,0),(30,1),(50,0)])) pref.adjectives[’MP’]=Adjective(Polygon([(30,0),(50,1),(70,0)])) pref.adjectives[’HP’]=Adjective(Polygon([(50,0),(70,1),(90,0)])) pref.adjectives[’VHP’]=Adjective(Polygon([(70,0),(90,1),(100,1),(100,0)]))

Balík fuzzy.norm pozostáva z rôznych t-noriem a t-konoriem, ktoré sú implementované triedami. Napr. operátory maxima, minima, algebraické sčítanie alebo algebraické násobenie. Tieto operátory sa používajú pri vyhodnocovaní pravidiel a pri agregácií, teda zjednotení výstupov každého pravidla. Balík fuzzy.defuzzify pozostáva z niekoľkých tried, ktoré vykonávajú proces defuzzifikácie. Ide o opačný proces k fuzzifikácii, teda triedy zobrazujú fuzzy množiny na ostré hodnoty. Najznámejšie sú COG (Center of Gravity) a COGS (Center of Gravity for Singletons). Trieda fuzzy.OutputVariable implementuje výstupnú fuzzy premennú. Pri jej inicializácii treba určiť metódu defuzzifikácie. Pozostáva z niekoľkých fuzzy hodnôt.

5.4 Definovanie bázy pravidiel

Predošlú tabuľku bázy pravidiel zapíšeme v Pythone takto (iba prvé pravidlo):

from fuzzy.Rule import Rule
from fuzzy.operator.Compound import Compound
from fuzzy.operator.Input import Input
OR, AND = Max(), Min()
system.rules[’preference index is VLP’] = Rule(
adjective = VLP ,
# it gets its value from here
operator=Compound( AND ,
Input(system.variables["irregularity"].adjectives["VLI"]), Compound(
OR,
Input(system.variables["frequency"].adjectives["VLF"]), Input(system.variables["frequency"].adjectives["LF"]), Input(system.variables["frequency"].adjectives["MF"]), Input(system.variables["frequency"].adjectives["HF"]), Input(system.variables["frequency"].adjectives["VHF"])
)
,)
CER=CER
)

Podobne píšeme kód aj pre zostávajúce pravidlá R2 až R5. Trieda fuzzy.Rule implementuje bázu pravidiel. Balík fuzzy.operator pozostáva z operátorov, ktoré vytvárajú bázu pravidiel. Napríklad trieda Compound() slúži na skladanie zloži- tejších pravidiel pomocou noriem a konoriem. Trieda Input() slúži na zviazanie fuzzy hodnoty k uvažovanému vstupu (tvorba výroku).

5.5 Vykreslenie grafov

Príkaz createDoc(system) vykresľuje grafy fuzzy premenných vstupov (irre- gularity, frequency) a výstupov (index preferencie) zadefinovaných v báze dát. Príkaz create3DPlot() vykresľuje 3D obrázok riešenia výstupu FIS vzhľadom na vstupy.

from fuzzy.doc.plot.gnuplot import doc
d = doc.Doc()
d.createDoc(system)
d.create3DPlot(system ,"irregularity","frequency","preference")

Balíček fuzzy.doc.plot.gnuplot je potrebný na vykreslenie vstupných fuzzy mno- žín a výstupných fuzzy premenných a to v 2D a 3D prevedení. Na vykreslenie je použitý program gnuplot [21] cez rozhranie Gnuplot.py.

5.6 Získanie výstupnej hodnoty

Inštancia vstupných hodnôt relatívnej odchýlky pracovných kumulovaných ča- sov od ideálnych je napríklad rovná hodnote irr = 13 a relatívna odchýlka frek- vencie opakovania podobných turnusov je rovná hodnote freq = −54 (priradenie jedného vodiča a jeden turnus). Výslednú hodnotu indexu preferencie spočítame pomocou príkazu system.calculate(…). Ta naplní slovník „out“ novou hod- notou výstupu.

irr, freq, out = 13, -54, {"preference" : 0} system.calculate(input={’irregularity’:irr,’frequency’:freq},output=out)
print output

Nasledujúca sekcia zobrazuje zadanie a riešenie jednej inštancie reálneho problému autobusovej spoločnosti MHD Martin.

6 Reálna inštancia problému

Pre každý deň z množiny dní D = {1,2,…,28} priraď vodičovi V_i z množiny vodičov V = {V₁,V₂,…,V₁₀₇} deň voľna alebo turnus T_k z množiny turnusov T = {T₁,T₂,…,T₁₇₉}, pričom nedôjde k porušeniu žiadnej ťažkej podmienky a k maximálnemu zlepšeniu ľahkých podmienok. Časť turnusov T_k je zadaná v tabuľke 1.

Tabuľka 1: 28 dňová inštancia problému rozpisovania služieb

	Počet vodičov	Počet dni	Počet turnusov
	107	28	179
Turnus	Začiatok [min]	Koniec [min]	Pracovný čas [min]
T1	298	460	239.4
T2	793	980	227.8
…	…	…	…
T178	522	711	219.0
T179	260	700	480.3

Turnusy s identifikačným číslom 1 až 107 sú turnusy, ktoré sa majú odjazdiť počas pracovných dní. Turnusy s číslami 108 až 179 sa majú odjazdiť počas víkendov. Vzhľadom na túto skutočnosť sú definované parametre u_ik, v_i, w_k pre celé obdobie rozpisovania služieb.

Algoritmus day-by-day je napísaný v programovacom jazyku Python (Python Programming Language [18]). Na výpočet priraďovacej úlohy je použité GLPK (GNU Linear Programming Kit [19]). Získavame prijateľný 28 dňovy rozpis služieb vodičov autobusov (tabuľka 2), ktorého relatívna odchýlka kumulovaného pracovného času od ideálneho (obrázok 7(a)) sa sústreďuje okolo nuly. Na obrázku 7(b) vidíme zobrazenú frekvenciu opakovania sa podobných turnusov pridelených vodičom za celé obdobie rozpisovania služieb.

V/D	1Pon	1Uto	1Str	1štv	1Pia	1Sob	…	4Sob	4Ned	si [min]
V1	T1	T2	T4	T4	T8	T127	…	T135	T131	12991.9
V2	T3	T6	T6	T12	T12	T0	…	T0	T135	11753.4
V3	T2	T4	T8	T19	T23	T0	…	T0	T147	7180.4
…	…	…	…	…	…	…	…	…	…	…
V104	T41	T23	T46	T46	T177	T147	…	T119	T164	11984.3
V107	T21	T42	T57	T1	T114	T114	…	T155	T133	11134.2
V106	T19	T5	T10	T38	T144	T133	…	T163	T125	11138.9

Obr. 7: Relatívna odchýlka a frekvencia navrhnutého 28 dňového rozpisu služieb vodičov autobusov

7 Záver

Článok sa venoval problematike rozpisovania služieb vodičom autobusov vo verejnej autobusovej doprave na linkách do 50km. Na vyriešenie problému bola zvolená heuristická metóda day-by-day, ktorá vytvára rozpis služieb po rade pre každý deň plánovaného obdobia. Slabinou (neistotou) algoritmu je, či vytvorený rozpis služieb v uvažovaný deň vedie k optimálnemu výsledku. Z tohoto dôvodu je časť algoritmu fuzzifikovaná a riešená ako fuzzy inferenčný systém. Vstupom systému sú kandidáti na riešenie (odchýlky od ideálneho pracovného času a frekvencie podobných turnusov) a výstupom je index preferencie. Tento index slúži v zovšeobecnenej priraďovacej úlohe ako cena priradenia medzi turnusmi a vodičmi. Iným dôvodom zavedenia fuzzy inferenčného systému je uľahčenie tvorby rozpisu služieb vzhľadom na skúsenosti tvorcov rozpisov (fuzzy premenné a ich hodnoty, fuzzy pravidlá).

Prečo sa v článku snažíme minimalizovať nerovnomernosti v pracovných výkonoch vodičov autobusov? Dôvodov je viacero. Jedným z nich je vplyv na morálku vodičov. Morálka vodičov a tak isto aj práceschopnosť (menej absencií) sa zvyšuje s rovnomernejšími pracovnými výkonmi. Prečo článok maximalizuje u vodičov frekvenciu rovnakých alebo podobných turnusov? Tak isto aj v tomto prípade je dôvodov viacero. Napríklad bezpečnosť a pohodlie vodičov autobusov (návyk na trasu turnusu, tieto turnusy sú odjazdené bezpečnejšie).

No netreba zabúdať aj na to, že sa turnusy nesmú opakovať príliš často. Je možné, že samotná trasa turnusu a jej rôznorodosť pôsobí na vodičov tak, že zostávajú pozorní a že neupadajú do mdlôb z dlhého času sedenia za volantom. Potom by sa ponúkalo viac priestoru pre tvorcu rozpisov služieb, aby sa početnosť podobných turnusov mohla zvýšiť.

Balíček pyFuzzy je veľmi užitočný nástroj. Uľahčuje tvorbu fuzzy množín a prácu s fuzzy logikou pri tvorbe aplikácií. Jeho výhodami je napríklad ľahké modelovanie neistoty, jednoduchý návrh bázy pravidiel a jednoduchý návrh bázy dát (oproti pravdepodobnostným rozdeleniam). Jeho nevýhodami sú napríklad výpočtová rýchlosť inferenčného systému, chýba užívateľská dokumentácia a čiastočná kompatibilita s Windows.

Poďakovanie – Táto práca vznikla s podporou grantovej agentúry VEGA vrámci riešenia projektu 1/0135/08 „Optimalizačné problémy v logistických a doprav- ných systémoch“.

Literatúra

1. FRELING R., WAGELMANS, A.P.M., PAIa ̄O, J.M.P., An Overview of Models and Techniques for Integrating Vehicle and Crew Scheduling, Econometric Institute, Erasmus Universiy Rotterdam, The Netherlands, (1998)
2. POLIAK, M., GNAP, J., Práca vodičov nákladných automobilov a autobusov a používanie tachografov, Žilinská univerzita v Žiline/EDIS-vydavateľstvo ŽU, ISBN 978-80-8070-989-1, (2009).
3. BURKE, E., CAUSMAECKER, P., BERGHE G.V.,A Hybrid Tabu Search Algorithm for the Nurse Rostering Problem, Proceedings of the Second Asia-Pacific Conference on Simulated Evolution and Learning, Springer, 187- 194, (1998)
4. BURKE, E., KENDALL, G., SOUBE- IGA, E.,A Tabu-Search Hyperheuristic for Timetabling and Rostering, (2003).
5. ANDERSEN, A.Ch., FUNCH, Ch.,Rostering Optimization for Business Jet Airlines, Master Thesis, Department of Transport, Technical University of Denmark, Kongens Lyngby, (2008).
6. CAPPANERA, P., GALLO, G., On The Airline Crew Rostering Problem, Technical Report TR-01-08, Dipartimento Di Informatica, Univerista Di Pisa, (2003).
7. KOHL,N.,KARISCH,E.,AirlineCrew Rostering: Problem Types Modeling, and Optimization, Annals of Operations Research, Vol 127, Numbers 1-4, Springer, 223-257, (2004).
8. THEODOROVIC, D., LUČIĆ, P., A fuzzy set theory approach to the aircrew rostering problem, Fuzzy Sets and Systems, Vol 95, Issue 3, 261 – 271,(1998).
9. RESPÍCIO, A., MOZ, M., PATO, M.V., A Mementic Algorithm for a Biobjective Bus Driver Rostering Prob- lem, Centro de Investigacao Operacional, University of Lisbon, Faculy of Science, Lisboa, Portugal, CIO-Working Paper 13/2007 (2007).
10. CAPRARA, A., FISCHETTI, M., TOTH, P., VIGO, D., Modeling and Solving the Crew Rostering Problem, Technical Report DEIS-OR-95-6(R), Universita degli Studi di Bologna, Dipartimento di Elettronica Informatica e Sistemistica, Italy, (1998).
11. PEŠKO, Š., The Matrix Permutation Problem in Interval Arithmetic, Journal of Information, Control and Management Systems, Vol. 1, No.1, 2006
12. ČERNÝ, J., PEŠKO, Š., Uniform Splitting In Managerial Decision Making, E+M,Economics and Management, 4/2006, IX, pp. 67-71, Technuická univerzita v Liberci, ISSN 1212-3609, (2006)
13. TEGZE, M., VLACH, M., On the Matrix Permutation Problem, Report 84-54, Institute fur mathematic, Universityät Graz, 1984
14. RYAN, D.M., The Solution of Massive Generalized Set Partitioning Problems in Air Crew Rostering, J. Oper. Res. Soc. 43, 459-467, (1992)
15. LEE, H.K., First Course of Fuzzy Theory and Applications, Advances in soft computing, Springer, ISBN 3-540- 22988-4 (2005)
16. KLIR, G.J, YUAN B., Fuzzy Sets and Fuzzy Logic, Theory and Applications, ISBN 0-13-101171-5, (1995)
17. SIVANANDAM, S.N., SUMATHI, S., DEEPA, S.N., Introduction to Fuzzy Logic using MATLAB, ISBN 10-3-540- 35780-7, (2007)
18. Python Programming Language, http://www.python.org/
19. GNU Linear Programming Kit (GLPK), Package for solving large- scale linear programming (LP) and mixed integer programming (MIP), www.gnu.org/software/glpk
20. Python fuzzy package, http://pyfuzzy.sourceforge.net/
21. Gnuplot, A portable command-line driven graphing utility, http://www. gnuplot.info/