Dvojetapové stochastické programovanie a rovnomerné rozvrhy pri neistote

16. Máj, 2011, Autor článku: Ladovský Tomáš, Informačné technológie
Ročník 4, číslo 5 Pridať príspevok

Článok sa venuje problematike rozpisovania služieb vodičom autobusov pre prvé tri víkendy predvianočného obdobia, pričom tvorca rozvrhu chce tento rozvrh navrhnúť tak, aby prechod na Vianočný rozvrh, ktorého rozvrhovanie sa ešte len bude realizovať, bol čo najplynulejší. Tvorca rozvrhu na riešenie použije dvojetapové stochastické programovanie (SP), ktorého jadro tvorí priraďovacia úloha. Princíp dvojetapového SP spočíva v tom, že v prvej etape sa priradia turnusy vodičom pre každý deň predvianočného víkendu a v druhej etape sa vykonávajú rekurzívne opravy týchto priradení vzhľadom na predpokladaný rozvrh vo Vianočnom rozvrhu.

1. Úvod

Tvorca rozvrhu má za úlohu vytvoriť rozpisy služieb vodičom autobusov v prímestskej doprave [3] pre časové obdobie dvoch dní. Ide o dni sobota a nedeľa v mesiaci december 2010. Tri víkendy sú v tomto mesiaci pred Vianocami a dva víkendy sa vyskytujú počas sviatkov (Vianoce, Nový rok). Predpokladom je krátkodobé plánovanie, t.j. pre tento mesiac sa vytvára rozvrh najskôr pre prvé tri týždne. Po aplikovaní rozvrhu v praxi sa plánuje Vianočný rozvrh.

Tvorca rozvrhu chce pre tri periodicky sa opakujúce víkendy predvianočného obdobia rozvrhnúť vodičom autobusov turnusy tak, aby celkové výkony vodičov boli čo najrovnomernejšie. Realizácie pracovných časov turnusov predvianočného obdobia modelujeme priemernou hodnotou trvania turnusov za predošlé roky. Tento rozvrh ale treba vytvoriť tak, aby prechod na Vianočný rozvrh, ktorého rozvrhovanie sa ešte len bude realizovať, bol čo najplynulejší, tzv. prechod z predvianočného rozvrhu na Vianočný rozvrh sa realizoval s čo najmenším počtom zmien v priradeniach vodič/turnus, viď. poznámka 6. Realizácie denných pracovných časov turnusov počas Vianočného obdobia nepoznáme vopred, poznáme iba ich optimistický, priemerný a pesimistický odhad.

Najskôr si ukážeme (sekcia 3), ako môžeme vytvoriť rozpis služieb bez predpokladania nejakej náväznosti na Vianočný rozvrh. Tvorba rozpisu služieb na dva dni je optimalizačne nekomplexný problém, ktorý môže riešiť exaktne pomocou bivalentného lineárneho programovania, “priraďovacej úlohy”. Potom si ukážeme (sekcia 4), ako vytvoriť predvianočný rozvrh vzhľadom na predpokladaný Vianočný rozvrh a to tak, aby prechod medzi týmito dvoma rozvrhmi bol čo najplynulejší, t.j. počet zmien v priradeniach vodič/turnus je nulový. Vianočný rozvrh zatiaľ neexistuje, poznáme ale predpokladané realizácie denných pracovných časov turnusov, ktoré môžu byť optimistické, priemerné alebo pesimistické. Na základe týchto predpokladov vieme vytvoriť Vianočný rozvrh. Teda získame tak tri scenáre Vianočného rozvrhu, ktoré sa pravdepodobne môžu udiať.

Ak by sme mali informácia o tom, aké časy turnusov sa budú počas Vianočného obdobia realizovať, tak by tvorba predvianočného rozvrhu nebola vôbec komplikovaná. Keďže ale túto informáciu nemáme, vytvoríme tri samostatné predvianočné rozvrhy. Nakoniec si ukážeme (sekcia 5), ako vytvoriť predvianočný rozvrh pomocou dvojetapového modelu stochastického programovania [1]. Keďže nepoznáme informáciu o skutočných realizáciách denných pracovných časov turnusov vo Vianočnom období, skúsime vytvoriť taký predvianočný rozvrh, ktorý je ideálny za všetkých okolností, ktoré môžu nastať počas sviatkov. Princíp dvojetapového SP spočíva v tom, že pridelí turnusy vodičom v predvianočnom rozvrhu tak, aby celkové výkony vodičov boli čo najrovnomernejšie a druhá etapa vykonáva rekurzívne opravy v tomto predvianočnom rozvrhu vzhľadom na predpokladaný Vianočný rozvrh.

Problém rozpisovania služieb vodičom autobusov (angl. The Bus Driver Rostering Problem – DRP) môžeme formulovať ako: Nech $m$ je počet vodičov autobusov a $n$ je počet pracovných dní. Pre každého vodiča má tvorca rozvrhu navrhnúť postupnosť $n$ turnusov, teda $i$ -ty vodič má prejsť $k$ -ty turnus v $j$ -ty deň. DRP je obmedzovaný viacerými právnymi predpismi [6] a pravidlami spoločností pomocou nasledujúcich ťažkých podmienok:

(h1) v uvažovanom dni môžeme každému vodičovi priradiť práve jeden turnus alebo deň voľna,
(h2) v uvažovanom dni musíme každému turnusu priradiť práve jedného vodiča,
(h3) pre všetkých vodičov sú splnené všetky nutné podmienky na zákonný denný a týždenný odpočinok (článok sa nezaoberá),
(h4) pre všetkých vodičov sú splnené všetky nutné podmienky týkajúce sa maximálneho týždenného pracovného času a času vedenia vozidla (článok sa nezaoberá).

Nazývame ich ťažkými podmienkami, pretože sa nesmú porušiť. Ďalej je dobrý rozpis služieb charakterizovaný čo najlepším dodržaním ľahkých podmienok:

(s1) celkové pracovné časy jednotlivých vodičov za dané obdobie sú približne rovnaké,
(s2) prechod z predvianočného rozvrhu na vianočný rozvrh obsahuje čo najmenej zmien v priradení vodič/turnus.
(s3) náklady sú minimálne (článok sa nezaoberá),
(s4) vodič má priradené turnusy, ktoré dobre pozná, t.j. postupnosť priradených turnusov obsahuje rovnaké alebo podobné trasy (článok sa nezaoberá).

V ľahkých podmienkach sú zahrnuté ciele rozpisovania služieb a tie optimalizujeme. Celkový pracovný čas $i$ -teho vodiča spočítame ako súčet pracovných časov pre každý pracovný deň. Denný pracovný čas vodiča je súčet časov jazdy, prejazdov, manipulácie a státia.

2. Matematická formulácia

Nech $\mathcal D = \{1,2,\dots,n\}$ je množina dní, $\mathcal V = \{1,2,\dots,m\}$ je množina indexov vodičov autobusov a $\mathcal T = \{T_1,T_2,\dots,T_t\}$ je množina turnusov. Parametere $n,m,t$ vyjadrujú porade počet dní, počet vodičov a počet turnusov. Ďalej v texte predpokladáme, že $m = t$ .

Rozpisovanie služieb vodičom autobusov znamená, že pre každý deň z množiny dní $\mathcal D$ priradí tvorca rozvrhu vodičovi $V_i\in\mathcal V$ deň voľna alebo turnus $T_k\in\mathcal T$ z množiny turnusov tak, aby nedošlo k porušeniu žiadnej ťažkej podmienky počas optimalizovania ľahkých podmienok.

Turnus je pevne daná postupnosť trás pre jeden autobus na jeden deň. Definujeme ho ako usporiadanú štvoricu $T_k = (c^o_k, c^p_k, c^m_k, c^s_k)$ nasledovných parametrov: $c^o_k$ čas obsadenia, $c^p_k$ čas prejazdov, $c^m_k$ čas manipulácie a $c^s_k$ čas státia $k$ -teho turnusu. Denný pracovný čas $k$ -teho turnusu spočítame ako $c_k = c^o_k + c^p_k + c^m_k + c^s_k$ pre $k\in\mathcal T$ . Jednotkou času sú minúty.

Celkový pracovný čas i-teho vodiča $s_i$ spočítame ako súčet denných pracovných časov turnusov jemu priradených za celé obdobie rozpisovania služieb.

Rozpisy služieb vodičov autobusov môžeme zovšeobecniť a formulovať ako kombinatorický problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice (angl. matrix permutation problem ${\mathcal MPP}$ ) [5]. Vhodným preusporiadaním stĺpcov (denných výkonov) matice možno zrovnomerniť výkony vodičov zodpovedajúce riadkovým súčtom.

Definícia 1 Matrix permutation problem

Nech $\mathcal M=\{1,2,\dots,m\}$ a $\mathcal N=\{1,2,\dots,n\}$ sú konečné neprázdne množiny a nech $\mathbb A=(a_{ij})\in\mathfrak R^{m\times n}$ je reálna matica rozmeru $m\times n$ . Hľadá sa taká matica permutácií $\Psi = (\psi_j)_{j\in N}$ stĺpcov matice $\mathbb A$ pre ktorú platí:

$\min\Big\{ f(s^{\psi}_1,s^{\psi}_2,\dots,s^{\psi}_m) | s^{\psi}_i=\sum_{j\in\mathcal N} a_{\psi_{ij},j},\forall i\in\mathcal M, \psi_j =$

$= (\psi_{1j},\psi_{2j}\dots,\psi_{mj})\in\Pi(\mathcal M),\forall j\in\mathcal N \Big\}$

kde $f$ je nejaká miera nerovnomernosti vektora reálnych čísel, $s^{\psi}_i$ je $i$ -ty riadkový súčet matice ${\mathrm A}^\psi$ a $\Pi(\mathcal M)$ je množina všetkých permutácií množiny $\mathcal M$ . Riešením takto formulovanej úlohy $\mathcal{MPP}$ je matica ${\mathbb A}^\psi = (a_{\psi_{ij},j})$ .

Mieru nerovnomernosti $f$ potrebujeme na určenie nerovnomernosti riadkových súčtov matice $A^\psi$ pri danej permutačnej matici $\Psi$ . Čím je miera nerovnomernosti $f$ menšia, tým sú riadkové súčty matice $A^\psi$ viac zrovnomernené. V súčasnosti existuje niekoľko mier nerovnomernosti. S ich definíciou sa môžeme stretnúť napríklad v [4,5]. V nasledujúcom texte sa stretneme s nasledujúcimi troma formami miery nerovnomernosti:

$f_{dif}(x_1, \dots, x_m)=\max\{x_1, \dots, x_m\} - \min\{x_1, \dots, x_m\}$

$f_{dev}(x_1, \dots, x_m)=\frac{1}{m}\sum_{i=1}^{m}\frac{|x_i-\bar{x}|}{\bar{x}}$

$f_{ssqr}(x_1, \dots, x_m)=\frac{1}{m}\sum_{i=1}^{m} (x_i - \bar{x})^2$

(1)

Jednotlivé premenné $x_1$ až $x_m$ predstavujú kumulované pracovné výkony $m$ vodičov¹ a $\bar{x}$ je ideálnym pracovným výkonom vodiča, v tomto prípade priemerná hodnota, ktorú spočítame ako

$\bar{x} = \frac{1}{m} \sum_{i=1}^{m} x_i$

Problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice je výpočtovej zložitosti $O((m!)^n)$ . Z tohoto dôvodu sú exaktne riešiteľné len veľmi malé inštancie. Na riešenie veľkých inštancií môžeme použiť heuristické metódy. Najznámejšou a najvhodnejšou heuristickou metódou, ktorá je veľmi rýchla a dosahuje veľmi dobré výsledky, je stochastická-dekompozičná metóda [4,5].

V nasledujúcom texte si predstavíme príklad dvojdňového predvianočného rozpisu služieb, t.j. ${\mathcal MPP}$ inštanciu, kde $n=2$ . Takto definovaný problém poznáme pod menom \uv{problém rovnomernosti riadkových súčtov stĺpcovo permutovanej dvojstĺpcovej reálnej matice}, ( $MPP2c$ ).

3. Rozpisovanie služieb v predvianočnom období

Riešme nasledujúcu inštanciu MPP2c problému s nasledujúcimi vstupnými hodnota: Nech $m = t = 7$ a $n = 2$ . Pre prvky matice $\mathbb A = (a_{ij})$ rozmeru $m\times 2$ platí, že $a_{ij} = c_i$ pre $\forall(i,j)\in\mathcal M\times\mathcal D$ , kde $c_i$ predstavuje denný pracovný čas $i$ -teho turnusu. Časy obsadenia, prejazdov, manipulácie, státia a celkové časy turnusov sú v tabuľke 1. Problém ${\mathcal MPP2c}$ [4,5] vieme riešiť exaktne v polynomiálnom čase pomocou priraďovacej úlohy lineárneho bivalentného programovania, pre ktorú sú obe ťažké podmienky ( $h_1,h_2$ ) splnené.

Tab.1. Časy obsadenia, prejazdov, manipulácie, státia a celkové časy turnusov obdobia pred Vianocami

Turnus	$c^o_k$	$c^p_k$	$c^m_k$	$c^s_k$	$c_k$
Turnus 1	206	8	53	75	342
Turnus 2	274	4	75	141	494
Turnus 3	216	4	54	77	351
Turnus 4	228	8	60	106	402
Turnus 5	239	4	54	92	389
Turnus 6	314	4	68	111	497
Turnus 7	212	4	65	117	398

Definícia 2 Klasická priraďovacia úloha ${\mathcal KPU}$ )

Medzi najznámejšie inštancie rozvrhovacích úloh patrí klasická priraďovacia úloha. Nech $\mathcal V,|V|=m$ je konečná množina, $\mathbb C$ typu $m\times m$ je daná matica reálnych čísel a $\mathbb X$ typu $m\times m$ je hľadaná matica priradení. Potom priraďovaciu úlohu možno formulovať ako nasledujúcu úlohu bivalentného lineárneho programovania.

$\begin{array}{c} \min Z = \sum_{i\in\mathcal V} \sum_{j\in\mathcal V}{c_{ij}x_{ij}} \\ s.t. \\ \sum_{i\in\mathcal V}x_{ij} = 1, \quad pre \quad \forall j\in\mathcal V, \\ \sum_{j\in\mathcal V}x_{ij} = 1, \quad pre \quad \forall i\in\mathcal V \\ x_{ij}\in\{0,1\}, \quad pre \quad \forall (i,j)\in\mathcal V^2 \end{array}$

Prvky matice priradení $\mathbb X$ môžeme pre ${\mathcal MPP2c}$ problém definovať ako: x_ij =

1 – ak $latexi$-temu vodičovi/turnusu v prvý deň priradíme $j$ -ty turnus v druhý deň, t.j. $\psi_{i2} = j$
0 – nič nerobíme

Ostáva nám teraz, vzhľadom na ľahkú podmienku (s1), správne navrhnúť účelovú funkciu, t.j. prvky matice $\mathbb C$ . Pre tento účel nám poslúži miera nerovnomernosti (1). Po jednoduchej úprave získavame nasledujúci tvar

$f_{ssqr}(s_1,s_2,\dots,s_m) = \frac{1}{m}\sum_{i=1}^{m}s_i^2 - \bar{s}^2$

kde je $s_i = a_{i1} + a_{\psi_{i2} 2}$ a to za predpokladu, že permutácia prvého stĺpca je identická, t.j. $\psi_{i1} = (1,2,\dots, m)$ . Hodnoty $\frac{1}{m}$ a $\bar{s}^2$ sú konštantné a neovplyvňujú výsledok optimalizácie, preto ich z účelovej funkcie môžeme vypustiť. Za predpokladu $\psi_{i2} = j$ môžeme písať prvok matice $\mathbb C$ ako $c_{ij} = (a_{i1} + a_{j2})^2$ . Potom účelová funkcia nadobúda tvar

$Z = \sum_{i\in\mathcal V} \sum_{j\in\mathcal V}{(a_{i1} + a_{j2})^2 x_{ij}}$

Priraďovaciu úlohu môžeme riešiť napríklad použitím solvera GLPK [7]. V tabuľke 2 môžeme nájsť víkendový rozpis služieb predvianočného obdobia. Výsledku sa dá ľahko porozumieť. Solver spojil prvý najkratší turnus s prvým najdlhším turnusom, druhý najkratší turnus s druhým najdlhším turnusom, a tak ďalej. Hodnoty mier nerovnomerností sú pre rozvrh viď. tabuľka 2 zobrazené v tabuľke 3. Vyriešili sme problém, dodržali všetky podmienky a získali sme rozvrh pre tri víkendy predvianočného obdobia, ktorých celkové pracovné časy medzi vodičmi sú približne rovnaké.

Tab. 2. Výsledky priradenia turnusov – finálny rozvrh

Vodič	Sobota	Nedeľa	$s_i$
1	T1 (342)	T6 (497)	839
2	T2 (494)	T3 (351)	845
3	T3 (351)	T2 (494)	845
4	T4 (402)	T5 (389)	791
5	T5 (389)	T4 (402)	791
6	T6 (497)	T1 (342)	839
7	T7 (398)	T7 (398)	796

Tab.3. Výsledky priradenia turnusov – miery nerovnomernosti

Cieľová f.	hodnota
$f_{diff}$	54
$f_{dev}$	0.029
$f_{ssqr}$	4224.86

Poznámka 1

Čitateľ si mohol všimnúť, že rovnomernejšie výkony vodičov, pre prvé tri víkendy mesiaca december 2010, by sme obdržali riešením problému ${\mathcal MPP}$ s parametrami $m = 7$ a $n = 6$ , kde prvé dva stĺpce predstavujú prvý víkend, druhé dva stĺpce druhý víkend a posledné dva stĺpce matice $\mathbb A$ predstavujú tretí víkend. Tento problém je však $NP$ -ťažký a riešiteľný už pre takto malú inštanciu iba heuristickými metódami. Najúspešnejšou z nich je vzhľadom na rýchlosť a optimalitu riešenia stochastická dekompozičná metóda [4,5].

4. Reprezentácia pomocou scenárov

V predošlej sekcii sme navrhli predvianočný rozpis služieb pre prvé tri víkendy mesiaca december 2010. Vieme, že vianočný rozpis služieb, t.j. posledné dva víkendy mesiaca december 2010, sa bude rozvrhovať až po odovzdaní a aplikovaní predvianočného rozvrhu. Ak by sme použili predvianočný rozpis služieb a rovnakým spôsobom naplánovali Vianočný rozpis služieb, tak by mohla nastať situácia, že celkové kumulované pracovné časy by boli veľmi nerovnomerné, t.j. by sme porušili veľmi ľahkú podmienku (s1).

Taktiež je veľmi pravdepodobné, že by došlo k porušeniu podmienky (s2), tzv. prechod z predvianočného rozvrhu na Vianočný rozvrh by znamenal zmeny v priradeniach medzi turnusmi a vodičmi, na čo by protestovali vodiči autobusov. Preto sa pokúsime vytvoriť predvianočný rozvrh, ktorý by viedol na rovnomerné kumulované pracovné výkony vodičov za celý mesiac, pričom prechod z tohoto rozvrhu na Vianočný rozvrh je čo najplynulejší.

Poznámka 2 Zaujímavá sa zdá byť problematika minimalizovania počtu zmien pri prechode z rozvrhu A na rozvrh B.

Predpokladajme, že z predošlej sekcie máme k dispozícií časy obsadenia, prejazdov, manipulácie, státia a denné pracovné časy turnusov predvianočného obdobia 1. Realizácie denných pracovných časov turnusov Vianočného obdobia nepoznáme, poznáme iba ich optimistický, priemerný a pesimistický odhad. Tabuľka 4 obsahuje takéto dáta, pričom 3(a) sú dĺžky turnusov za dobrých podmienok, 3(b) sú dĺžky turnusov za priemerných podmienok a 3(c) sú dĺžky turnusov za zlých podmienok.

Tab.3. Časy obsadenia, prejazdov, manipulácie, státia a celkové časy turnusov za dobrých, priemerných a zlých podmienok v období Vianoc

(a) Dobré podmienky

$T_k$	$c^{o1}_j$	$c^{p1}_j$	$c^{m1}_j$	$c^{s1}_j$	$c^1_j$
$T_1$	215	8	59	77	359
$T_2$	279	6	77	143	505
$T_3$	218	5	54	78	355
$T_4$	231	9	65	108	413
$T_5$	239	5	56	96	396
$T_6$	321	7	69	117	514
$T_7$	219	9	69	122	419

(b) Priemerné podmienky

$T_k$	$c^{o2}_j$	$c^{p2}_j$	$c^{m2}_j$	$c^{s2}_j$	$c^2_j$
$T_1$	220	8	60	77	365
$T_2$	283	6	77	146	512
$T_3$	218	6	59	84	367
$T_4$	235	9	65	110	419
$T_5$	251	8	59	100	401
$T_6$	322	7	69	118	516
$T_7$	220	9	70	123	422

(c) Zlé podmienky

$T_k$	$c^{o2}_j$	$c^{p2}_j$	$c^{m2}_j$	$c^{s2}_j$	$c^2_j$
$T_1$	222	9	61	79	371
$T_2$	286	6	79	148	519
$T_3$	219	8	62	89	378
$T_4$	237	9	65	114	425
$T_5$	251	8	59	100	418
$T_6$	323	7	70	118	518
$T_7$	221	9	70	124	424

Pomocou týchto údajov vyhodnotíme pre každý turnus $T_k\in\mathcal T$ tri hodnoty:

optimistický odhad pracovného času za predpokladu realizácie krátkych pracovných časov možných situácií,
priemerný odhad pracovného času
pesimistický odhad pracovného času za predpokladu realizácie dlhých pracovných možných situácií.

Teraz nás zaujíma citlivosť rovnomernosti predvianočného rozvrhu vzhľadom na predpokladané Vianočné realizácie denných pracovných časov. Preto spravíme ešte ďalšie tri optimalizácie založené na predpokladaných realizáciách denných časov turnusov počas Vianočného obdobia. Ako príklad si ukážeme výpočet optimálneho rozvrhu za predpokladu, že počas Vianoc nastanú tie najlepšie podmienky.

Nech $\mathcal V$ je množina indexov vodičov autobusov a nech prvky matice $\mathbb A$ rozmeru $m\times 2$ predstavujú plánované denné pracovné časy predvianočného obdobia a nech prvky matice $\mathbb B^1$ rozmeru $m\times 2$ predstavujú plánované optimistické denné pracovné časy Vianočného obdobia. Účelovú funkciu navrhneme rovnako ako v predošlom matematickom modeli.

$\begin{array}{c} \min Z = \sum_{i\in\mathcal V}\sum_{j\in\mathcal V} {(a_{i1}+a_{j2})^2 x_{ij}} + \sum_{i\in\mathcal V}\sum_{j\in\mathcal V} {(b^1_{i1}+b^1_{j2})^2 y_{ij}} \\ \text{subject to} \\ \sum_{i\in\mathcal V} x_{ij} = 1, \quad \mbox{ pre } \quad j\in\mathcal V \\ \sum_{j\in\mathcal V} x_{ij} = 1, \quad \mbox{ pre } \quad i\in\mathcal V \\ \sum_{i\in\mathcal V} y_{ij} = 1, \quad \mbox{ pre } \quad j\in\mathcal V \\ \sum_{j\in\mathcal V} y_{ij} = 1, \quad \mbox{ pre } \quad i\in\mathcal V \\ x_{ij} - y_{ij} = 0 \quad \mbox{ pre } \quad i\in\mathcal V, j\in\mathcal V \end{array}$

(2)

kde $x_{ij} = y_{ij} =$

1 ak i-temu turnusu v prvý deň priradíme j-ty turnus v druhý deň, t.j. $\psi_{i2} = j \quad \forall (i,j)\in\mathcal V\times\mathcal V$
0 inak

Poznámka 3 Aj keď sa dá matematický model (2) zjednodušiť aplikovaním substitúcie $y_{ij} = x_{ij}, (i,j)\in\mathcal V^2$ , tak túto formuláciu ponechávame z ilustračného dôvodu a neskoršieho použitia v nasledujúcej sekcii v dvojetapovom stochastickom programovaní, kde premenné matice $X$ vyjadrujú rozhodnutia prvej etapy a premenné matice $Y$ vyjadrujú rozhodnutia druhej etapy.

Poznámka 4 Ďalším vhodným spôsobom optimalizácie ľahkej podmienky (s2) z úvodu článku je Lagrangeová relaxácia podmienky $x_{ij} - y_{ij} = 0$ z matematického modelu (2). Nech $\lambda\geq 0$, potom účelovú funkciu matematického modelu \REFe{\eqnlabelname: extended assignment problem} môžeme zapísať ako:

$Z = \sum_{i\in\mathcal V}\sum_{j\in\mathcal V} {(a_{i1}+a_{j2})^2 x_{ij}} + \sum_{i\in\mathcal V}\sum_{j\in\mathcal V} {(b_{i1}+b_{j2})^2 y_{ij}} +$

$+ \lambda \sum_{i\in\mathcal V}\sum_{j\in\mathcal V} (x_{ij} - y_{ij})$

Použitím solvera GLPK [7] sme obdržali predvianočný rozvrh a to za predpokladu, že sa počas Vianoc budú realizovať optimistické odhady denných pracovných časov turnusov. Takto spočítame predvianočné rozvrhy aj pre ostatné scenáre. V tabuľke 5 sa nachádzajú optimálne rozvrhy obdobia pred Vianocami za predpokladu výskytu najlepších možných situácií 4(a), za predpokladu výskytu priemerných situácií 4(b) a za predpokladu výskytu najhorších možných situácií 4(c).

Tab.5. Predvianočné rozvrhy za optimálnych, priemerných a pesimistických podmienok Vianočného obdobia

(a) Predvianočný rozvrh za dobrých podmienok

$V_i$	Sobota	Nedeľa	$s_i$
1	T1 (342)	T6 (494)	836
2	T2 (494)	T3 (342)	836
3	T3 (351)	T2 (497)	848
4	T4 (402)	T5 (402)	804
5	T5 (389)	T4 (398)	787
6	T6 (497)	T1 (351)	848
7	T7 (398)	T7 (389)	787

(b) Predvianočný rozvrh za priemerných podmienok

$V_i$	Sobota	Nedeľa	$s_i$
1	T1 (342)	T6 (497)	839
2	T2 (494)	T3 (351)	845
3	T3 (351)	T2 (494)	845
4	T4 (402)	T5 (402)	804
5	T5 (389)	T4 (398)	787
6	T6 (497)	T1 (342)	839
7	T7 (398)	T7 (389)	787

(c) Predvianočný rozvrh za zlých podmienok

$V_i$	Sobota	Nedeľa	$s_i$
1	T1 (342)	T6 (497)	839
2	T2 (494)	T3 (351)	845
3	T3 (351)	T2 (494)	845
4	T4 (402)	T5 (389)	791
5	T5 (389)	T4 (402)	791
6	T6 (497)	T1 (342)	839
7	T7 (398)	T7 (398)	796

Pre predvianočné rozvrhy z tabuľky 5 môžeme spočítať miery nerovnomernosti, ktoré sú zobrazené v tabuľke 6.

Tab.6 Miery nerovnomernosti predvianočných rozvrhov za optimálnych, priemerných a pesimistických podmienok Vianočného obdobia

(a)

Cieľová f.	hodnota
$f_{max}$	848
$f_{dev}$	0.0294
$f_{ssqr}$	4508.86

(b)

Cieľová f.	hodnota
$f_{max}$	845
$f_{dev}$	0.0294
$f_{ssqr}$	4400.86

(c)

Cieľová f.	hodnota
$f_{max}$	845
$f_{dev}$	0.0294
$f_{ssqr}$	4224.86

Poznámka 5 Je zrejmé, že veľkosť miery nerovnomernosti závisí od realizácií denných pracovných časov Vianočného obdobia ale zároveň je nezávislá od charakteru scenára. Mohli by sme totiž predpokladať, že pri optimistických Vianočných časoch je miera nerovnomernosti minimálna. Za dobrých podmienok je miera nerovnomernosti $f_{ssqr}$ rovná hodnote 4508.86 a za zlých podmienok je miera nerovnomernosti $f_{ssqr}$ rovná hodnote 4224.86, ktorá je nižšia ako hodnota za dobrých podmienok, t.j. rozvrh je viac zrovnomernený pri pesimistických denných pracovných časoch turnusov.

Poznámka 6 Po vypustení podmienky $x_{ij} - y_{ij} = 0$ z matematického modelu 2 získame dva nezávislé rozvrhy, ktoré sme schopní zostaviť na základe rozhodnutí priradenia turnusov $x_{ij}$ a $y_{ij}$ . Ak sú za tohoto predpokladu tieto rozhodnutia rovnaké pre každé i a j, tak oba rozvrhy majú minimálne miery nerovnomernosti a nedôjde k žiadnym zmenám v rozvrhoch pri prechode z predvianočného obdobia na vianočné obdobie. Ak by ale rozhodnutia $x_{ij}$ a $y_{ij}$ boli rôzne, napr. $x_{11} = 1$ a $x_{14} = 1$ , tak prvému vodičovi v predvianočnom rozvrhu priradíme prvý turnus, zatiaľ čo vo vianočnom rozvrhu by sme prvému vodičovi museli zmeniť prvý turnus na štvrtý.

5. Stochastický prístup

V predošlej sekcii by sa nám veľmi zišla informácia o tom, aké denné pracovné časy turnusov sa počas Vianoc budú realizovať. Ak by sme takúto informáciu mali, napríklad podmienky budú počas Vianoc dobré, čo bude viesť k optimistickým časom, tak by nám stačilo použiť predvianočný rozvrh z tabuľky 4(a). Nanešťastie takúto informáciu nemáme, a tak sa musíme rozhodnúť bez nej. Vieme ale, že chceme taký predvianočný rozvrh, ktorý bude vyhovovať všetkým podmienkam.

Rozhodnutia $X = (x_{ij})$ musíme urobiť v najbližšom čase, ale rozhodnutia $Y = (y_{ij})$ budeme robiť pár dní pred Vianočným rozvrhom. Na rozlíšenie rozhodnutí $y_{ij}$ závislých na Vianočných podmienkach použijeme index scenára $s=1,2,3$ , odpovedajúci optimálnym, priemerným a pesimistickým realizáciám denných pracovných časov turnusov. Toto vytvorí novú množinu premenných tvaru $y^s_{ij}, s=1,2,3, (i,j)\in\mathcal V\times\mathcal V$ .

Rozhodnutie $y^3_{13}$ predstavuje priradenie prvého turnusu v prvý víkendový deň Vianočného obdobia k tretiemu turnusu v druhý víkendový deň Vianočného obdobia a to za predpokladu pesimistických realizácií pracovných časov turnusov. Rovnako ako v predošlej sekcii je našim cieľom vytvoriť predvianočný rozvrh, ktorý by viedol na rovnomerné kumulované pracovné výkony vodičov za celý mesiac, pričom prechod z tohoto rozvrhu na Vianočný rozvrh je čo najplynulejší.

Nech $\mathcal V = \{1,2,\dots,m\}$ je množina indexov vodičov autobusov, nech $\mathcal S = \{1,2,3\}$ je množina indexov scenárov (opt., priem., pes.) a nech prvky matice $\mathbb A$ rozmeru $m\times 2$ predstavujú plánované denné pracovné časy predvianočného obdobia a nech prvky matice $\mathbb B^s$ rozmeru $m\times 2$ predstavujú plánované denné pracovné časy Vianočného obdobia za scenára $s$ . Účelovú funkciu rozšírime podobne ako v predošlej sekcii. Ak majú scenáre rovnakú pravdepodobnosť rovnú hodnote 1/3, potom problém rovnomerného rozpisovania služieb vodičom autobusov, môžeme zapísať ako:

$\begin{array}{c} \min \sum_{i\in\mathcal V}\sum_{j\in\mathcal V} {(a_{i1}+a_{j2})^2 x_{ij}} + \frac{1}{3}\sum_{s\in\mathcal S}\sum_{i\in\mathcal V}\sum_{j\in\mathcal V} {(b^s_{i1}+b^s_{j2})^2 y^s_{ij}} \\ \text{subject to} \\ \sum_{i\in\mathcal V} x_{ij} = 1, \quad \mbox{ pre } \quad j\in\mathcal V \\ \sum_{j\in\mathcal V} x_{ij} = 1, \quad \mbox{ pre } \quad i\in\mathcal V \\ \sum_{i\in\mathcal V} y^s_{ij} = 1, \quad \mbox{ pre } \quad j\in\mathcal V, s\in\mathcal S \\ \sum_{j\in\mathcal V} y^s_{ij} = 1, \quad \mbox{ pre } \quad i\in\mathcal V, s\in\mathcal S \\ x_{ij} - y^s_{ij} = 0, \quad \mbox{ pre } \quad i\in\mathcal V, j\in\mathcal V, s\in\mathcal S \end{array}$

(3)

kde $x_{ij}$

1 ak v predvianočnom rozvrhu i-temu turnusu v prvý deň priradíme j-ty turnus v druhý deň, t.j. $\psi_{i2} = j \quad \forall (i,j)\in\mathcal V\times\mathcal V$
0 inak,

kde $y^s_{ij}$

1 ak vo Vianočnom rozvrhu i-temu turnusu v prvý deň priradíme j-ty turnus v druhý deň v s-tom scenári, \quad \forall (i,j,s)\in\mathcal V\times\mathcal V\times\mathcal S$
0 inak,

Rozhodnutia $x_{ij}$ sa nazývajú prvou etapou SP a sú vykonané teraz (predvianočný rozvrh). Rozhodnutia $y^s_{ij}$ sa nazývajú druhou etapou SP a závisia na budúcich okolnostiach. Takýto model stochastického pregramovania je známy ako rozsiahla forma (extensive form) [1], pretože explicitne² popisuje druhú etapu (second stage) premenných rozhodnutí pre všetky scenáre. Optimálne riešenie pre (3) je v tabuľke 7.

Tab. 7. Predvianočný dvojetapový rozvrh

Vodič	Sobota	Nedeľa	$s_k$ [min]
1	T1 (342)	T6 (497)	839
2	T2 (494)	T3 (351)	845
3	T3 (351)	T2 (494)	845
4	T4 (402)	T5 (402)	804
5	T5 (389)	T4 (398)	787
6	T6 (497)	T1 (342)	839
7	T7 (398)	T7 (389)	787

Na základe predvianočného dvojetapového rozvrhu sú vypočítané miery nerovnomernosti, ktoré môžeme vidieť v tabuľke 8.

Tab. 8 Miery nerovnomernosti predvianočného dvojetapového rozvrh

Cieľová f.	hodnota
$f_{max}$	845
$f_{dev}$	0.0294
$f_{ssqr}$	4296.86

Záver

Článok sa zaoberal problematikou rovnomerného rozpisovania služieb vodičom autobusov v prímestskej autobusovej doprave. Zovšeobecnený problém môžeme v literatúre nájsť pod názvom \uv{problém rovnomernosti riadkových súčtov stĺpcovo permutovanej matice} (angl. Matrix permutation problem [4,5]). Rozpisy služieb sme vytvorili pre prvé tri víkendy mesiaca December 2010 tak, aby tento predvianočný rozvrh mal zrovnomernené celkové kumulované výkony vodičov autobusov. Navyše sme tento rozvrh vytvorili tak, aby prechod na Vianočný rozvrh, ktorého rozvrhovanie sa ešte len bude realizovať, bol čo najplynulejší, tzv. aby ostali rovnaké (podobné) turnusy vodičom počas celého mesiaca December.

Takto zadefinovaný problém sme najskôr riešili iba pre predvianočné obdobie. Potom sme problém rozšírili o Vianočný rozvrh, ktorého realizácie denných pracovných časov turnusov sme nepoznali, poznali sme iba ich optimistické, priemerné a pesimistické odhady. Vzhľadom na tieto odhady sme obdržali tri možné scenáre predvianočného rozvrhu. Takto vyriešený problém je ale neefektívny v praxi. Preto sme využili nástroj stochastického matematického programovania a vytvorili jeden rozpis služieb, ktorý je výhodný pre všetky tri scenáre.

Poďakovanie

Táto práca vznikla s podporou grantovej agentúry VEGA vrámci riešenia projektu 1/0374/11 “Modelovanie a optimalizácia mobility a infraštruktúry v logistických sieťach.”.

Literatúra

Birge, J.R., Louveaux, F., Introduction to Stochastic Programming, Springer, ISBN 0-387- 98217-5, 1997
Krišandová, M., Návrh mesačných rozvrhov vodičov autobusov, Fakulta riadenia a informatiky, Univerzita v Žiline, Diploma work 268/2006, 2007
Ladovský, T., Fuzzifikovaná heuristika day-by-day pre tvorbu rozvrhu služieb vodičov autobusov, Dopravná infraštruktúra v mestách, 7. medzinárodná konferencia DIvM 2010, 2010
Peško, Š., Optimalizácia NP-ťažkých dopravných rozvrhov, ŽU Žilina, Habilitačná práca, 2002
Peško, Š., The Matrix Permutation Problem in Interval Arithmetic, Journal of Information, Control and Management Systems, vol. 1, num. 1, 2006
Poliak, M. and 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
GNU Linear Programming Kit (GLPK), Package for solving large-scale linear programming (LP) and mixed integer programming (MIP)

¹ Pre MPP problém platí x_i = s_i pre všetky i ∈ M
²Explicitne (lat.) je výslovne, jasne, jednoznačne

O časopise

Meta

RSS

Dvojetapové stochastické programovanie a rovnomerné rozvrhy pri neistote

Napísať príspevok

Rubriky

Burza práce

Štúdijné materiály

Archív