Kivonat. elősegíthető. Egy ilyen optimalizálási feladat nagyon komplex, ezért a

¨ Utemez´ esi feladatok az aut´ obuszos k¨ oz¨ oss´ egi k¨ ozleked´ es operat´ıv tervez´ es´ eben: Egy ´ attekint´ es ´ Argil´ an Viktor, Balogh J´ anos, B´ ek´ esi J´ ozsef, D´ avid Bal´ azs, Galambos G´ abor, Kr´ esz Mikl´ os, T´ oth Attila Szegedi Tudom´ anyegyetem, Juhász Gyula Pedagógusképz˝o Kar, Informatika Alkalmazásai Tanszék, 6701 Szeged, Pf. 396. {gilan,balogh,bekesi,davidb,galambos,kresz,attila}@jgypk.u-szeged.hu Kivonat A k¨ ozlekedési t´ arsas´ agok sz´ am´ ara lényeges szempont a k¨ oltségeik racionaliz´ al´ asa, amit legk¨ onnyebben az operat´ıv k¨ oltségeik cs¨ okkentésével val´ os´ıthatnak meg. Ez a j´ aratok, a j´ arm˝ uvek optimaliz´ alt u ¨temezésével is el˝ oseg´ıthet˝ o. Egy ilyen optimaliz´ al´ asi feladat nagyon komplex, ezért a m˝ uveletek u ¨temezését h´ arom f´ azisra bontva t´ argyaljuk. Ezek a j´ arm˝ uu ¨temezés, a vezet˝ ou ¨temezés és a m˝ uszakkioszt´ as feladatai. Ezek a részfeladatok a ´ltal´ aban NP-nehéz problém´ ak, ezért az elm´ ult évtizedig k¨ ozepes méret˝ u feladatok optim´ alis megold´ asa sem volt lehetséges. A sz´ am´ıt´ asi sebesség, az alkalmazott modellek és az azokat megold´ o algoritmusok olyan jelent˝ osen fejl˝ odtek, hogy lehet˝ ové v´ alt nagyobb méret˝ u feladatok kezelése is. A cikkben a ´ttekintj¨ uk az eml´ıtett részfeladatok megold´ as´ ara szolg´ al´ o legfontosabb m´ odszereket. T´ argyaljuk azok k¨ ul¨ onb¨ oz˝ o matematikai modelljeit, hatékony megold´ asi lehet˝ oségeikkel egy¨ utt. A speci´ alis korl´ atoz´ o feltételek szerepét saj´ at tapasztalatainkon kereszt¨ ul vizsg´ aljuk. Utalunk a busz- és vezet˝ ou ¨temezési probléma a ´ltalunk tanulm´ anyozott és bevezetett megold´ asi m´ odszereire is.

1.

Bevezet´ es

A k¨ oz¨ osségi k¨ ozlekedési szolgáltató vállalatok kiadásainak nagy részét az operat´ıv k¨ oltségek alkotj´ ak. Ez jórészt a járm˝ uflotta költségéb˝ol, a járm˝ uvek u ¨zemanyag- és karbantart´ asi k¨ oltségéb˝ol, valamint a járm˝ uvezet˝ok fizetéséb˝ol tev˝odik ossze. Ebb˝ ¨ ol k¨ ovetkez˝ oen az operat´ıv költségekben mutatkozó megtakar´ıtás sz´ amottev˝ o jav´ıt´ ast adhat költségvetés¨ ukben. A leggyakrabban használt módszer ezeknek a k¨ oltségeknek a csökkentésére egy hatékony, szám´ıtógéppel támogatott inform´ aci´ os rendszer kialak´ıtása és használata. Az IKT (információs és telekommunik´ aci´ os technológia) fejl˝odésének köszönhet˝oen napjainkra szinte minden k¨ oz¨ osségi k¨ ozlekedési társaság — modern vállalatirány´ıtási környezetet biztos´ıtva — rendelkezik saját információs rendszerrel. Ezeknek a rendszereknek a f˝o funkciói az u ¨zleti alkalmazásokon t´ ul (´ ugymint k¨ onyvelés, sz´ amvitel, stb.) olyan modulokat is tartalmaznak, amelyek • el˝ okész´ıtik a j´ arm˝ uvek u ¨temezését a vállalat által kiszolgált vonalakhoz, • illesztik a j´ arm˝ uvek és a járm˝ uvezet˝ok m˝ uszakjainak u ¨temezését a vonalakhoz,

1

• képesek a j´ arm˝ uflotta nyomon követésére és monitorozására egy-egy nap sor´ an, • jelzik a diszpécsernek a szokatlan eseményeket (meghibásodás, késés, stb.), • nyomon k¨ ovetik a j´ arm˝ uflotta járm˝ uveinek állapotát, és m´ as hasonl´ o tevékenységeket. Az IKT-k¨ ornyezet alapvet˝o háttérként szolgál a hatékony logisztikai irány´ıt´ asra (l´ asd pl. [56]), ugyanakkor a folyamatban jelen van egy másik elvárás, amely azt k´ıv´ anja, hogy tal´ aljuk meg a rendszer azon részeit, amelyek az operat´ıv, m˝ uveleti k¨ oltségek szempontjából csökkenthet˝ok. J´ onéh´ any ipari d¨ ontést´ amogatási eszköz létezik, amely a logisztikai rendszertervezési és optimaliz´ al´ asi feladatok komplett megoldását célozza. A gyakorlatban ennek ellenére kider¨ ul, hogy sok vállalatspecifikus részlet, korlátozó feltétel van jelen, amelyeket az általános rendszerek nem kezelhetnek egységesen, de amelyek fontosak a közlekedési vállalatok számára. Példaként eml´ıtj¨ uk, hogy amennyiben a k¨ ozlekedési társaság alternat´ıv u ¨zemanyag´ u járm˝ uveket is alkalmaz flott´ aj´ an´ al, akkor ezek u ¨temezésénél figyelembe kell venni a szaknyelven r´ adiusznak nevezett, egy tankolással megtehet˝o kilométerek számát, amely j´ oval kevesebb lehet, mint a hagyományos u ¨zemanyagokkal m˝ uköd˝o járm˝ uvek fut´ asi teljes´ıtménye. Ilyen eseteket vizsgáltak [62]-ben és [53]-ban. Alternat´ıv u ¨zemanyag´ u j´ arm˝ uveknél fontos tényez˝o a tankolás id˝otartama is. Am´ıg hagyom´ anyos u ¨zemanyagokn´ al (pl. d´ızelolaj) a tankolás kb. 5 perc, addig CNG (compressed natural gas) vagy más u ¨zemanyagok esetén a feltöltési id˝o ennek t¨ obbsz¨ or¨ ose is lehet. Ilyen jelleg˝ u feladatok kezelését ismertett¨ uk néhány cikk¨ unkben (l´ asd pl. [9]). Azért, hogy megfelel˝o járm˝ uu ¨temezés kész¨ uljön, ezeket a feltételeket sz´ am´ıt´ asba kell venni a napi u ¨temezést elkész´ıt˝o szoftvernél. Legjobb tudom´ asunk szerint napjaink u ¨temez˝o szoftverei nem kezelnek ilyen jelleg˝ u feltételeket, vagy azokat csak korlátozott mértékben veszik figyelembe. K¨ ovetve a k¨ oz¨ osségi k¨ ozlekedési szolgáltatás fejlesztésének általános módszereit, egy fejlesztés f˝ o horizontjai a következ˝ok: • stratégiai tervezés, ennek f˝o eleme a buszok, járatok u ´tvonalának meghat´ aroz´ asa (buszvonalak kialak´ıtása), • taktikai tervezés, melynek legfontosabb eredménye a menetrend elkész´ıtése és • operat´ıv tervezés, a szolgáltatás ellátásához a buszok és a vezet˝ok, a m˝ uszakok u ¨temezése. Az irodalomban létezik másféle felfogás is, a feladatokat lehet másképpen csoportos´ıtani. Bornd¨ orfer [14] a stratégiai és a taktikai tervezést közös, u ń. szolg´ altat´ astervezési” f´ azisba vonja össze. Megeml´ıt olyan kapcsolódó — a szol” g´ altat´ astervezés k¨ orébe sorolható — feladatokat (pl. jegyárazás, tarifatervezés és -kialak´ıt´ as), amelyek az utazási igényeket is meghatározhatják. Az ilyen jelleg˝ u feladatokat — és a hozzájuk tartozó modelleket — ebben a cikkben nem t´ argyaljuk. 2

Az, hogy mi csak az eml´ıtett operat´ıv tervezési részfeladatok tárgyalására szor´ıtkozunk, a terjedelmi korlátokon t´ ul az is az oka, hogy a közösségi közlekedési szolg´ altat´ o v´ allalatoknak a többi eml´ıtett stratégiai és taktikai tervezési feladatra kevés befoly´ asuk van: ezek általában az állami kormányzati vagy helyi onkorm´ ¨ anyzati (pl. v´ arosi) szervek által meghatározottak. Azon k´ıv¨ ul, hogy a j´ aratok milyen s˝ ur˝ un k¨ ovessék egymást, más el˝o´ırások is vonatkozhatnak a vonalakra, és azon bel¨ ul bizonyos járatokra is. Például a vonalak kapacitására, vagy a szolg´ altat´ ast ell´ at´ o j´ arm˝ uvek speciális tulajdonságaira is lehetnek el˝o´ırások. Egy jellemz˝ o példa az, hogy melyik vonalon milyen id˝oközzel közlekedjenek alacsonypadl´ os j´ arm˝ uvek. Ezen t´ ulmen˝ oen viszont szinte teljesen a közlekedési társaságok döntését˝ol f¨ ugg, hogy a saj´ at j´ arm˝ uflottájukat hogyan u ¨temezik, és a járm˝ uvezet˝oiket hogyan osztj´ ak be m˝ uszakokba rövid- és hossz´ utávon egyaránt. Az m´ ar ebb˝ ol a bevezet˝ob˝ol is látszik, hogy a költségek csökkentése ebben a k¨ ornyezetben egy komplexen összefonódott problémacsokor, amelynek megold´ asa glob´ alis optimalizálási módszereket igényel. Mivel mindezekre egy teljesen ¨ osszetett megk¨ ozel´ıtés megvalós´ıthatatlannak látszik, ezért olyan részproblém´ akra osztjuk a feladatot, amelyek eléggé izoláltak ahhoz, hogy ezeket a gyakorlatban kezelni tudjuk. Ezek • a buszvonalak u ´tvonaltervezése, • a menetrendtervezés, • az operat´ıv u ¨temezés. Megjegyezz¨ uk, hogy ennek ellenére a tervezési fázisok és az u ¨temezési fázisa, ha nem is szorosan, de ´ altalában mégis hatnak egymásra annak érdekében, hogy glob´ alisan hatékonyabb — vagy legalább lehetséges — megoldás legyen nyerhet˝ o. A tudom´ anyos k¨ oz¨ osség évtizedekkel ezel˝ott felismerte, hogy az operat´ıv tervezési problém´ ak optimalizált megoldása nagy kih´ıvást jelent˝o, érdekfesz´ıt˝o feladat. Ezeket a feladatokat tárgyalva sok eredmény sz¨ uletett (lásd például a [12, 13, 17, 23, 27, 54] cikkeket), amelyek k¨ ulönböz˝o modelleket és eltér˝o hatékonys´ ag´ u algoritmusokat tárgyalva foglalkoztak a témával. Hamar kider¨ ult, hogy a legt¨ obb részprobléma NP-nehéz, ami id˝oben sokszor reménytelenné teszi az optim´ alis — vagy k¨ ozel optimális — megoldások megtalálását a gyakorlatban felmer¨ ul˝ o problém´ ak esetén. Már közepes méret˝ u feladatok — például néhány sz´ azezer f˝ os lakoss´ ag´ u v´ arosok — esetén is elég összetett, komplex feladattal allunk szemben, amely még összetettebbé válik, ha a részleteket is figyelembe ´ kell venn¨ unk. Még bonyolultabbá teszi a problémát, ha olyan korlátokat is kezelni kell, amelyeket a jogszabályok, a szakszervezetek, az egyéni igények és egyéb gyakorlati feltételek határoznak meg. Ezek például a járm˝ uvezet˝ok vezetési idejére, munkaidejére, pihen˝oidejére és munkaközi sz¨ uneteire vonatkozó el˝ o´ır´ asok. Ilyen tov´ abbi korlátozó feltételeket adhatnak a telephelyek kötöttségein, kapacit´ as´ an és egyéb feltételein kereszt¨ ul más gyakorlati részletek, egészen od´ aig, hogy a vezet˝ oknél megfelel˝o mértékben legyenek vegy´ıtve a kedvelt és

3

nem kedvelt m˝ uszakok. Ehhez az utóbbihoz kapcsolódóan megeml´ıtj¨ uk, hogy péld´ aul Abbink és szerz˝ ot´ arsai 2007-ben publikált cikke [1] tárgyal egy vas´ uti m˝ uszakkioszt´ asi péld´ at. Nem célunk sem a h´ al´ ozati u ´tvonal-, sem a menetrend-tervezés tárgyalása. Mindezekhez Desaulniers [24] áttekint˝o tanulmányát javasoljuk, amely jó bevezetés, kiindul´ opont lehet ilyen jelleg˝ u problémák megoldásának tanulmányozás´ ahoz. Annak ellenére, hogy felvázoltuk a (buszos) tömegközlekedési rendszerek altal´ ´ anos strukt´ ur´ aj´ at, mi a jelen tanulmányban az operat´ıv tervezés egyes f´ azisait vizsg´ aljuk. Ezen bel˝ ul a buszflotta járm˝ uveinek u ¨temezésére, a járm˝ uvezet˝ ok m˝ uszakonkénti u ¨temezésére és beosztására fogunk koncentrálni. A munkaer˝ ou ¨temezését tov´ abbi részfeladatokra bontjuk: k¨ ulön fejezetben tárgyaljuk a j´ arm˝ uvezet˝ ok u ¨temezését és a m˝ uszakok kiosztását a járm˝ uvezet˝ok között. A cikk felép´ıtése a k¨ ovetkez˝o. Mint látni fogjuk, a legutóbbi id˝okig kidolgozott elj´ ar´ asok a két u ¨temezési problémát egymás után végrehajtva oldják meg. A j´ arm˝ uu ¨temezés eredményeire támaszkodva keresnek optimális — vagy közel optim´ alis — megold´ ast a vezet˝o-¨ utemezési feladatok megoldására. Ezért a két u ¨temezési problém´ at elv´ alasztva tárgyaljuk a második és a harmadik fejezetben. Azonban azt is l´ atni kell, hogy ma már egyre nagyobb teret nyernek azok a megk¨ ozel´ıtések, amelyek a járm˝ u- és vezet˝o-¨ utemezési problémát egy¨ utt kezelik, és egyszerre pr´ ob´ alj´ ak megoldani. Figyelembe véve az algoritmusokban bek¨ ovetkez˝ o jav´ıt´ asokat és a hardverek rohamosan növekv˝o szám´ıtási kapacitás´ at, nem kétséges, hogy ezek a módszerek is hamarosan beép¨ ulnek az u ´jonnan kifejlesztend˝ o interakt´ıv rendszerekbe. Ezért k¨ ulön fejezetet szentel¨ unk a napjainkban kibontakoz´ o hatékony integrált modellek kidolgozására szolgáló kutat´ asok ´ attekintésének. A k¨ ovetkez˝ o fejezetekben el˝oször általánosan — moduláris szerkezetben — vizsg´ aljuk a feladatokat, majd alfejezetenként részletesen tárgyaljuk az ismert megold´ asi m´ odszereket.

2. 2.1.

A j´ arm˝ uu ¨ temez´ esi feladat A feladatr´ ol ´ altal´ aban. Defin´ıci´ ok, jel¨ ol´ esek

A j´ arm˝ u-¨ utemezési problémánál (Vehicle Scheduling Problem, VSP) adott a j´ arm˝ uflotta j´ arm˝ uveinek és a menetrendi j´ aratoknak ahalmaza. Jelölje ezeket rendre két halmaz, V = {v1 , v2 , . . . , vm∗ } és U = {u1 , u2 , . . . , un∗ }. Egy V halmazba tartoz´ o minden v ∈ V járm˝ u azonos t´ıpusba tartozik (pl. alacsony padlós és g´ az¨ uzem˝ u). Ha t¨ obb — eltér˝o t´ıpus´ u — járm˝ uv¨ unk van, akkor a járm˝ uvek halmaz´ at diszjunt Vi (i = 1, . . . , k) részhalmazokra bontjuk. Jelölje továbbá ci,j azt a k¨ oltséget, amivel az i járm˝ u a j járat által el˝o´ırt tevékenységet elvégzi. A feladat az, hogy a j´ arm˝ uflotta elemeit rendelj¨ uk hozzá az egyes járatokhoz u ´gy, hogy a hozz´ arendelés o¨sszköltsége minimális legyen. Az els˝o pillanatban egyszer˝ u hozz´ arendelési feladatnak t˝ un˝o probléma azért bonyolódik meg, mert nem kell minden j´ arm˝ uvet j´ arathoz rendelni, és egy járm˝ u — a járatok id˝obeli

4

1. ´ abra. 6 j´ aratot ´ abr´ azol´ o sematikus feladat. A szaggatott nyilak jelzik az egym´ assal kompatibilis j´ aratokat. Az ábra jobb oldali része azt illusztrálja, hogy a feladat 3 j´ arm˝ uvel megoldható. eltol´ od´ asa miatt — t¨ obb j´ arathoz is hozzárendelhet˝o. További korlátozó feltételt jelenthet az, hogy minden j´ aratot pontosan egyszer kell végrehajtani, és — esetleg tov´ abbi feltételek alapj´ an — minden járm˝ u legyen képes végrehajtani azokat a j´ aratokat, amelyekhez a megoldásunk során hozzárendelt¨ uk. Minden ui ∈ U menetrendi járatra adott a járat dt(ui ) indul´ asi ideje és at(ui ) érkezési ideje, valamint dg(ui ) indul´ asi és ag(ui ) érkezési f¨ oldrajzi helye. Az ui és az uj j´ aratot kompatibilisnek (ebben a sorrendben egymás után végrehajthatónak, ¨ osszef˝ uzhet˝ onek) nevezz¨ uk, ha ugyanaz a járm˝ u képes kiszolgálni egymás ut´ an ˝ oket, azaz at(ui ) ≤ dt(uj ), és dt(uj )−at(ui ) kisebb, mint a dg(uj ) és ag(ui ) k¨ ozti t´ avols´ ag megtételéhez sz¨ ukséges id˝o. Az 1. és a 2. ábra egy-egy, néhány j´ aratb´ ol ´ all´ o sematikus szituációt mutat. A sematikus ábrákon szaggatott nyilak jelzik a kompatibilis j´ aratpárokat (itt a v´ızszintes tengely reprezentálja az id˝ ot, a f¨ oldrajzi helyek nincsenek ábrázolva), csak akkor köt¨ unk össze szaggatott ny´ıllal két j´ aratot, ha egym´ assal kompatibilisek. Az 1. ábrán jelzett sematikus szitu´ aci´ oban ilyen m´ odon 3 járm˝ u elég a 6 járat ellátásához, m´ıg a 2. ábráén ehhez m´ ar 4 j´ arm˝ u kell. Az u ¨temezési id˝ oszak kezdetén a járm˝ uvek dep´ okban állnak, és az u ¨temezési id˝ oszak végén oda is térnek vissza. Depóba ker¨ ulhet egy járm˝ u az u ¨temezési id˝ oszak b´ armely id˝ opontj´ aban, ha hosszabb ideig nem rendel¨ unk hozzá járatot. Dep´ o lehet gar´ azs, parkol´ ohely vagy telephely, attól f¨ ugg˝oen, hogy a járm˝ u hol parkol. A dep´ ok sz´ am´ at´ ol f¨ ugg˝ oen beszélhet¨ unk egydepós (Single Depot Vehicle 5

2. ´ abra. Az 1. ´ abr´ aéhoz hasonló sematikus szituáció, de itt az ottaninál kevesebb j´ arat kompatibilis egym´ assal, ´ıgy ez a feladat csak 4 járm˝ uvel oldható meg. Scheduling Problem, SDVSP) és többdepós (Multiple Depot Vehicle Scheduling Problem, MDVSP) j´ arm˝ u-¨ utemezési feladatról. A többdepós esetben az is el˝ o lehet ´ırva, hogy melyik j´ aratot melyik depókhoz tartozó járm˝ uvek hajthatják végre. A menetrendi j´ aratokon k´ıv¨ ul, amelyek száll´ıtanak utast, megk¨ ulönböztet¨ unk olyan j´ aratokat is, amelyek nem száll´ıtanak utast. Ekkor beszél¨ unk rezsij´ aratr´ ol. Ez ut´ obbiak k¨ ozé tartozik a depóból történ˝o ki- és beállás, valamint két kompatibilis menetrendi járat esetén az els˝o járat érkezési és a második járat indul´ asi f¨ oldrajzi helye k¨ oz¨ otti átállás. Egy j´ arm˝ uu ¨temezése j´ aratoknak egy olyan lánca, amelyben minden egymást ´ k¨ ovet˝ o két menetrendi j´ arat egymással kompatibilis. Altal´ aban egy járm˝ uu ¨temezése a gyakorlatban egy járm˝ u egy napi munkájának el˝o´ırását jelenti, amit j´ arm˝ um˝ uszaknak (szaksz´ oval járm˝ ufordának vagy eszközfordának) is nevez¨ unk. A j´ arm˝ u egy érvényes u ¨temezése egy kiállási járattal kezd˝odik, és egy beállási j´ arattal végz˝ odik. A 3. ´ abra a 2. ábrának megfelel˝o sematikus szituáció egy érvényes j´ arm˝ u-¨ utemezésekké kib˝ov´ıtett megoldását mutatja. Itt feltett¨ uk, hogy egy dep´ o van (egydep´ os eset), és a depóból valamennyi járat indulási helyére és érkezési helyér˝ ol a dep´ oba vezetnek depókiállási és -beállási járatok). A j´ arm˝ uu ¨temezés alapfeladata abból áll, hogy adjuk meg a járm˝ uflotta járm˝ uveinek u ¨temezését a fenti módon u ´gy, hogy minden egyes menetrendi járat hozz´ a legyen rendelve pontosan egy járm˝ uu ¨temezéséhez, és minden menetrendi j´ arat a megfelel˝ o dep´ ok valamelyikéb˝ol legyen végrehajtva. (Természetesen lehetnek olyan j´ arm˝ uvek is, amelyek az adott, pl. egy napi u ¨temezésben nem 6

3. ´ abra. A 2. ´ abr´ an l´ athat´ o sematikus szituáció megoldása egy depó esetén a dep´ o ki- és be´ all´ asi j´ aratokkal érvényes járm˝ u-¨ utemezéseket alkot. vesznek részt.) Célf¨ uggvényként kezelhetj¨ uk az u ¨temezésben használt járm˝ uvek sz´ am´ anak a minimaliz´ al´ as´ at, de definiálható más költségf¨ uggvény is. A cél akkor a k¨ oltségf¨ uggvény minimalizálása. Ha a költségf¨ uggvény a teljes u ¨temezés költségét reprezent´ alja, akkor tartalmaznia kell az egyes depókhoz tartozó átalányk¨ oltséget, valamint operat´ıv költséget is. Az átalányköltségen azt a költséget értj¨ uk, amely abb´ ol keletkezik, hogy egy adott járm˝ u a depóban rendelkezésre all. Ez lehet a beszerzési, fenntartási, karbantartási, stb. költségekb˝ol vet´ıtett ´ atlag. Az operat´ıv k¨ ´ oltség ´ altalában a megtett távolságokkal arányos, azonban k¨ ul¨ onb¨ oz˝ o lehet att´ ol f¨ ugg˝ oen, hogy melyik depóból származó járm˝ u látja el az adott feladatot. A j´ aratok operat´ıv költsége attól is f¨ ugghet, hogy rezsi- vagy menetrendi j´ aratr´ ol van-e sz´ o, mivel k¨ ulönböz˝o lehet a kilométerek egységára”. ” T¨ obb modell képes u ´gynevezett depókapacitási korlátozó feltételek kezelésére is, azaz lehetséges megold´ asnak csak olyan megoldásokat tekint, amely figyelembe veszi minden dep´ o esetén az ahhoz tartozó járm˝ uvek maximális számát. A célf¨ uggvényben az u ¨temezett járm˝ uvek általános (pl. a fenntartási költségekb˝ ol ad´ od´ o) és utaz´ asi (menetrendi- és rezsijáratainak) költségei szerepelnek. Némileg k¨ onny´ıti a feladatot, hogy mint eml´ıtett¨ uk a költség második komponense ´ altal´ aban a megfelel˝o u ´t hosszával arányos, ugyanakkor a menetrendi j´ aratok és a rezsij´ aratok kilométereihez eltér˝o költségek is tartozhatnak. Természetesen a rezsij´ aratok költségei ´ıgy f¨ uggenek a megfelel˝o földrajzi helyek k¨ oz¨ otti t´ avols´ agokt´ ol, k¨ ovetkezésképpen eltér˝o lehet a rezsijáratok költsége attól f¨ ugg˝ oen, hogy egy adott menetrendi járat mely másik járatot követ. T¨ obb alapvet˝ o matematikai modell létezik k¨ ulönböz˝o (SDVSP, MDVSP) feladatok megold´ as´ ara, amelyeket az el˝oz˝o évtizedekben dolgoztak ki. A következ˝o

7

4. ´ abra. Az 1. ´ abr´ an l´ athat´ o sematikus szituációhoz tartozó páros gráf Bertossi és szerz˝ ot´ arsai SDVSP-modelljében [12]. A folytonos, vastagabb vonallal rajzolt élek az E1 élhalmazt, a szaggatott, vékonyabb vonallal rajzolt élek az E2 élhalmazt ´ abr´ azolj´ ak itt. alfejezetekben ´ attekintj¨ uk a feladatok néhány alapvet˝o megoldási módszerét. A napjainkban tal´ an legszélesebb kör˝ uen használt MDVSP-modellekben a probléma egy egészérték˝ u t¨ obbtermékes hálózati folyam problémaként fogalmazódik meg (l´ asd [13, 48, 54]). Ebben a modellben az optimális u ¨temezést egy egészérték˝ u line´ aris programoz´ asi feladat megoldásaként szám´ıthatjuk ki. A probléma megfogalmazhat´ o halmazlefedési vagy halmazparticionálási feladatként is (lásd péld´ aul [43, 63]).

2.2.

Az egydep´ os j´ arm˝ uu ¨ temez´ esi feladat

Az SDVSP problém´ ara adott els˝o megoldási módszert Saha [64] publikálta. Az U j´ arathalmaz elemeire egy részleges rendezést definiál, és bevezetésre ker¨ ul egy β rendezési rel´ aci´ o, mely szerint akkor szolgálható ki u2 legálisan u1 után, ha ag(u1 ) = dg(u2 ), valamint at(u1 ) ≤ dt(u2 ). A megkötésekb˝ol látható, hogy ez a modell nem engedélyezi a k¨ ulönböz˝o járatok között végrehajtott rezsimeneteket, ´ıgy az itt meghat´ arozott β reláció a fent definiált kompatibilitásnál gyengébb. Az SDVSP-re t¨ obb p´ aros gráfon alapuló modellt is publikáltak. Ezekr˝ol b˝ ovebb ´ attekintés tal´ alhat´ o Bunte és Kliewer [16] munkájában. Mi az alábbiakban Bertossi és t´ arsai [12] modelljét és megoldását ismertetj¨ uk, ahol szintén p´ aros´ıt´ asi problémaként modellezik a feladatot. Vegy¨ unk egy G = (G1 , G2 , E) teljes p´ aros gr´ afot, ahol G1 és G2 cs´ ucshalmazok, ahol minden i ∈ G1 cs´ ucs egy-egy j´ arat érkezésének (érkezési földrajzi helyének), m´ıg minden j ∈ G2

8

cs´ ucs egy-egy j´ arat indul´ as´ anak (indulási földrajzi helyének) felel meg. E jelöli az élhalmazt, valamint |G1 | = |G2 | = |U | = n∗ , és |E| = (n∗ )2 . Tegy¨ uk fel tov´ abb´ a, hogy E két E1 és E2 részhalmazra osztható, amelyek: E1 = {(i, j) | ui és uj kompatibilis járatpár}, E2 = E \ E1 . A fenti gr´ af a k¨ ovetkez˝ o módon értelmezhet˝o (lásd a 4. ábrán egy egyszer˝ u, sematikus feladat illusztr´ aci´ oját). Az (i, j) ∈ E1 élek két kompatibilis ui és uj j´ arat érkezési és indul´ asi f¨ oldrajzi helyei közti lehetséges rezsijáratot jelképezik, m´ıg minden (i, j) ∈ E2 él két egymás utáni rezsijáratnak felel meg, ezek köz¨ ul az els˝ o az ui j´ arat érkezési f¨ oldrajzi helyér˝ol a depóba, majd a másik a depóból az uj j´ arat indul´ asi f¨ oldrajzi helyére. Ezek seg´ıtségével látható, hogy a G gráf egy M teljes p´ aros´ıt´ asa egy lehetséges járm˝ uu ¨temezést fog adni, melyben a járm˝ uvek sz´ ama |M ∩ E2 |. Az (i, j) élekhez ci,j k¨ oltségeket rendelve az SDVSP feladata megfeleltethet˝o egy minim´ alis k¨ oltség˝ u teljes páros´ıtás keresésének a G gráfban. • Ha ci,j = 1 minden (i, j) ∈ E2 esetén, és ci,j = 0 egyébként, u ´gy a feladat megold´ as´ aval megkapjuk a járatok teljes´ıtéséhez sz¨ ukséges minimális eszk¨ ozsz´ amot. • Ha ci,j értékei az adott rezsijáratok végrehajtásához sz¨ ukséges költségek lesznek, akkor a feladat megoldása a minimális operat´ıv költséget adja. Természetesen az el˝ obbi k¨ oltségek valamely kombinációja is használható. A gyakorlati életben a probléma kiegész¨ ul még a járm˝ uvek darabszámára adott korl´ attal. Legyen ez a korlát k. Ekkor egy korlátos páros´ıtási feladatot kapunk, ahol a feladat a minimális költség˝ u páros´ıtást megkeresni a gráfban az |M ∩ E2 | ≤ k feltétel mellett. A probléma formálisan a következ˝oképpen adhat´ o meg: legyen x bin´ aris változók vektora, ahol xi,j = 1, ha az (i, j) él az M p´ aros´ıt´ ashoz tartozik, k¨ ulönben xi,j = 0, és legyen c a költségvektor. Az X lehetséges megold´ asok halmazát az alábbi feltételeknek megfelel˝o vektorok hat´ arozz´ ak meg: X xi,j = 1, i = 1, 2, . . . , n∗ , j

X

xi,j = 1, j = 1, 2, . . . , n∗ ,

i

X

xi,j ≤ k.

(i,j)∈E2

A célf¨ uggvény min(i,j) {cx | x ∈ X,

xi,j ∈ {0, 1}}.

A fenti feladat minim´ alis k¨ oltség˝ u hálózati folyamproblémaként is megoldható (l´ asd [16]). A h´ al´ ozat konstruálása ekkor annyiban tér el a fent definiált gráftól, 9

hogy tov´ abbi cs´ ucsokat és éleket vezet¨ unk be: a járatokat jelz˝o cs´ ucsokat a h´ al´ ozatban kettébontjuk a j´ arat indulását és a járat érkezését reprezentáló cs´ ucsra, melyeket egy, a j´ aratot jelz˝o éllel köt¨ unk össze. Ezeknek a járat-éleknek az als´ o és fels˝ o korl´ atja is 1 lesz, ´ıgy biztos´ıtva azt, hogy minden járat pontosan egy alkalommal ker¨ ulj¨ on teljes´ıtésre. Ennek az a következménye, hogy az ezeken az éleiken felmer¨ ul˝ o k¨ oltségek egy konstans többletként jelentkeznek, ami a feladat célf¨ uggvényére nincs hat´ assal. A járatok cs´ ucsaihoz hasonlóan a depót jelképez˝o cs´ ucs helyett is egy dep´ o-indulási, illetve depó-érkezési cs´ ucsot vezet¨ unk be. Ezeket egy 0 k¨ oltség˝ u éllel k¨ otj¨ uk össze, mely a hálózat depó-körfolyam éle lesz. Ha a fentiek szerint korl´ atozzuk a rendelkezésre álló eszközök számát, u ´gy ennek az élnek a kapacit´ asa k lesz. Ezt a fajta formalizmust használva Ahuja és munkat´ arsai bebizony´ıtott´ ak, hogy a feladat er˝osen polinomiális id˝oben megoldhat´ o [3].

2.3.

A t¨ obbdep´ os j´ arm˝ uu ¨ temez´ esi feladat

A j´ arm˝ u-¨ utemezési feladat megoldására leggyakrabban használt modell az u ´gynevezett t¨ obbdep´ os j´ arm˝ uu ¨temezési probléma (Multiple Depot Vehicle Scheduling Problem, MDVSP) modellje. A valós életben a k¨ ulönböz˝o menetrendi j´ aratokra és a j´ arm˝ uvekre speciális igények vonatkozhatnak. Az eltér˝o járm˝ ut´ıpusok, valamint a j´ arm˝ uvek tartózkodási helye alapján a járm˝ uveket k¨ ulönböz˝o dep´ okba oszthatjuk, ´ıgy a j´ aratok kiszolgálása — az igényekt˝ol f¨ ugg˝oen — k¨ ul¨ onb¨ oz˝ o dep´ okb´ ol t¨ orténhet. A t¨ obbdep´ os j´ arm˝ u-¨ utemezési problémát Bodin és szerz˝otársai definiálták [13], majd Bertossi és szerz˝ otársai mutatták meg róla, hogy NP-nehéz feladat [12]. A modell értékét az adja, hogy tartalmazza a valós életbeli járm˝ u-¨ utemezési probléma legfontosabb komponenseit. A matematikai modellek ismertetése sor´ an jel¨ oléseinkben a L¨ obel által használt terminológiát követj¨ uk [54]. A t¨ obbdep´ os j´ arm˝ uu ¨temezési feladatnál minden menetrendi járat esetén a felhaszn´ al´ o megadja azokat a depókat, ahonnan az adott járat kiszolgálható. A gyakorlatban ez jelentheti például azt, hogy bizonyos járatok csak csuklós busszal l´ athat´ ok el, és az is megadható, hogy mely esetben mely telephelyhez tartozzanak. Ezeket az el˝ o´ırásokat a telephely és az állomás elhelyezkedése, valamint a forgalom jellemz˝ oi határozhatják meg. A k¨ ovetkez˝ okben az MDVSP k¨ ulönböz˝o megoldási technikáit mutatjuk be. Ezek egy része t¨ obbtermékes folyamproblémára vezeti vissza a feladatot, és egészérték˝ u programoz´ asi (IP) feladatként oldja meg azt. A k¨ ulönbség az alapul szolg´ al´ o h´ al´ ozat felép´ıtésének a módszerében rejlik. Ezek alapján megk¨ ulönböztet¨ unk kapcsolatalap´ u és az id˝o-tér hálózati modellt. Egy másik megközel´ıtésben a problém´ at halmazparticionálási illetve halmazlefedési feladatként modellezik. Ezt a modellt elemezték például Ribeiro és Soumis [63], vagy Hadjar és szerz˝ ot´ arsai [43].

10

2.3.1.

A kapcsolatalap´ u t¨ obbterm´ ekes h´ al´ ozati modell

A kapcsolatalap´ u t¨ obbtermékes hálózati folyam (connection-based multicommodity network flow) modell széleskör˝ uen használt az MDVSP probléma megold´ as´ ara. Sok, a tém´ aba v´ ag´ o kutatás fókuszált ennek alkalmazására. Intenz´ıven tanulm´ anyozt´ ak a gener´ alt egészérték˝ u programozási feladat megoldási módszereinek fejlesztésében rejl˝ o lehet˝oségeket. Számos megközel´ıtés alapul heurisztikus, k¨ ozel´ıt˝ o m´ odszerekre (lásd [23, 54, 57]), m´ıg mások pontos megoldást szolg´ altat´ o, egzakt algoritmusokat tárgyaltak (lásd [49, 55]). Miel˝ ott r´ atér¨ unk a modell le´ırására, a korábban bevezetett jelölések mellé u ´j defin´ıci´ okat is meg kell adnunk. Jelölje D a depók halmazát, és Du ⊆ D egy u menetrendi j´ arat dep´ ohalmazát: ez azokat a depókat tartalmazza, amelyekb˝ol ki lehet kiszolg´ alni az u j´ aratot. Jelölje Ud ⊆ U azoknak a járatoknak a halmaz´ at, amelyek kiszolg´ alhatók a d depóból. Hasonlóan, minden d ∈ D esetén defini´ alunk két, dt(d) és at(d) – depó-indulási és depó-érkezési – cs´ ucspontot a h´ al´ ozatban; ezek szimbolizálják azt, hogy a járm˝ u a d depóból indul, és oda érkezik vissza. A h´ al´ ozat cs´ ucspontjainak N halmazát ezek után a következ˝o m´ odon defini´ aljuk N = {dt(u) | u ∈ U } ∪ {at(u) | u ∈ U } ∪ {dt(d) | d ∈ D} ∪ {at(d) | d ∈ D}. A h´ al´ ozat éleinek defin´ıci´ oj´ ahoz vezess¨ uk be a következ˝o jelöléseket. Egy d dep´ ohoz tartoz´ o menetrendi j´ aratok halmazához rendelj¨ uk a következ˝o irány´ıtott éleket: Ed = {(dt(u), at(u))|u ∈ Ud }, ∀d ∈ D. Rendelj¨ unk ir´ any´ıtott élet a d depó minden u járatának érkezési idejét reprezent´ al´ o cs´ ucsb´ ol az u-val kompatibilis — szintén d-beli — járatok indulási id˝ opontj´ ahoz rendelt cs´ ucsba: Bd = {(at(u), dt(u0 )) | u, u0 ∈ Ud kompatibilis járatok}, ∀d ∈ D. Bd élei rezsij´ aratok. Tov´ abbi, a d depóhoz tartozó nem-menetrendi járatok, amelyekhez éleket kell rendelni a hálózatban alkotják a depóhoz tartozó kiállási és be´ all´ asi élek halmaz´ at: Rd = {(dt(d), dt(u)), (at(u), at(d)) | u ∈ Ud }, ∀d ∈ D. Ha korl´ atot szeretnénk el˝ o´ırni az egyes depókban rendelkezésre álló járm˝ uvek sz´ am´ ara, akkor sz¨ ukség¨ unk van az u ń. dep´ o-k¨ orfolyam” élek halmazának defi” ni´ al´ as´ ara is: Kd = {(at(d), dt(d))}, ∀d ∈ D. Ezek alapj´ an meg tudjuk adni a hálózat d depóhoz tartozó éleinek a halmaz´ at: Ad = Ed ∪ Bd ∪ Rd ∪ Kd , ∀d ∈ D, és a gr´ af ¨ osszes éleinek a halmaza E = ∪d∈D Ad . 11

5. ´ abra. A kapcsolatalap´ u modell hálózata egy kétdepós feladat példája esetén. (A f¨ oldrajzi helyek mellett ezen az ábrán az indulási és érkezési id˝opontokat sem reprezent´ aljuk, de csak azokat a cs´ ucsokat kötj¨ uk össze éllel, ahol a megfelel˝o j´ aratok kompatibilisek.) A kapcsolatalap´ u modell hálózatának felép´ıtését az 5. ábra szemlélteti. Ezen el˝ okész¨ uletek ut´ an most már készen állunk arra, hogy definiáljuk az MDVSP feladatot a G = (N, E) hálózaton. Ehhez definiálunk egy egészérték˝ ux vektort, amely egy t¨ obbtermékes folyamként is tekinthet˝o. A vektor dimenziója megegyezik a h´ al´ ozat éleinek számával. A vektor e ∈ E élhez tartozó kompoolj¨ uk, ha az e él a d depóhoz tartozik (e ∈ Ad ). Az xde komponens nensét xde -vel jel¨ értéke egy adott u ¨temezésben 1 lesz, ha az adott él benne van az u ¨temezésben, k¨ ul¨ onben 0. Ez al´ ol csak a depó-körfolyam élek a kivételek, mert azok többször is szerepelhetnek egy u ¨temezésben. Az x vektor seg´ıtségével olyan korlátozó feltételeket definiálunk, amelyek a feladat k¨ ovetelményeit biztos´ıtják. A k¨ ovetkez˝ o els˝ o feltétel azt biztos´ıtja, hogy minden menetrendi járatot pontosan egyszer hajtsunk végre. Ez azt jelenti, hogy egy lehetséges megoldásban csak olyan j´ arm˝ uu ¨temezések szerepelhetnek, amelyeknek — a depó-körfolyam élekt˝ ol eltekintve — nincs k¨ ozös él¨ uk. Ezt a következ˝o feltételekkel érhetj¨ uk el: X xde = 1, ∀u ∈ U. d∈Du ,e=(dt(u),at(u))∈Ed

Biztos´ıtanunk kell azt is, hogy az u ¨temezési id˝oszak végére minden járm˝ u viszsza´ alljon egy dep´ oba. Ez m´ as megfogalmazásban azt jelenti, hogy ha egy adott dep´ ohoz tartoz´ o j´ arm˝ u egy — depótól eltér˝o valamelyik — cs´ ucsra (állomásra)

12

megérkezik, azt el is kell hagynia. X X xde = 0, xde − e∈n+

∀u ∈ U, ∀n ∈ N,

e∈n−

ahol n+ jel¨ oli az n ∈ N cs´ ucsból induló élek halmazát, és hasonlóan, n− az n ∈ N cs´ ucsba fut´ o élek halmaza. Ha vannak dep´ okapacit´ ast korlátozó feltételek, akkor azokat a depó-körfolyam élekhez kell kapacit´ asként, vagyis a folyamértékre vonatkozó fels˝o korlátként el˝ o´ırni. Ez azt jelenti, hogy ha kd a d depóhoz tartozó azonos t´ıpus´ u buszok sz´ ama, akkor a feltételrendszerhez hozzá kell adni az xdat(d),dt(d) ≤ kd feltételt. B´ armely, a fenti feltételeket kielég´ıt˝o folyam a feladat egy lehetséges megold´ asa lesz. Amennyiben optim´ alis megoldást szeretnénk kapni, definiálnunk kell egy célf¨ uggvényt, amelynek a fenti feltételeket kielég´ıt˝o optimális megoldását keress¨ uk. Ez az élekhez nemnegat´ıv, valós érték˝ u s´ ulyokat rendelve történhet. Az él s´ ulya az adott j´ arat költségét reprezentálja. Amennyiben egyszer˝ uen a j´ arm˝ uvek sz´ am´ at szeretnénk minimalizálni (ekkor a flottaminimalizálási feladatnak nevezett problém´ ar´ ol van szó), akkor a kiállási élekhez a többi él költségéhez viszony´ıtva nagyon nagy s´ ulyokat kell rendelni. Ha ce jelöli az e élhez rendelt k¨ oltséget, akkor a feladat célf¨ uggvénye: X min ce x e . e∈E

Ez a fenti korl´ atoz´ o feltételekkel egy¨ utt tekintve egy egészérték˝ u programozási feladatot hat´ aroz meg, amelynek megoldása — bizonyos értelemben — rutinfeladat. Ennek megold´ as´ aval kapcsolatban a legf˝obb felmer¨ ul˝o probléma az, hogy a h´ al´ ozatnak t´ ul sok éle lehet. Gondoljunk csak egy több ezer menetrendi járatot tartalmaz´ o h´ al´ ozatra. Ez már egy közepes, néhány százezer lakos´ u városnál is el˝ ofordulhat, és egy ilyen esetben a lehetséges rezsiátmenetek száma milliós nagys´ agrend˝ u is lehet. Ennek az oka az, hogy a kapcsolatalap´ u hálózat minden élt tartalmaz, ahol ak´ ar csak elméletileg is lehetséges (rezsi)átmenet (az adott két j´ arat elméletileg kompatibilis egymással). A végs˝o megoldásba ezeknek ugyan csak egy csekély h´ anyada ker¨ ul be, de nem lehetséges ezek elhagyása, mert azzal esetleg elvesz´ıthetj¨ uk a feladat optimális megoldását is. 2.3.2.

Az id˝ o-t´ er h´ al´ ozati modell

Az élek sz´ am´ anak cs¨ okkentése egy u ´j, módos´ıtott modellel történhet. Ezt tárgyaljuk a k¨ ovetkez˝ okben. Az id˝ o-tér h´ al´ ozati (time-space network, TSN) modellt Kliewer és szerz˝ ot´ arsai vezették be [48] köz´ uti közösségi közlekedési feladatok kapcs´ an. Annak ellenére, hogy az id˝o-tér modellt légiközlekedési feladatoknál

13

(rep˝ ul˝ oj´ aratok u ¨temezésénél) már használták korábban (lásd pl. [44]), a járm˝ uu ¨temezés ter¨ uletén [48] az els˝o id˝o-tér módszert tárgyaló publikáció. A modell f˝ o v´ıvm´ anya, hogy nagyobb méret˝ u, a gyakorlatban el˝oforduló problém´ akat is meg lehet vele oldani. A modell két dimenzi´ ot használ, ezek az id˝o és a tér. A tér szó jelentése itt az, hogy melyik f¨ oldrajzi helyr˝ol (állomásról) van szó, m´ıg az id˝ot id˝ovonalak reprezent´ alj´ ak, amelyek egyes állomásokhoz (földrajzi helyekhez) tartoznak. Az id˝ ovonalak az indul´ asi és érkezési id˝opontokat tartalmazzák. Minden egyes allom´ ´ ashoz tartozik egy id˝ ovonal, és az állomás minden lehetséges indulási és érkezési id˝ opontj´ ahoz egy cs´ ucspontot definiálunk annak id˝ovonalán. (Ha t¨ obb, k¨ ul¨ onb¨ oz˝ o j´ arat indul´ asi vagy érkezési id˝opontja egybeesik, azokhoz egy osszevont” cs´ ¨ ucspont tartozik.) Könny˝ u észrevenni, hogy a két modell közötti ” alapvet˝ o k¨ ul¨ onbség az, hogy az id˝opontok itt helyekhez vannak kötve. Így a h´ al´ ozat N cs´ ucshalmaz´ at az állomásokhoz tartozó indulási és érkezési id˝opontok adj´ ak. Minden d ∈ D dep´ o esetén hasonlóan definiálhatjuk Ed -t, mint a kapcsolatalap´ u modellben. Természetesen a depókhoz is id˝ovonalakat adunk meg, ´ıgy hasonl´ oan defini´ alhat´ o Rd is. A legf˝ obb k¨ ul¨ onbség azonban a két modell között a rezsijáratok defin´ıciój´ aban rejlik. Az id˝ o-tér h´ al´ ozati modellben ugyanis az id˝ovonalak használatával lehet˝ oség ny´ılik arra, hogy összegy˝ ujts¨ uk”, összevonjuk több rezsijáratnak ” a lehetséges folyam´ at. Így nem feltétlen¨ ul sz¨ ukséges minden egyes lehetséges rezsij´ aratot k¨ ul¨ on éllel reprezentálni, hanem megfelel˝o rezsiátmenetekhez tartoz´ o éleket ¨ osszevonhatunk egyetlen éllé. A szerz˝ok [48]-ban az u ´gynevezett utols´ o-els˝ o egyezési stratégi´ at alkalmazták. Ennek alapgondolata egy kétfázis´ u osszevon´ ¨ asi stratégia: • Az els˝ o f´ azisban minden egyes járat érkezését jelképez˝o cs´ ucspontból az osszes t¨ ¨ obbi ´ allom´ as esetén csak a másik állomás els˝o olyan járatához vezet˝ o, rezsij´ aratot jelent˝o élt h´ uzzuk be, amely járatunkkal id˝oben az els˝ o kompatibilis j´ arat a másik állomáson. Ezen éleket nevezz¨ uk els˝o egyezésnek. Csak ezeket az éleket tekintj¨ uk a lehetséges rezsiélek köz¨ ul. • Az els˝ o f´ azis ut´ an egy adott állomásnak az indulást jelképez˝o cs´ ucspontjaiba mindegyik m´ asik ´ allomásról érkez˝o rezsijáratok köz¨ ul már csak ez els˝o egyezésnek megfelel˝ o rezsijáratokat hagytuk meg. A második fázisban tov´ abb cs¨ okkentj¨ uk ezen élek számát. Most ker¨ ul sor arra, hogy összevonjuk a beérkez˝ o rezsiéleket. A második fázisban egy adott állomás id˝opontjaihoz végignézz¨ uk az összes többi állomásról érkez˝o, els˝o egyezés éleket, és az oda egy azonos, de másik állomásról érkez˝o, els˝o egyezést jelent˝o élek k¨ oz¨ ul csak a legkés˝obb indulót hagyjuk meg. Ezt nevezz¨ uk utolsóels˝ o egyezést jelképez˝ o élnek. Elhagyva a többi, els˝o egyezést jelképez˝o élet, az élek sz´ am´ anak további csökkentése lehetséges. Ezért a Bd halmaz az ¨ osszes rezsijáratnak csak egy részét fogja tartalmazni. Ezen a m´ odon cs¨ okkenthet˝o a k¨ ulönböz˝o állomások között rezsiélek száma. Azonban, hogy teljessé tegy¨ uk a modellt, ahhoz mindegyik állomáshoz be kell vezetni az ´ allom´ ason bel¨ uli cs´ ucspontokat összeköt˝o, u ´gynevezett várakozó élek 14

6. ´ abra. Egy egyszer˝ u példa id˝o-tér hálózatra [10]. Wd halmaz´ at, minden d ∈ D depó esetén. Ezek az élek mindig az állomás id˝ ovonal´ at k¨ ovetik, éllel ¨ osszekötve az egymást követ˝o (indulási) id˝opontokat, osszegy˝ ¨ ujtve azok folyam´ at. Ebben az esetben az Ad élhalmaz defin´ıciója a k¨ ovetkez˝ o lesz: Ad = Ed ∪ Bd ∪ Rd ∪ Kd ∪ Wd , ∀d ∈ D, és a gr´ af ¨ osszes éleinek a halmaza E = ∪d∈D Ad . A 6. ´ abra mutat egy egyszer˝ u példát egy id˝o-tér hálózatra. Ebben az esetben az IP-modell a kapcsolatlap´ u modelléhez hasonló lesz. Az egyetlen k¨ ul¨ onbség, hogy t¨ obb él folyamát egyetlen élbe gy˝ ujthetj¨ uk össze, ´ıgy unk. az xde ∈ {0, 1} feltétel helyett az xde ≥ 0, xde egész” feltételt kell szerepeltetn¨ ” 2.3.3.

A halmazparticion´ al´ asi modell

Ebben az alfejezetben Ribeiro és Soumis [63] cikke alapján megadjuk a probléma egy halmazparticion´ al´ asi megfogalmazását. Az MDVSP a 2.3.1. alfejezetben megfogalmazott G gr´ afon megadott körfolyamok seg´ıtéségével u ´jrafogalmazhat´ o. Minden d ∈ D esetén legyen Hd azon G-beli p utak halmaza, amelyek dt(d)-b˝ ol indulnak, és oda is térnek vissza. Legyen [ H= Hd d∈D

az o ¨sszes G-beli ilyen utak halmaza. Minden p ∈ Hd esetén vezess¨ unk be egy ypd bin´ aris v´ altoz´ ot, amelyet a következ˝oképpen definiálunk:

15

( ypd

1, ha a p ∈ Hd u ´t szerepel a megoldásban,

= 0, k¨ ulönben.

Defini´ aljuk tov´ abb´ a ade,p -t az alábbi módon: ( 1, ha a p ∈ Hd u ´t tartalmazza az e élet, d ae,p = 0, k¨ ulönben. Legyen cp a p ∈ Hd u ´thoz rendelt költség. Ekkor a modell a következ˝oképpen fogalmazhat´ o meg. Mimimalizáljuk a X X cp ypd d∈D p∈Hd

célf¨ uggvényt a X

X

ade,p ypd = 1,

∀u ∈ U

d∈D p∈Hd ,e=(dt(u),at(u))∈Ed

és ypd ∈ {0, 1}, ∀d ∈ D, ∀p ∈ Hd feltételek mellett. Ha a d dep´ oban korl´ atos, kd szám´ u járm˝ u van, akkor ebben az esetben a feltételeket ki kell egész´ıteni a következ˝o egyenl˝otlenségekkel: X ypd ≤ kd , ∀d ∈ D. p∈Hd

2.3.4.

Heurisztikus algoritmusok

Az MDVSP-re sz´ amos heurisztikus megközel´ıtést publikáltak. Kliewer és társai egy u ń. v´ altoz´ ofix´ al´ asi (variable fixing) heurisztik´ at adnak meg [47], amely az id˝ o-tér modellen alapul. Ennek alapötlete, hogy egyszer˝ us´ıtett problémák megold´ as´ aval (az eml´ıtett cikkben k¨ ulön SDVSP problémákat oldanak meg az eredeti MDVSP minden dep´ oj´ ara) olyan járatsorozatokat találjon, melyek minden egyszer˝ us´ıtett problém´ aban egymás után következnek. Ezeket a sorozatokat lek¨ oti, és a felép´ıtend˝ o id˝ o-tér modellben egy¨ utt kezeli ˝oket. Suhl és szerz˝ ot´ arsai [69] egy kerek´ıtéses heurisztikát alkalmaztak. Módszer¨ uk alap¨ otlete, hogy az MDVSP-feladat LP-relaxációjának értéke és az optimális egész megold´ as értéke k¨ oz¨ otti k¨ ulönbség meglehet˝osen kicsi, néha nulla, és az LP-relax´ aci´ o optim´ alis megoldásában sok változó kap már egész értéket. Az algoritmus egy el˝ ore meghatározott korlát elérésekor leáll´ıtja az IP-megoldót (ez lehet a bej´ art cs´ ucsok számának korlátja, vagy az aktuális feladat értéke és az LP-relax´ aci´ o értéke k¨ oz¨ otti k¨ ulönbség), majd az ´ıgy kézben lév˝o” részmegol” d´ ason végrehajt egy kerek´ıtési algoritmust. Az algoritmus által meghatározott 16

két kerek´ıtési tartom´ any [0, rl ] és [ru , 1], ahol 0 ≤ rl ≤ ru ≤ 1. Legyen xj egy v´ altoz´ o, és xj − bxj c = fj , ahol 0 ≤ xj ≤ 1. A heuriszrtika az xj értékét az al´ abbi szab´ alyok szerint kerek´ıti: ( bxj c, ha fj ∈ [0, rl ], xj := dxj e, ha fj ∈ [ru , 1]. Egym´ as ut´ an t¨ obb kerek´ıtési iterációt is végrehajthatunk, feltéve, hogy az ´ıgy létrej¨ ott LP még mindig lehetséges megoldást ad. Ha nem tudtunk egy v´ altoz´ ot sem kerek´ıteni, akkor a kezdeti kerek´ıtési intervallumok növelhet˝ok. Az ´ıgy kapott feladatra u ´jra lefuttatjuk a korlátozás-szétválasztás módszerére alapul´ o IP-megold´ ot. A folyamatot addig ismételj¨ uk, am´ıg minden változót fix´ altunk, vagy a feladatnak nincs lehetséges megoldása. Pepin és szerz˝ ot´ arsainak dolgozata több heurisztikus módszert hasonl´ıt össze [61]. A publik´ aci´ oban ¨ ot k¨ ulönböz˝o heurisztikus megközel´ıtést vizsgálnak: • egy szétv´ alaszt´ as és v´ agás (branch-and-cut) t´ıpus´ u megoldást, • Lagrange-relax´ aci´ ora alapuló heurisztikát, • oszlopgener´ al´ ast, • egy nagy szomszéds´ agi keresést, • valamint egy tabu-keresést. A szétv´ alaszt´ as és v´ ag´ as t´ıpus´ u megoldás alkalmazásánál a feladat id˝o-tér modelljét ép´ıtik fel, majd oldják meg CPLEX-szel, m´ıg az oszlopgenerálásnál lényegében szintén CPLEX-szel kapnak eredményt. A probléma folyammegmaradási feltételének Lagrange-relaxálásával a kapott feladat SDVSP-részproblém´ akkal lesz ekvivalens, amit egy aukciós algoritmussal oldanak meg. Az ´ıgy kapott alsó korlátot szubgradiens módszerrel jav´ıtják. A nagy szomszéds´ agi keresés egy kezdeti megoldásból kiindulva minden iteráci´ oban r k¨ ul¨ onb¨ oz˝ o j´ arm˝ um˝ uszakot választ ki, több választási stratégia valamelyikével. Az ´ıgy kiv´ alasztott m˝ uszakokat u ´jraoptimalizálják, az oszlopgenerálást haszn´ alva. A v´ alaszt´ asi stratégiák valósz´ın˝ usége minden iterációban változik att´ ol f¨ ugg˝ oen, hogy az el˝ oz˝ oek mennyire voltak hatékonyak. A tabukeresés szintén egy kezdeti megoldásból indul, és minden iterációban az aktu´ alis megold´ as egy szomszédjára tér át. Kétféle módon definiálják a szomszéds´ agot: 1-mozgat´ as, és csere-mozgatás alapján. Az 1-mozgatással olyan szomszédok érhet˝ oek el, melynél a vi eszköz valamely járatát a szomszédban egy m´ asik, vj eszk¨ oz hajtja végre. A csere-mozgatás olyan szomszédokat ad, melyeknél, ha a tk j´ aratot a vi eszköz, valamint a tk0 járatot a vj eszköz hajtotta végre az eredeti u ¨temezésben, u ´gy a szomszédban a tk járatot a vj , valamint a tk0 j´ aratot a vi eszk¨ oz hajtja végre (valamely k, k 0 , i és j értékekre).

17

3.

A j´ arm˝ uvezet˝ o-¨ utemez´ esi feladat

A munkaer˝ o k¨ oltsége egy nagyon fontos, kiemelt összetev˝oje az egész operat´ıv u ¨temezés k¨ oltségének, ´ıgy a dolgozók munkájának beosztása, u ¨temezése manaps´ ag k¨ ozponti kérdés. Tipikus személyzetbeosztási alkalmazások jelennek meg a k´ orh´ azak u ¨zemeltetésénél (pl. n˝ovérek), a call-centerekben (operátorok), légit´ arsas´ agokn´ al (stewardess-ek, pilóták), és a közlekedési vállalatoknál (járm˝ uvezet˝ ok) munk´ aj´ anak u ¨temezésére. A beosztások elkész´ıtésekor a feltételek er˝osen szakmaspecifikusak, ´ıgy a problémák megfogalmazása, a modellek és megoldási m´ odszerek is meglehet˝ osen változatosak [28]. A j´ arm˝ uvezet˝ o-¨ utemezés során (amelyet röviden vezet˝ou ¨temezésnek is fogunk nevezni) adott az ell´ atandó, operat´ıv feladatok halmaza. Ezt kell olyan m´ odon m˝ uszakokba rendezni az adott id˝operiódusra (általában egy napra) vonatkoz´ oan, hogy minden feladat hozzá legyen rendelve egy m˝ uszakhoz és a m˝ uszakok minden — a j´ arm˝ uvezet˝ok számára el˝o´ırt — szabálynak megfeleljenek. A hozz´ arendelést u ´gy kell megadni, hogy eközben minimalizáljuk az u ¨temezés sor´ an kialak´ıtott m˝ uszakok költségeinek összegét. Sok olyan feltétel van, amelyet a vonatkozó jogszabályok és az adott közlekedési v´ allalat dolgoz´ oira vonatkozó szabályok, el˝o´ırások határoznak meg. Ilyenek a napi munkaid˝ o-beoszt´ asra vonatkozó szabályok, a maximális munkaid˝o és a a napi pihen˝ oid˝ o minim´ alis hossza, a kell˝o szám´ u és idej˝ u sz¨ unet el˝o´ırása egy adott vezetési id˝ o ut´ an, két munkabeosztás között kötelez˝oen el˝o´ırt pihen˝oid˝o, stb. A menetrendi j´ aratokon és a rezsimeneteken k´ıv¨ ul sokféle technikai és adminisztr´ aci´ os feladat is van, amelyeknek pontosan meghatározott id˝obeli hossza van. Ilyenek az utasok ki- és beszállási ideje a járatok végállomásain, tankolás, parkol´ as, m˝ uszakkezdet és -befejezés, stb. Megjegyezz¨ uk, hogy a vezetési id˝o és a munkaid˝ o k¨ ul¨ onb¨ oz˝ o fogalmak, ´ıgy ezekre eltér˝o szabályok vonatkozhatnak, miként arra is, hogy melyik technikai tevékenység ideje melyikbe szám´ıt bele. Ehhez j´ arulhat még hozz´ a az, hogy k¨ ulönböz˝o vállalatoknál további korlátozó fogalmak és szab´ alyok is el˝ o fordulhatnak (szolgálati id˝o, tengelyen töltött id˝o stb.). A k¨ ul¨ onb¨ oz˝ o tevékenységekhez tartozó dolgozói költségeknek (a fizetéseknek és egyéb j´ arulékoknak) megfelel˝oen az egyes feladatokhoz költségeket tudunk rendelni. Így az egyes m˝ uszakok költségeit u ´gy szám´ıtjuk ki, hogy összeadjuk a k¨ ul¨ onb¨ oz˝ o tevékenységek k¨ oltségeit. A legnépszer˝ ubb megk¨ ozel´ıtés a probléma megoldására a halmazparticionál´ as (l´ asd pl. [30]), valamint az annak relaxációját jelent˝o halmazlefedési modell (pl. [66, 73]) vizsg´ alata. A megold´ as el˝ o´ all´ıt´ asa tipikusan kétféle módon történhet: vagy a korlátoz´ o feltételeket kielég´ıt˝ o egy lehetséges megoldás el˝oáll´ıtásával [27] és annak iterat´ıvan t¨ ortén˝ o jav´ıt´ as´ aval, vagy nagyszám´ u legenerált lehetséges megoldás k¨ oz¨ ul a legjobbak kiv´ alaszt´ asával [50]. K¨ ulönböz˝o jelleg˝ u algoritmusokat alkalmaztak a probléma megold´ asára. Ezek köz¨ ul érdemes kiemelni az egészérték˝ u programoz´ asi modelleket (l´ asd pl. [72]), az evol´ uciós elvekre ép¨ ul˝o metaheurisztikus elj´ ar´ ast [50], vagy a Fuzzy-módszeren alapuló [52] algoritmusokat. A helyes modell kialak´ıt´ asát nagymértékben nehez´ıti az, hogy a k¨ ulönböz˝o 18

k¨ ozlekedési t´ arsas´ agok m´ as-más elveket, bels˝o szabályokat alkalmaznak a vezet˝ou ¨temezésnél. Ilyen lehet például annak el˝o´ırása, hogy mely pontokon (mely f¨ oldrajzi helyeken) t¨ orténhet vezet˝ocsere egy adott járm˝ uvön, ez mennyi id˝ot igényel, milyen szab´ alyok vonatkoznak a sz¨ unetekre, stb. Az ilyen k¨ ulönbségek, és a nagysz´ am´ u, nehéz korl´ atozó feltétel miatt a legtöbb megoldási módszer csak a legalapvet˝ obb korl´ atoz´ o feltételeket veszik figyelembe. Ilyen lehet például a maxim´ alis munkaid˝ o, a néh´ any rövid és egy hossz´ u (étkezési) munkaközi sz¨ unet. Egy val´ os életb˝ ol sz´ armazó példa esetén az összes sz¨ unet kezelése, u ¨temezése azonban nem egyszer˝ u: az egy m˝ uszakon bel¨ ul el˝o´ırt sz¨ unetek száma ugyanis f¨ ugghet a m˝ uszak és/vagy a már ledolgozott munkaid˝o hosszától. A munkaid˝o el˝ orehalad´ as´ aval egyre gyakrabban kell a sz¨ uneteket kiadni (általában egyre r¨ ovidebb munkaszakaszok után, de ezekre is vonatkozhatnak bonyolultabb szab´ alyok); t¨ obb k¨ ul¨ onb¨ oz˝ o variáció van a sz¨ unetek hosszára. Emellett sok szabály nem a munkaid˝ ore vonatkozik, hanem a vezetési id˝ore, és a kett˝o eltérhet egym´ ast´ ol. A munkaid˝ obe beleszámolódhatnak más, el˝o´ırt technikai id˝ok is, például a vég´ allom´ asokon t¨ ortén˝ o fel- és leszállási id˝ok [29]. A fenti korlátozó feltételeket azért soroltuk fel, hogy érzékeltess¨ uk azt, hogy mennyire bonyolult egy ilyen rendszer, és pr´ ob´ altuk felv´ azolni azt is, hogy milyen elvárásokat támasztanak egy matematikai modell elkész´ıtése és alkalmazása során az egyes felhasználók. A vezet˝ ou ¨temezés problémája központi logisztikai probléma a tömegközlekedésben, hiszen a j´ arm˝ uvezet˝okkel kapcsolatos költségek a teljes, közlekedéssel kapcsolatos k¨ oltségek nagy részét alkotják. A vezet˝ou ¨temezés alapproblémája a k¨ ovetkez˝ o m´ odon hat´ arozható meg: Adottak a járm˝ uvek közlekedései/tevékenységei, fix indul´ asi és érkezési idej¨ ukkel és hely¨ ukkel. A feladat az, hogy mindegyikhez j´ arm˝ uvezet˝ oket rendelj¨ unk minimális költséggel, átfedések nélk¨ ul, kielég´ıtve a szab´ alyokat és az el˝o´ırásokat. Ennek klasszikus matematikai megfogalmaz´ asa egy halmazlefedési problémát eredményez, amely problémáról ismert, hogy NP-teljes [37]. A vezet˝ ou ¨temezési problémára CSP-ként (Crew Scheduling Problem) fogunk hivatkozni, b´ ar az angol nyelv˝ u szakirodalomban emellett szokás Driver Scheduling Problem-nek vagy Duty Scheduling Problem-nek is nevezni. Az irodalomban sz´ amos CSP-megold´ asi módszer és alkalmazás található. A következ˝okben ezeket tekintj¨ uk ´ at r¨ oviden. Részletesebb áttekintéshez például a [28] tanulmány aj´ anlhat´ o az ez ir´ ant érdekl˝ od˝oknek.

3.1.

Modellek ´ es algoritmusok a CSP-re

Az alfejezetet az alapvet˝ o jel¨ olések összefoglalásával kezdj¨ uk. Egy olyan földrajzi helyet, ahol egy feladat (task) kezd˝odik, vagy befejez˝odik, és a vezet˝o elhagyhatja, vagy elfoglalhatja a járm˝ uvet, v´ alt´ asi helynek (relief point) nevez¨ unk. Amikor egy j´ arm˝ u egy v´ alt´ asi helyhez ér, lehetséges v´ alt´ asi pontr´ ol (relief oppurtunity) beszél¨ unk. A j´ arm˝ u két egymást követ˝o lehetséges váltási pont közötti feladatait munkaszakasznak (work piece) nevezz¨ uk. A vezet˝ou ¨temezési feladat megold´ as´ ara két ´ altal´ anos megközel´ıtés létezik.

19

3.1.1.

A Gener´ al´ as ´ es Kiv´ alaszt´ as m´ odszere

A m´ odszerre az angol elnevezés (Generate and Select) rövid´ıtése alapján GaSsel fogunk hivatkozni. GaS technikát használtak a [50, 52, 72] cikkekben. A m´ odszer a k¨ ovetkez˝ oképpen foglalható össze: A generálási lépésben áll´ıtsunk el˝ o nagysz´ am´ u szab´ alyos m˝ uszakot, majd a kiválasztási lépésben keress¨ unk egy olyan részhalmazt a gener´ alt m˝ uszakokból, amely minimális költség˝ u és lefedi a feladatokat. Az els˝ o f´ azis jelent˝ os sz´ am´ıtási id˝ot igényel. A szám´ıtási igény nagyban f¨ ugg a j´ aratok mennyiségét˝ ol, a szabályok számától és bonyolultságától. Emellett a szab´ alyok ellen˝ orzésének sz´ am´ıtási igénye is nagyban befolyásolja ennek a fázisnak — és ´ıgy az egész problémának — a komplexitását. A GaS kiv´ alaszt´ asi f´ azisa hagyományosan egy halmazlefedési vagy halmazparticion´ al´ asi feladatként fogalmazható meg. Jelölje n0 a lehetséges m˝ uszakok és m0 a feladatok sz´ am´ at, xj ∈ {0, 1} és ai,j ∈ {0, 1} az i. feladathoz és a j. m˝ uszakhoz tartoz´ o v´ altoz´ okat (i = 1, 2, . . . , m0 , j = 1, 2, . . . , n0 ), ahol ( 1, ha a j. m˝ uszakot kiválasztjuk, xj = 0, k¨ ul¨ onben. ( 1, ha az i. feladatot tartalmazza a j. m˝ uszak, ai,j = 0, k¨ ul¨ onben. Ekkor a feladat a k¨ ovetkez˝ o módon ´ırható fel: 0

min w1

n X

0

cj xj + w2

j=1

n X

xj

(1)

j=1

figyelembe véve az al´ abbi korlátozó feltételeket: 0

n X

ai,j xj ≥ 1,

i = 1, 2, . . . , m0 ,

(2)

j=1

ahol cj a j. m˝ uszak k¨ oltsége, w1 és w2 k¨ ulönböz˝o s´ ulyok. A (1) célf¨ uggvény a (2) feltételrendszerrel egy halmazlefedési feladatot gener´ al, melynél — mint az észrevehet˝o — átfedés is lehetséges. Ez azt jelenti, hogy ugyanazon feladathoz elvileg több m˝ uszak is hozzárendelhet˝o. Ebben az esetben a gyakorlatban gondoskodnunk kell az esetleges átfedések kezelésér˝ol, vagy ezek sz´ am´ anak minimaliz´ al´ as´ ar´ ol is [25, 66]. A particion´ al´ asi modell a lefedési feladat olyan megszor´ıtása, amikor átfedés nem lehetséges. Ez annyiban módos´ıtja a feltételrendszert, hogy az egyenl˝otlenségek helyett egyenl˝ oségeket ´ırunk el˝o. A probléma az, hogy ebben az esetben a lehetséges megold´ asok létezése nem garantált. Megjegyezz¨ uk, hogy mindkét feladatr´ ol bebizony´ıtott´ ak, hogy NP-nehéz [37]. A probléma megold´ as´ ara számos eljárás létezik. Például egészérték˝ u programoz´ asi m´ odszereket használnak [72]-ben, heurisztikus megoldási technikákat alkalmaznak [50]-ben. 20

3.1.2.

A Konstrukt´ıv Megk¨ ozel´ıt´ es m´ odszere

A Konstrukt´ıv Megk¨ ozel´ıtés egyetlen megoldást ép´ıt fel irány´ıtottan egy optimaliz´ al´ asi elj´ ar´ as seg´ıtségével. Ennek kerete rendszerint egy hagyományos iterat´ıv elj´ ar´ as, amely egy induló megoldást generál, és iterat´ıvan jav´ıtja azt. Ezzel a m´ odszerrel tal´ alkozhatunk a [2, 27, 40, 71] cikkekben. 3.1.3.

A szab´ alyok ellen˝ orz´ ese

A legkritikusabb részfeladat annak ellen˝orzése, hogy a kapott megoldás lehetséges megold´ as-e. Ez azt jelenti, hogy — mindkét megközel´ıtés generáló folyamata sor´ an — a megold´ ashoz tartozó összes m˝ uszakról el kell dönten¨ unk, hogy azok teljes´ıtik-e a feltételeket. Miután — még egy kisméret˝ u probléma esetén is — a lehetséges m˝ uszakok száma nagyon nagy, ezért a technikák többségénél k¨ ul¨ onb¨ oz˝ o egyszer˝ us´ıtések ker¨ ulnek végrehajtásra azért, hogy a futási id˝ot csökkentsék. Egy alkalmazott megoldás az, hogy a probléma méretét csökkentik azzal, hogy lehetséges v´ altási pontokat hagynak el, vagy azzal, hogy csak sz´ am´ıt´ asilag kezelhet˝ o sz´ am´ u m˝ uszakot generálnak le. Ezek az egyszer˝ us´ıtések természetesen befoly´ asolhatják és korlátozhatják a módszernél az optimalizálás sikerét.

3.2.

A CSP korl´ atoz´ o felt´ eteleir˝ ol

A CSP megold´ asa sor´ an a korlátozó feltételek valóban dönt˝o szerepet játszanak a megold´ asi m´ odszer szempontjából. Ezek er˝osen befolyásolják a megoldás milyenségét és a sz´ am´ıt´ asi id˝ot. Er˝os korlátozó feltételekkel rendelkez˝o valós problém´ ak esetén az egy nehéz kérdés, hogy megtalálják az egyens´ ulyt a fenti szempontok k¨ oz¨ ott. Mivel ´ altalában a probléma mérete nagy, és az el˝o´ırt szab´ alyok r¨ ogz´ıtettek, a f˝ o cél az, hogy találjunk egy hatékony módszert, amely gyakorlati szempontb´ ol j´ o min˝oség˝ u, kivitelezhet˝o megoldást ny´ ujt. A f˝ o korl´ atokat nemzetk¨ ozi (pl. EU-s szabályok) és nemzeti (minisztériumi, onkorm´ ¨ anyzati, stb.) szinten határozzák meg. A helyi közlekedési vállalat is tov´ abbi kemény” és puha” igényeket (szigor´ uan betartandó vagy ajánlott) ” ” defini´ alhat. Fontos igény a valós, gyakorlati alkalmazások mellett a rugalmasság. Sok esetben az adapt´ alhat´ oság és a futási id˝o a legfontosabb szempontok, ha a megold´ as min˝ osége megfelel bizonyos követelményeknek (általában valamilyen korl´ atoz´ o feltételeknek). Abban az esetben, ha döntéstámogató az u ¨temezés, egyes mérn¨ oki k¨ ovetelmények min˝oségére vonatkozóan a megoldást nem kell, vagy nem is lehet formaliz´ alni. Ekkor a hossz´ utáv´ u tervezés u ¨temezése interakt´ıv mechanizmusként valósul meg, azaz interakt´ıv, mérnöki beavatkozás lehetséges vagy sz¨ ukséges is. Egy módszer alkalmazásának lehet˝osége nagymértékben f¨ ugg att´ ol, hogy miként lehet a modellben a sz¨ ukséges szabályokat megfogalmazni, formaliz´ alni, milyen paramétereket képes kezelni, és ezáltal a k¨ ul¨ onb¨ oz˝ o megold´ asokat el˝ oa´ll´ıtani. Ez a rugalmass´ ag k¨ ozponti kérdés az optimalizálási folyamat többi szakasz´ ahoz val´ o viszony tekintetében is: a megoldás értékelése önmagában nem,

21

csak a j´ arm˝ uu ¨temezés valamint a vezet˝obeosztás eredményének értékelésével egy¨ utt lehetséges.

3.3.

A c´ elf¨ uggv´ enyr¨ ol

A CSP megold´ as´ anak min˝ osége csak részben f¨ ugg az eredményezett m˝ uszakok ´ sz´ am´ at´ ol. Altal´ anosabban, egy megoldás költségének a tartalmazott m˝ uszakok k¨ oltségeinek ¨ osszegét tekinthetj¨ uk. Természetesen van egy általános költsége egy j´ arm˝ uvezet˝ o foglalkoztat´ as´ anak, ezért minimalizálva az összköltséget, a vezet˝ou ¨temezés alacsony szinten fogja tartani a m˝ uszakok számát is. Másrészt, költségeket rendelhet¨ unk a m˝ uszakokhoz a benn¨ uk szerepl˝o feladatok szerint is. Ezen k´ıv¨ ul meg lehet hat´ arozni egyéb jellemz˝oket, mint például a m˝ uszak t´ıpusa, a v´ arhat´ o id˝ otartama, amelyek járulékosan, b¨ untetésként szerepelhetnek a költségben is. Mindazon´ altal, a legáltalánosabb értelemben értékelve a megoldást, a m˝ uszakok ¨ osszes munkaidejét lehet teljes költségként tekinteni. (Egyes helyeken a bérezés nem munkaid˝ o szerint történik, ilyenkor természetesen a m˝ uszak k¨ oltségét is ehhez kell igaz´ıtani.)

4.

Integr´ alt strat´ egi´ ak

Ebben a fejezetben a j´ arm˝ u- és járm˝ uvezet˝o-¨ utemezési feladat integr´ alt megk¨ ozel´ıtéseit (vehicle and crew scheduling problem, VCSP) tekintj¨ uk át röviden, megeml´ıtve az irodalomban tárgyalt legfontosabb modelleket, algoritmusokat. Az érdekl˝ od˝ oknek kiindul´ opontként a [68] cikket ajánljuk, a részletesebb elmély¨ uléshez javasoljuk a kit˝ un˝ o áttekintést adó [24] tanulmányt. A j´ arm˝ uvezet˝ o-¨ utemezés a hagyományos megközel´ıtést követve a járm˝ uu ¨temezés f´ azisa ut´ an hajt´ odik végre. (Ezért ezt szekvenci´ alis megk¨ ozél´ıtésnek is nevezz¨ uk.) Ez ´ altal´ aban hatékonyan végrehajtható, ha a váltási helyek között sok olyan van, amely megengedett váltási pont is egyben, és a kialak´ıtott járm˝ uu ¨temezés gyakran érint ilyen váltási helyet. Azonban, ha a kialak´ıtott járm˝ uu ¨temezés t´ ul s˝ ur˝ u”, sok helyen nincs elég id˝o a járm˝ uvezet˝o-váltásra, vagy a ” kialak´ıtott j´ arm˝ uu ¨temezés hossz´ u ideig nem érint megengedett váltási helyet, akkor ronthatunk az el˝ oz˝ o f´ azis eredményén, vesz´ıthet¨ unk a hatékonyságból. A j´ arm˝ uu ¨temezés és a j´ arm˝ uvezet˝o-¨ utemezés egyszerre történ˝o elvégzése emiatt indokolt lehet, és ez napjaink egyik fontos kutatási ter¨ ulete. A VCSP feladata a k¨ ovetkez˝oképpen fogalmazható meg. Adott menetrendi j´ aratok egy halmaza, adott a járm˝ uflotta, melynek járm˝ uvei k¨ ulönböz˝o depókhoz tartoznak, adottak tov´ abb´ a a járm˝ uvezet˝okre vonatkozó szabályok. A feladat a j´ arm˝ uveknek és a j´ arm˝ uvezet˝oknek olyan érvényes u ¨temezését adni, hogy az valamennyi — j´ arm˝ ure és j´ arm˝ uvezet˝ore — vonatkozó szabálynak megfeleljen, és minim´ alis k¨ oltség˝ u legyen. Ez a feladat egy, az MDVSP-hez hasonló egészérték˝ u programozási feladatként fel´ırhat´ o, kib˝ ov´ıtve olyan feltételekkel, amelyek egyrészt a vezet˝ou ¨temezésnek felelnek meg, m´ asrészt pedig kapcsolatot teremtenek a két u ¨temezés között.

22

Ekkor a célf¨ uggvényben is a két u ¨temezés költségének összege jelenik meg (lásd pl. [24]). Mint kor´ abban l´ attuk, az MDVSP és a VCSP feladat kapcsán is elmondhatjuk, hogy mindkett˝ o NP-nehéz feladat. A k¨ ovetkez˝ oekben ismertetett módszerek esetén néhánynál a járm˝ uu ¨temezés részfeladata egydep´ os, és ´ıgy polinomiális id˝oben megoldható [13]. A VCSP feladat´ aban a lehetséges m˝ uszakok száma igen nagy, k¨ ulönösen ´ a t¨ obbdep´ os esetben. Eppen ezért az 1990-es évek végéig nem övezte akkora érdekl˝ odés a problém´ at a kutatók körében, mint a járm˝ u-¨ utemezési vagy j´ arm˝ uvezet˝ o-¨ utemezési problémát. A szám´ıtógépek szám´ıtási sebességének növekedése és az egyre kifinomultabb optimalizálási módszerek alkalmazása révén azonban az utols´ o évtizedben megn˝ott az érdekl˝odés ezek irányában, szaporodnak az ilyen t´ argy´ u publik´ aciók. A kis és közepes méret˝ u problémák mára megoldhat´ ov´ a v´ altak. M´ ar az 1980-as évek elején Bodin és szerz˝otársai komolyan kritizálták a ´ szekvenci´ alis megk¨ ozel´ıtést [13]. Eszak-amerikai tömegközlekedési példákon kereszt¨ ul bizony´ıtt´ ak azon érvelés¨ uket, hogy a járm˝ uvezet˝ok (bér)költsége sokszor magasabb, mint a j´ arm˝ uvekkel kapcsolatos költségek. Extrém esetekben a bérk¨ oltség ak´ ar 80%-´ at is adhatja a kétféle költség összegének. Ebb˝ol az k¨ ovetkezik, hogy ezt a k¨ oltséget nem lehet másodlagos kérdésnek tekinteni. S˝ot, alapvet˝ oen figyelembe kell venni már az els˝o fázisban, vagy kombinált, integrált m´ odon. Ball és szerz˝ ot´ arsai [8] ugyancsak integrált modellt javasoltak. Az ezt k¨ ovet˝ o cikkekben k¨ ulönböz˝o heurisztikus módszereket adtak meg a kutat´ ok, amelyekben a VCSP heurisztikus megoldása során figyelembe vettek bizonyos, j´ arm˝ uvekre vonatkozó feltételeket is. Az 1997 el˝ott használt módszerekr˝ ol egy j´ o ´ attekintés található Gaffi és Nonato 1999-es közleményében [35], vagy Freling 1997-es PhD-dolgozatában [32]. Az els˝ o, val´ oban integr´ alt járm˝ u- és vezet˝ou ¨temezési megközel´ıtés csak 1995ben sz¨ uletett Freling és szerz˝otársai révén [31]. Err˝ol Gaffi és Nonato [35] bizony´ıtotta be, hogy hatékony lehet akkor is, amikor a megengedett váltási pontok t´ avol esnek egym´ ast´ ol, például helyközi vagy távolsági tömegközlekedés esetén. A m´ odszer szintén jól m˝ uködhet azokban az esetekben, amikor egy vezet˝ o egy j´ arm˝ uvet haszn´ alhat csak a m˝ uszakja során. A legnépszer˝ ubb megk¨ ozel´ıtés az integrált VCSP problémára kétségk´ıv¨ ul az egészérték˝ u programoz´ asi modell alkalmazása. Freling és szerz˝otársai [31] modellje az egydep´ os esetre h´ arom részb˝ol állt: az SDVSP-t kvázi-hozzárendelési, a VCSP-t halmazparticion´ al´ asi feladatként fogalmazták meg. A kett˝ot korlátozó feltételekkel k¨ ot¨ otték ¨ ossze, biztos´ıtva a kompatibilitást. A feladat megoldására Lagrange-relax´ aci´ ot és oszlopgenerálási módszert kombináló, közel´ıt˝o megoldást adtak. Ez azt´ an tov´ abbi publikációkat inspirált, lásd [33, 34, 46]. Freling és szerz˝ ot´ arsai a [33, 34] cikkeikben szintén az egydepós integrált feladatot tekintették, a buszok számára vonatkozó fels˝o korlát nélk¨ ul. Ugyancsak oszlopgener´ al´ ast — és ezen bel¨ ul Lagrange-relaxációt — használtak az ott adódó u ń. mester probléma megoldására, a feltételek relaxációjával. A [34] cikkben val´ os, kb. 150, illetve 240 j´ aratból álló feladatok megoldásáról számoltak be, kezelhet˝ o megold´ asi id˝ oben. Megmutatták, hogy csak kis jav´ıtás érhet˝o el a 23

feladatok szekvenci´ alis, egymás után történ˝o megoldásához képest. Ez a jav´ıt´ as szignifik´ ansabb, ha a j´ arm˝ uvezet˝ok nem válthatnak járm˝ uvet (egy sz¨ unetet k¨ ovet˝ oen). Az els˝ o pontos megold´ ast adó algoritmust 1999-ben publikálta Haase és Friberg [41] az egydep´ os esetre. Modellj¨ ukben egy integrált matematikai megfogalmaz´ as´ at adt´ ak mindkét halmazparticionálási megközel´ıtésnek: mindkét részfeladatot halmazparticon´ al´ asi feladatként fogalmazták meg. Eljárásukban a járm˝ uvek u ¨temezése Ribeiro és Soumis 1994-es [63], m´ıg a járm˝ uvezet˝ok u ¨temezése Desrochers és Soumis 1989-es [26] modelljein alapult. A szétválasztás és vágás és ´ araz´ as (branch-and-cut-and-price) t´ıpus´ u algoritmusukban oszlopgenerálást és v´ ag´ asgener´ al´ ast alkalmaztak. Az oszlopgenerálási mesterprobléma az LPrelax´ aci´ onak felelt meg, m´ıg az árazásra (pricing) a legrövidebb u ´t problémák megold´ asa szolg´ alt. Algoritmusukkal csak kisméret˝ u példákat tudtak megoldani, legfeljebb 20 j´ aratb´ ol ´ all´ okat. Egy m´ asik érdekes egzakt algoritmust adtak meg az egydepós esetre Haase és szerz˝ ot´ arsai 2001-ben [42]. A járm˝ uvezet˝o-¨ utemezési problémát egy többtermékes h´ al´ ozati folyam problémaként megfogalmazva oldották meg u ´gy, hogy bele´ agyazt´ ak az egydep´ os, járm˝ uvekre vonatkozó feltételeket. Ezt olyan módon tették, hogy mindkét f´ azist figyelembe véve, a VCSP feladatra garantált, pontos optimumot adott az algoritmusuk. Itt a szétválasztás és árazás (branchand-price) t´ıpus´ u algoritmusra számos gyors´ıtási technikát alkalmaztak. Két algoritmusv´ altozatot is t´ argyaltak a szétválasztáskor adódó ágak kezelésére: egy egzakt és egy heurisztikus v´ altozatot. Véletlen feladatokon végeztek szám´ıtógé´ pes szimul´ aci´ os teszteket. Atlagosan kb. 1,5 órás (bár 10-b˝ol 6 esetben 3 órás) fut´ asi id˝ ovel tudtak 150 j´ aratméret˝ u példákig pontos megoldást szolgáltatni. Ennél nagyobb, 350 j´ aratméret˝ u példákig heurisztikus megoldást alkalmaztak, 2´ or´ an bel¨ uli CPU-id˝ ot használva. Itt a feladat olyan egyszer˝ us´ıtett megfogalmaz´ as´ at tekintették, ahol a k¨ oltségben csak a sz¨ ukséges buszok száma szerepelt, és ok sem vettek figyelembe korlátot ezek számára. Így megfogalmazásuk gyakor˝ latilag szintén egydep´ os feladatként fogható fel. Fontos kiemelni ugyanakkor, hogy a feladatok nem val´ os, hanem a tömegközlekedési feladatokat szimuláló véletlen adatokb´ ol sz´ armaztak. A t¨ obbdep´ os esetben Gaffi és szerz˝otársa [35] tárgyalták el˝oször az integrált feladatot, heurisztikus m´ odszert használva. Lagrange-relaxációt és az oszlopgener´ al´ as m´ odszerét haszn´ alták, csak a többdepós esetre módos´ıtva a megfogal˝ is az egyidej˝ maz´ ast. Ok u vezet˝o- és járm˝ uu ¨temezés el˝onyei mellett érveltek olasz t¨ omegk¨ ozlekedési példákon kereszt¨ ul, amelyek nem városi (nem helyi) k¨ ozlekedési péld´ ak voltak. De u ´jra felh´ıvja a figyelm¨ unket a szám´ıtási id˝o fontoss´ ag´ ara, kritikus volt´ ara, hogy egy 257 járatból álló, olasz tömegközlekedési példa esete 24 ´ or´ an´ al hosszabb szám´ıtási id˝ot adott, átlagosan 2 − 6 óra volt a fut´ asi id˝ o, b´ ar a maiakn´ al lényegesen lassabb, 180 MHz-es PC gépen. Huisman és szerz˝ ot´ arsai 2005-ben [46] a korábbi egydepós [34, 42] modelleket és algoritmusokat sikeresen terjesztették ki a többdepós problémára. Ez volt a t¨ obbdep´ os probléma els˝o általános matematikai megfogalmazása. Két megk¨ ozel´ıtést is javasoltak: az egyik a [32, 34], a másik a [42] tanulmányokban ismertetett m´ odszer ´ altal´ anos´ıtása a többdepós esetre. Mindkett˝o esetén az els˝o 24

f´ azisban egy als´ o korl´ atot szám´ıtanak ki az optimumra. Az els˝o fázis LPrelax´ ac´ on alapszik, oszlopgenerálást és Lagrange-relaxációt használ. A második f´ azis ad egy lehetséges egészérték˝ u megoldást a feladatra. A [34]-ben használt Lagrange-relax´ aci´ ot alkalmazva el˝oször egy járm˝ uu ¨temezést generál, amelyb˝ol azt´ an a [33, 34] cikkekben t´ argyalt módszereket használva járm˝ uvezet˝o-¨ uteme¨ zést kész´ıt. Osszehasonl´ ıt´ o teszteket kb. 650 járatig kész´ıtettek, amelyek eredményei fel¨ ulm´ ulj´ ak a szok´ asos szekvenciális u ¨temezést használó módszereket. Teszteket végeztek val´ os és szimulációs tesztadatokon egyaránt. A két megközel´ıtés k¨ oz¨ ott nem mutatkozott szignifikáns eltérés, de az els˝o valamennyivel jobbnak bizonyult. Val´ os, nagyméret˝ u, t¨ obbdepós, heterogén járm˝ uflotta esetén az eddig megeml´ıtett m´ odszerek integr´ al´ asa nehéz lenne egy alkalmazási rendszerbe. Így ezek helyett a szekvenci´ alis, esetleg kézi módon történ˝o integrálást alkalmazták a 2000-es évek elejéig. A [22] cikkben r¨ ovidebb megoldási id˝ot tudtak produkálni és nagyobb feladatokat tudtak megoldani a szerz˝ok, kisebb méret˝ u részfeladatokra vágva a feladatokat, és azokat — ¨ onmagukban integrált módon, k¨ ulön — oldva meg. A t¨ obbdep´ os feladatra Bornd¨ orfer és szerz˝otársai [15] is Lagrange-relaxáción alapul´ o megk¨ ozel´ıtést haszn´ altak. A járm˝ u-¨ utemezési és a járm˝ uvezet˝o-¨ utemezési problém´ akn´ al haszn´ alt k¨ ozel´ıt˝o megoldásokat alkalmazták, ezek információit felhaszn´ alva egy branch-and-bound t´ıpus´ u algoritmusban. Egészérték˝ u programoz´ asi technik´ at haszn´ altak, k¨ ulönböz˝o korlátozó feltételekkel összekapcsolva a j´ arm˝ uveket és j´ arm˝ uvezet˝ oket a rezsi és a kiállási, valamint beállási járatoknál. Heurisztikus m´ odon, Lagrange-relaxációt használva, majd az egészérték˝ u megold´ asokat egy korl´ atoz´ as és szétválasztás t´ıpus´ u technikával nyerve nagyméret˝ u problém´ akat, 1500-as j´ aratszám´ u problémát is kezelni tudtak. Az integr´ alt feladat egy heurisztikus megközel´ıtését adja Laurent és Hao dolgozata [51] is. Hab´ ar az ´ altaluk tárgyalt feladat általánosabb, mint az egydepós eset, de feltételezik, hogy az ¨ osszes járm˝ u ugyanabban a depóban parkol. Ugyanakkor a j´ arm˝ uvek t´ıpusaik szerint nem kell, hogy homogén flottát alkossanak. Egy moh´ o, véletlen adapt´ıv keresést alkalmaznak (Greedy Randomized Adaptive Search, GRASP). Hasonlóan a legtöbb módszerhez egynapos id˝ohorizontot alkalmaznak, de a j´ arm˝ uvezet˝okre vonatkozó feltételek egyszer˝ us´ıtettek: csak a napi m˝ uszak ´ atmér˝ ojére” (a fellépés és lelépés között eltelt id˝ore) vonatkozó ” korl´ atot, a napi teljes munkaid˝ore vonatkozó korlátot, és azt a paramétert veszik figyelembe, hogy a j´ arm˝ uvezet˝oknek megengedett-e vagy nem a napon bel¨ uli j´ arm˝ uv´ alt´ as. Mesquita és Paias 2008-ban [58] két matematikai megfogalmazást adtak a problém´ ara. Mindkét modell többtermékes hálózati modellt tartalmaz a járm˝ uu ¨temezésre, m´ıg a j´ arm˝ uvezet˝o-¨ utemezési rész vagy halmazparticionálási vagy kombin´ alt halmazparticion´ alási és lefedési megfogalmazás. A relaxált LP-t oszlopgener´ al´ assal oldott´ ak meg, amelynek részproblémája korlátozó feltételekkel ell´ atott legr¨ ovidebb u ´t feladat. Amennyiben a relaxált LP megoldása nem egésznek ad´ odott, egészérték˝ u megoldást kerestek korlátozás és szétválasztás alap´ u hagyom´ anyos IP-megoldóval. A [38]-ban alkalmazott eljárás egy ehhez hasonl´ o megk¨ ozel´ıtést használt, a szerz˝ok korábbi id˝o-tér hálózati modelljét al25

kalmazva a j´ arm˝ u-¨ utemezési komponensben. A részben integr´ alt modellek közé tartozó modellt tárgyal Gintner, Kliewer és Suhl 2008-as cikke [39]. Ez annyiban hasonl´ıt a tradicionális szekvenciális megk¨ ozel´ıtésekre, hogy a járm˝ uvek optimalizált u ¨temezését végzi el el˝oször, majd — ennek eredményét felhasználva — a járm˝ uvezet˝okét. A járm˝ uvek u ¨temezési f´ azisa az id˝ o-tér h´ al´ ozati MDVSP-modellt használja, de annyiban k¨ ulönb¨ ozik az eredeti megk¨ ozel´ıtést˝ol, hogy nem egyetlen optimális megoldást ad, hanem t¨ obbet, minim´ alis j´ arm˝ uszámmal és minimális költséggel. Ezek után a VCSP-t halmazparticion´ alási feladatként oldja meg, és Lagrange-relaxációt alkalmaz. A klasszikus megközel´ıtéssel összehasonl´ıtva a módszer jobb járm˝ uvezet˝ o-¨ utemezéseket eredményez. Steinzen és szerz˝ ot´ arsai 2010-ben [68] egy teljesen integrált VCSP megközel´ıtést adnak. A m¨ og¨ ottes, járm˝ uu ¨temezést kezel˝o modell az id˝o-tér hálózati modell. A megold´ as itt is az oszlopgenerálás és a Lagrange-relaxációs módszert kombin´ alva t¨ orténik. Az oszlopgenerálás részfeladatát korlátozó feltételekkel ell´ atott — egy id˝ o-tér h´ al´ ozaton alapuló — legrövidebb u ´t feladat megoldásával modellezték. Egy heurisztikus, szétválasztás és árazás t´ıpus´ u módszerrel gener´ altak lehetséges megold´ asokat. A numerikus tesztjeik azt mutatják, hogy ez a m´ odszer fel¨ ulm´ ulja a kor´ abbiakat az ismertetett tesztfeladatokon, amelyeket 640 j´ aratot tartalmaz´ o példaméretekig tekintettek. Az összehasonl´ıtás alapjait a [15, 38, 45, 46] cikkek alkották, amelyek köz¨ ul valamennyit fel¨ ulm´ ulta tesztpéld´ aikon az algoritmusuk. Az alkalmazott tesztpéldáik (kizárólag) a Steinzen weblapj´ an tal´ alhat´ o péld´ ak [67] voltak.

5.

A m˝ uszakkioszt´ asi feladat

A j´ arm˝ uvezet˝ ok m˝ uszakkiosztási problémája is az általános m˝ uszakkiosztási feladatok k¨ ozé tartozik. Itt a feladat az, hogy egy tervezési periódusban munkav´ allal´ okat — sz´ amos ´ altal´ anos és speciális feltétel figyelembevételével — rendelj¨ unk hozz´ a a napi m˝ uszakokhoz. A járm˝ uvezet˝ok m˝ uszakkiosztási feladatának feltételei ´ altal´ aban megfelelnek más, tipikus alkalmazások feltételeinek, amelyek egyes személyzetbeoszt´ asi [17, 18] és n˝ovérbeosztási [19, 11] feladatoknál, illetve a call-centerek u ¨zemeltetése esetén az operátori m˝ uszakkiosztásnál [65] is megtal´ alhat´ ok. A j´ arm˝ uvezet˝ ok m˝ uszakkiosztási feladatában adottak a járm˝ uvezet˝oi m˝ uszakok, amelyeket a vezet˝ ou ¨temezés során meghatároztunk. Ezek napi beosztásokat jelentenek. Ezek a m˝ uszakok a tervezési periódus k¨ ulönböz˝o napjain eltér˝oek lehetnek. Adottak tov´ abb´ a a rendelkezésre álló járm˝ uvezet˝ok. A m˝ uszakkioszt´ as ´ altal´ aban hosszabb periódusra történik, amelyet tervezési id˝ oszaknak nevez¨ unk. A tervezési id˝oszak tipikusan néhány hétb˝ol álló id˝ointervallum, de ez lehet néh´ any nap, hónap, vagy akár egy egész év is. A m˝ uszakkioszt´ asi feladat lényege, hogy egy tervezési id˝oszakra az adott m˝ uszakokat rendelj¨ uk val´ os alkalmazottakhoz u ´gy, hogy az el˝o´ırt szabályokat betartjuk. Ez a feladat t¨ obb alkalmaz´ asi ter¨ uleten fordul el˝o. A leggyakoribb alkalmazások a légik¨ ozlekedésben (pil´ ota és személyzet), vas´ uti közlekedésben, call-centerekben

26

dolgoz´ ok, n˝ ovérek és buszsof˝orök munkájának tervezése. A m´ odszernek a tervezési id˝oszak minden m˝ uszakjához járm˝ uvezet˝ot (konkrét személyt) kell rendelnie. Van néhány általános szabály, rendelkezés, amely korl´ atoz´ o feltételként veend˝ o figyelembe. Ilyenek például a maximális heti munka´ or´ ak sz´ ama, vagy a szabadnapok el˝o´ırt minimális száma egy adott id˝oszakban, ezen bel¨ ul a vas´ arnapok sz´ ama, stb. A szabályok teljesen k¨ ulönbözhetnek az alkalmaz´ asi ter¨ ulett˝ ol f¨ ugg˝ oen (légi, vas´ uti közlekedés, városi tömegközlekedés, stb.). Gyakran tov´ abbi speci´ alis helyi szabályok is el˝ofordulnak, amelyeket szintén korl´ atoz´ o feltételként kell figyelembe venni a beosztás elkész´ıtéskor. Ilyen péld´ aul az, hogy milyen kateg´ oriáj´ u vezet˝oi jogos´ıtvánnyal kell rendelkeznie a vezet˝ onek bizonyos t´ıpus´ u buszok vezetéséhez. A hozz´ arendelés k¨ oltsége a közlekedési cégek esetén nagyban f¨ ugghet a vállalatvezetés filoz´ ofi´ aj´ at´ ol”. Ez lehet egyetlen cél is, de több összetev˝o is alkothat” ja. Ut´ obbi esetben ezekb˝ ol több is (pl. s´ ulyozott módon) megjelenhet a célf¨ uggvényben. Ilyen lehet a j´ arm˝ uvezet˝ok számának a minimalizálása, a szerz˝odésben szerepl˝ o meg´ allap´ıtott munkaóráktól való eltérések összegének minimalizálása (ak´ ar t´ ul´ or´ ar´ ol, ak´ ar az abban szerepl˝onél kevesebb tényleges munkaid˝or˝ol van sz´ o, azaz a t´ ulfoglalkoztat´ ast és az alulfoglalkoztatást egyaránt ker¨ ulni kell, a lehetséges mértékben). A fenti okok miatt több célf¨ uggvény˝ u optimalizálási m´ odszerek haszn´ alata is indokolt lehet [59, 60]. Miután az alapfeladat általánosan tekintve hozz´ arendelési probléma, a szakirodalomban megtalálható néhány — a hozz´ arendelési feladatra alapozott — általános megközel´ıtés is a m˝ uszakkioszt´ asi feladatra. Ilyenek például többtermékes folyam algoritmusok [17], a logikai programoz´ as alkalmazása korlátozó feltételekkel [74], vagy evol´ uciós m´ odszert haszn´ al´ o algoritmusok [59]. A feladatot t¨ obb részfeladatra lehet bontani, ahol az egyes lépéseket egymás ut´ an, esetleg iterat´ıvan lehet végrehajtani. Bizonyos környezetben nem minden lépés sz¨ ukséges, illetve ¨ ossze is lehet vonni ˝oket. A buszközlekedésben leginkább el˝ ofordul´ o lépések a k¨ ovetkez˝ok. • Igényfelmérés. Els˝ o lépésben meghatározható, hogy mennyi emberre van sz¨ ukség. Ez f¨ ugg a m˝ uszakok számától, egymáshoz képest id˝obeni viszonyukt´ ol, méret¨ ukt˝ ol, t´ıpusuktól, továbbá befolyásolják a rendelkezésre álló alkalmazottak tulajdonságai” (pl. szerz˝odések, jogos´ıtványok). ” • Szabadnap kioszt´ as. A szabadnapok kiosztása f˝oleg akkor sz¨ ukséges, amikor nem teljesen k¨ ot¨ ottek a jöv˝obeni m˝ uszakok. Ennek végrehajtása során némi rugalmass´ agot biztos´ıtani kell. Ez a lépés természetesen a definiált szab´ alyokt´ ol f¨ ugg, att´ ol, hogy mennyi és milyen szabadnapot kell kiosztani. • M˝ uszaksorozatok kész´ıtése. Ebben a lépésben az adott m˝ uszakokból (esetleg m´ asképp meghat´ arozott feladatokból) bizonyos id˝ointervallumra (jellemz˝ oen egy hétre vagy hónapra) adott hossz´ uság´ u sorozatokat hoznak létre. • M˝ uszaksorozat-ember hozzárendelés. Vég¨ ul itt az önálló m˝ uszakokat vagy m˝ uszaksorozatokat tényleges alkalmazottakhoz rendelik. 27

A feladat egy részletesebb, ´ altalánosabb felbontása megtalálható [28]-ban.

5.1.

Korl´ atoz´ o szab´ alyok

A szigor´ u, kemény” szab´ alyok f˝oleg az EU, minisztériumok, önkormányzatok, ” szakszervezetek, stb. ´ altal el˝ o´ırt szabályok, ezek betartása kötelez˝o az u ¨temezés sor´ an. Az aj´ anlott, puha” szabályok f˝oleg személyi igények során ker¨ ulnek ” el˝ otérbe (néh´ any szabadnap egymás után következzen, néhány szabadnap essen hétvégére, stb.). Ezek betartása nem kötelez˝o, de min˝os´ıtik a megoldás j´ os´ ag´ at”, s´ ulyozva beker¨ ulhetnek a célf¨ uggvénybe a kiértékelésnél. ” Jellemz˝ o szigor´ u szab´ alyfajták, amelyek a legtöbb alkalmazási ter¨ uleten el˝ofordulnak: • Adott az egym´ ast k¨ ovet˝o két m˝ uszak közötti minimális pihen˝oid˝o. • Maxim´ alva van a heti munkaid˝o. • Adott a heti minim´ alis pihen˝oid˝o. • Szab´ alyozott, hogy legfeljebb hány egymást követ˝o napon dolgozhat a munkav´ allal´ o szabadnap nélk¨ ul. • Adott, hogy legal´ abb hány szabadnapja legyen egy munkavállalónak egy h´ onapon bel¨ ul. • Adott, hogy h´ any szabadnapnak kell esnie bizonyos t´ıpus´ u napra (pl. hétvégére, vas´ arnapra, stb.) adott id˝on bel¨ ul (általában egy hónapon bel¨ ul). • Adott, hogy bizonyos munkavállalók csak bizonyos t´ıpus´ u m˝ uszakot kaphatnak, vagy milyen t´ıpusból mennyit kaphatnak. Jellemz˝ o puha” szab´ alyok, igények: ” • Ker¨ ulj¨ uk az olyan kiosztást, ahol két szabadnap között csak egy munkanap van. • El˝ onyben részes´ıtj¨ uk, ha két szabadnap egymás után következik. • Lehet˝ oleg a szabadnapok egyenletesen legyenek elosztva a tervezési id˝oszakban. • Egyenletesen legyenek a m˝ uszakt´ıpusok kiosztva az alkalmazottak között, vagy pont ford´ıtva, lehet˝oleg azonos t´ıpus´ u m˝ uszakot kapjon egy alkalmazott egy adott id˝ oszakon bel¨ ul (hét vagy hónap). A buszos j´ arm˝ uvezet˝ okre vonatkozó szabályok egyfajta osztályozása megtalálhat´ o [60]-ban.

28

5.2.

Ki´ ert´ ekel´ es

A m˝ uszakkioszt´ as min˝ oségének meghatározása nem egyértelm˝ u a szakirodalomban. Természetesen a cél mindenhol a költség minimalizálása, de a költség meghat´ aroz´ as´ ahoz t¨ obb tényez˝ot kell figyelembe venni. Egyrészt cél a sz¨ ukséges alkalmazottak sz´ am´ anak minimalizálása, feltételezve, hogy kevesebb ember alkalmaz´ as´ aval kisebb a k¨ oltség [17, 18, 74]. Ugyanakkor több helyen az alkalmazottak sz´ ama k¨ ot¨ ott, ilyenkor a kiosztás min˝oségének növelése a cél, amit a puha szab´ alyokhoz val´ o illeszkedés határoz meg. Ezen szabályok megfelel˝oen s´ ulyozott kiértékelése hat´ arozza meg a kiosztás min˝oségét. Természetesen gyakran az emberek sz´ am´ anak minimalizálása és a puha szabályok figyelembe vétele egy¨ uttesen jelenik meg az optimalizálásban [19, 59], esetleg a be nem osztott alkalmazottakat tartalékba helyezik betegségek esetére [60]. Ugyanakkor a valós életben a kioszt´ as k¨ oltségét nagyban befolyásolja az alkalmazottak szerz˝odése, amely meghat´ arozza a ledolgozandó órák számát. Ett˝ol való eltérés alul- illetve t´ ulfoglalkoztat´ ast jelent. Az el˝obbi azért költséges, mert a szerz˝odésben foglalt or´ ´ ak alapj´ an kapja a fizetését, holott nem dolgozott annyit, az utóbbi meg t´ ul´ or´ at jelent, amelynek bérezése általában magasabb az alap-órabérnél. Így ezek s´ ulyozott minimaliz´ al´ asa a költség csökkenését jelenti [6]. Az nyilvánvaló, hogy az alul- és t´ ulfoglalkoztatás csökkentése csak u ´gy érhet˝o el, ha a kiosztás sor´ an felhaszn´ alt alkalmazottak száma és összetev˝oje változik.

5.3.

Megold´ asi m´ odszerek

Ugyan a m˝ uszakkioszt´ asi feladat az élet több ter¨ uletén fordul el˝o, a f˝obb betartand´ o szab´ alyok illetve az optimalizálás során figyelembe vett költség- és célf¨ uggvények nagyon hasonlóak. Így a k¨ ulönböz˝o ter¨ uleten alkalmazott megold´ asi m´ odszerek is elég ´ altal´ anosak a többi alkalmazási környezetbe való illesztéshez. A m´ odszerek k¨ oz¨ otti k¨ ulönbség egyrészt inkább abból adódik, hogy hol h´ uzzuk meg a hat´ art a megoldás min˝osége, valamint a feladat mérete és a futási id˝ o k¨ oz¨ ott. M´ asrészt az alkalmazott optimalizálási algoritmusok változatossága jellemzi a szakirodalmat. Egyik megközel´ıtés, hogy a feladatot visszavezetik halmazlefedési vagy part´ıcion´ al´ asi feladatra, ahol legenerálnak sok m˝ uszakkiosztást, majd ezekb˝ ol kiv´ alasztj´ ak azokat, amelyekkel a költség a legkisebb. Ezt az ir´ anyt k¨ ovették péld´ aul Gamache és szerz˝otársai, akik 1999-es cikk¨ ukben [36] a halmazparticion´ al´ ast oszlopgenerálással oldották meg. A feladat fel´ırhat´ o folyamproblémaként is. Cappanera és szerz˝otársai 2004ben egy t¨ obbtermékes folyamproblémaként oldottak meg légiközlekedés u ¨temezési feladatot, ahol a t¨ obbtermékességet az adta, hogy háromféle kiosztást kész´ıtettek a kapit´ anyoknak, pilótáknak és légi utask´ısér˝oknek [17]. Jellemz˝o még a kombin´ alt megold´ asi m´ odszerek használata. Yunes és társai [74] rámutattak, hogy az egészérték˝ u programozási feladatként történ˝o fel´ırás csak kis feladatokra m˝ uk¨ odik elfogadhat´ o id˝ on bel¨ ul, m´ıg a pusztán korlátozó feltételes logikai programoz´ asként val´ o fel´ır´ as m´ ar hatékonyabb, de még mindig nem elfogadható valós méret˝ u feladatokra. Azt azonban kimutatták, hogy ennek a két módszernek a

29

kombin´ al´ as´ aval kész´ıtett hibrid módszer, ahol oszlopgenerálást alkalmaztak és az oszlopok gener´ al´ as´ at végezték korlátozó feltételes logikai programozással, már képes volt nagy feladatokra is hatékony megoldásokat adni elfogadható id˝o alatt. Tov´ abbi kombin´ alt m´ odszert alkalmaztak Caprara és szerz˝otársai. Itt a megold´ ast egy konstrukt´ıv heurisztika adja, amely a kiosztás ép´ıtése közben a mohó m˝ uszakv´ alaszt´ ashoz felhasználja egy Lagrange-féle relaxált egészérték˝ u programoz´ asi feladat megold´ as´ at [18]. Iterat´ıv kombinált heurisztikát alkalmaz Bellanti [11] és Nurmi [60]. El˝obbi egy kezdeti kiosztást generál mohó módon, majd ezt jav´ıtja szomszéds´ agi keresés módszerrel, ehhez tesztelt iterat´ıv helyi keresést illetve tabulist´ as m´ odszert [11]. Nurmi és szerz˝otársai [60] a megoldást két f´ azisban végzik: el˝ osz¨ or a szabadnapokat osztják ki, majd utána a m˝ uszakkioszt´ ast. Mindkét feladathoz ugyanazt a módszert alkalmazzák, amely egy mohó, popul´ aci´ oalap´ u helyi keresés. Egy kioszt´ as kiértékelése több tényez˝ob˝ol áll össze, ´ıgy az optimalizálás gyakran t¨ obb célf¨ uggvény˝ u optimalizálás. Erre példa Moz és szerz˝otársai [59] evol´ uci´ os m´ odszere, ahol két szempont szerint történik az optimalizálás. Ez a kett˝ o az emberek elv´ art számától való eltérés minimalizálása és a t´ ulórák egyenletes eloszt´ asa. A generált megoldások kiértékelésénél e két cél szerinti Pareto-dominanci´ at haszn´ alják fel.

5.4.

Sz´ etv´ alaszt´ asi strat´ egi´ ak

A fenti részfeladatokat k¨ ozelebbr˝ol megvizsgálva láthatjuk, hogy k¨ ulönböz˝o opci´ ok lehetségesek az u ¨temezési rendszer strukt´ urájának megtervezésére. Két alapvet˝ o kérdés, amely fontos ennek a strukt´ urának a megtervezésével kapcsolatban: • Hol legyen a hat´ arvonal a vezet˝ou ¨temezés és a m˝ uszakkiosztás feladatai k¨ oz¨ ott, mely szab´ alyokat melyik részfeladatnál vegy¨ unk figyelembe? Alapvet˝ oen a legf˝ obb elv ezzel kapcsolatban az, hogy a dolgozókra vonatkozó olyan szab´ alyok, rendelkezések, amelyek az egy napon bel¨ uli m˝ uszak kialak´ıt´ as´ aban veend˝ ok figyelembe, azok a vezet˝ou ¨temezés, m´ıg a további feltételek a m˝ uszakkiosztás feladatkörébe tartoznak. Sajnos, elméletileg ennek a szab´ alynak a figyelembevételével is a vezet˝ou ¨temezéssel a napi u ¨temezéseknek egy olyan szerkezetét kaphatjuk, amelyekb˝ol a m˝ uszakkioszt´ as m´ ar nem eredményezhet a szabályoknak megfelel˝o m˝ uszakkiosztást. A gyakorlatban ez a probléma inkább csak kisebb városok társaságainál életszer˝ u, ott fordulhat el˝o realisztikus módon (jóval százezer f˝o alatti lakoss´ ag esetén), mivel a kisebb kombinációs lehet˝oség okozhat hozzárendelési problém´ akat egy olyan u ¨temezésben, ahol az u ¨temezés szerkezetének el˝ o´ırtnak kell lennie. Mivel a feladat ebben az esetben kisebb méret˝ u, ez lehet˝ ové teszi napi u ¨temezés helyett heti periódusok kialak´ıtását, ´ıgy csökkentve annak a kock´ azatát, hogy nem kapunk lehetséges megoldást. • A sorrend a j´ arm˝ uu ¨temezés és a járm˝ uvezet˝ok u ¨temezése között: mivel a j´ arm˝ uvek napi m˝ uszakjai menetrendi el˝o´ırásokon alapulnak, ´ıgy természetes m´ odszerként ad´ odik els˝o fázisban az optimális járm˝ uu ¨temezést elkész´ı30

teni, és azut´ an a vezet˝oket hozzárendelni a járm˝ uvekhez (megengedve a m˝ uszak sor´ an az eszközökön a vezet˝ocserét) olyan módon, hogy az osszes, az emberekre vonatkozó szabály ki legyen elég´ıtve. Ez a módszer ¨ ugyan hatékony, viszont robusztus szám´ıtógépes optimalizálási hátteret ´ igényel. Eppen ezért a gyakorlatban, ahol nem használnak optimalizálási eszk¨ oz¨ oket automatiz´ alt tervezésre, vagy annak támogatására, az alkalmazott mérn¨ oki heurisztikák” megcserélik a két lépést: els˝o lépésként (nem ” automatiz´ alt tervezéssel) gyakran a menetrend alapján emberm˝ uszakokat hoznak létre, figyelembe véve a járm˝ uvezet˝okre vonatkozó szabályokat, majd azut´ an megfelel˝ o járm˝ uveket rendelnek a kialak´ıtott m˝ uszakokhoz. Ennek a megk¨ ozel´ıtésnek az el˝onye az, hogy a feladat komplexitása jelent˝ osen cs¨ okken, mivel a járm˝ uvezet˝o a m˝ uszakja alatt nem cserélhet j´ arm˝ uvet. Komoly h´ atrány ugyanakkor, hogy ez magasabb költség˝ uu ¨temezéseket eredményezhet. Jellemz˝oen, az egy napon használt járm˝ uvek sz´ ama ilyenkor szignifikánsan nagyobb. A fentiek alapján egy optimaliz´ al´ as-orient´ alt automatizált u ¨temezési rendszer esetén feltételezz¨ uk, hogy az j´ arm˝ u-¨ utemezéssel indul, vagy ha nem, akkor ezzel egyidej˝ uleg figyelnie kell a j´ arm˝ uszab´ alyokat is.

6.

N´ eh´ any saj´ at eredm´ eny

Vég¨ ul r¨ oviden megeml´ıtj¨ uk, hogy a jelen tanulmány szerz˝oi további (részben más t´ arsszerz˝ okkel k¨ oz¨ os) cikkeikben a közösségi buszközlekedés operat´ıv tervezési feladataira adott — ´ altal´ aban k¨ ulönböz˝o gyakorlati kih´ıvásokból fakadó — megold´ asaikat t´ argyalj´ ak az al´ abbi cikkekben, közleményekben: [4, 5, 6, 7, 9, 10, 20, 21, 70, 71]. Az itt t´ argyalt feloszt´ as alapján megvalós´ıtott, implementált fázisokat az [5] és a [10] publik´ aci´ okban egy keretrendszerben mutattuk be. A gyakorlatban is egy olyan, nagy modulokb´ ol álló keretrendszernek nevezhet˝o rendszert fejlesztett¨ unk, amelynek moduljai megengedik olyan eljárások beágyazását, amelyek megfelelnek a fent eml´ıtett követelményeknek. Amint az [10]-ben tárgyalt, ez a keretrendszer lehet˝ oséget ad arra, hogy egy-egy moduljába k¨ ulönböz˝o opciókat lehessen beép´ıteni. Így egy-egy modulon bel¨ ul alternat´ıv módszerek alkalmazhat´ ok opcion´ alis megold´ asként, és néhány esetben kitér¨ unk ezeknek a lehet˝oségeknek a t´ argyal´ as´ ara és vizsgálatára is. A j´ arm˝ u-¨ utemezési feladatra a [20] és a [21] publikációkban az MDVSPheurisztik´ ak kapcs´ an t´ argyalt, a [47] cikkben megadott változófixálási heurisztika néh´ any m´ odos´ıt´ as´ at, továbbbfejlesztését tárgyaltuk, k¨ ulönböz˝o hasonló t´ıpus´ u, tov´ abbi heurisztik´ akat tárgyalva és elemezve. A j´ arm˝ u-¨ utemezési és j´ arm˝ u-hozzárendelési feladatokhoz kapcsolódóan tapasztalatunk szerint a konkrét, gyakorlati u ¨temezésben a szakirodalomban tárgyalt és alkalmazott modellek hátrányaként lehet megeml´ıteni, hogy csak azokat a szab´ alyokat veszik figyelembe, amelyek a menetrendi járatokkal, az azokhoz megk´ıv´ ant buszt´ıpusokkal és kapacitásokkal, valamint a menetrendi járatok köz¨ otti rezsij´ aratokkal kapcsolatosak. Nem lehet viszont olyan specifikus feltétele-

31

7. ´ abra. Egy tipikus példa: egy munkanapon bel¨ ul melyik id˝oszakban hány járm˝ u (és j´ arm˝ uvezet˝ o) sz¨ ukséges minimálisan a járatok ellátásához. Ennek az u ń. kétp´ up´ u teve” diagramnak a p´ upjai”, a reggeli és a délutáni cs´ ucs (iskola- és ” ” munkakezdési és befejezési id˝opontok) jellegzetesek munkanapokon. ket beép´ıteni, amelyek val´ os alkalmazási környezetb˝ol származnak. A tömegközlekedés operat´ıv feladatainak tervezésénél ilyen tipikus, járm˝ uspecifikus korlátoz´ o feltételek a tankol´ asi vagy parkolási el˝o´ırások. Tankolási követelmények beép´ıtését t´ argyaltuk [7]-ben és [9]-ben. Az ezekben tárgyalt módszer el˝onye, hogy heterogén j´ arm˝ uflotta tankolási feladatait is kezeli. Erre sz¨ ukség lehet, amennyiben hossz´ u tankol´ asi idej˝ u, egy tankolással a d´ızel u ¨zemenyag´ u járm˝ uvekhez képest kis t´ avols´ agot megtenni képes járm˝ uvek (is) vannak a flottában. Egy j´ arm˝ uvezet˝ o-bar´ at, azaz olyan módszert tárgyalunk [5]-ben a járm˝ ués vezet˝ ou ¨temezési feladat iterat´ıv megoldására, ahol a járm˝ uvezet˝oknek nem kell a nap sor´ an j´ arm˝ uvet cserélni. Így csak egyazon járm˝ uvet vezetik a nap sor´ an a m˝ uszakjuk alatt, kivéve osztott m˝ uszak esetén. Ez olyan napközbeni, t¨ obb ´ or´ as otthoni pihen˝ o ut´ ani visszatérést tartalmazó m˝ uszak, amely tulajdonképpen két, f¨ uggetlen m˝ uszakrészb˝ol áll. A 7. ábra mutatja, hogy az osztott szolg´ alat miért sz¨ ukséges ´ altalában munkanapokon: a reggeli és a délutáni cs´ ucs j´ aratainak ell´ at´ as´ ahoz t¨ obb járm˝ u (és járm˝ uvezet˝o) sz¨ ukséges, mint egyébként napk¨ ozben. A [71] publik´ aci´ o a vezet˝ ou ¨temezésre ad a gyakorlatban használható heurisztik´ akat, m´ıg [70] a vezet˝ ou ¨temezéshez kapcsolódó tevékenységekre egy általános keretmunk´ at. A [6] publik´ aci´ oban a m˝ uszakkiosztási feladatra adott hossz´ u táv´ u, több hetes intervallumokra adott megoldásainkat ismertetj¨ uk. K¨ osz¨ onetnyilv´ an´ıt´ as. A kutatást a Szuperszám´ıtógép, a nemzeti virtuális ” 32

´ laborat´ orium” c´ım˝ u, TAMOP-4.2.2.C-11/1/KONV-2012-0010 azonos´ıtószám´ u projekt t´ amogatta az Eur´ opai Unió és az Európai Szociális Alap társfinansz´ı´ roz´ asa mellett. A tanulm´ any a TAMOP-4.2.1/B-09/1/KONV-2010-0003 Mobilit´ as és k¨ ornyezet: J´ arm˝ uipari, energetikai és környezeti kutatások a Középés Nyugat-Dun´ ant´ uli Régi´ oban projekt támogatásával jött létre, a projekt a ´ Magyar Allam és az Eur´ opai Unió támogatásával, az Európai Szociális Alap t´ arsfinansz´ıroz´ as´ aval val´ osul meg.

Hivatkoz´ asok [1] E. Abbink, J. van ’t Wout, and D. Huisman. Solving Large Scale Crew Scheduling Problems by using Iterative Partitioning, In Proceedings of ATMOS2007 – 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization and Systems, 96–106, 2007. [2] U. Aickelin, E.K. Burke, and J. Li. Improved Squeaky Wheel Optimization for Driver Scheduling, In Proceedings of the 9th International Conference on Parallel Problem Solving from Nature – PPSN IX, Lecture Notes in Computer Science, 4193, 182–191, Springer, 2006. [3] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows, Chapter IV of the Handbooks in Operations Research and Management Science, Volume 1: Optimization, (eds. G.L. Nemhauser, A.H.G. Rinnooy Kan, and M.J. Todd), 211–369, North Holland, 1989. ´ [4] V. Argil´ an, J. Balogh, J. Békési, B. Dávid, M. Krész, and A. Tóth. A flexible system for optimizing public transportation, In Proceedings of the 8th International Conference on Applied Informatics, Vol. 2, 181–190, 2010. ´ [5] V. Argil´ an, J. Balogh, J. Békési, B. Dávid, M. Krész, and A. Tóth. Driver scheduling based on ”driver-friendly” vehicle schedules, In Operations Research Proceedings 2011, Selected Papers of the International Conference on Operations Research (OR 2011), 323–328, Springer, 2012. ´ [6] V. Argil´ an, B. D´ avid, Cs. Kemény, G. Pongrácz, and A. Tóth. Greedy heuristics for driver scheduling and rostering, In Proceedings of the 2010 Mini-Conference on Applied Theoretical Computer Sciences, Koper, Slovenia, 13-14 October, 2010, University of Primorska Press, 101–108, 2011. (ISBN: 978-961-6832-10-6) ´ [7] V. Argil´ an, J. Balogh, J. Békési, B. Dávid, G. Galambos, M. Krész, and A. T´ oth. An Assignment Model for Real-World Vehicle Scheduling Problem with Refueling, k¨ ozlésre beny´ ujtva, 2013. [8] M. Ball, L. Bodin, and R. Dial. A matching based heuristic for scheduling mass transit crews and vehicles, Transportation Science, 7, 4–31, 1983.

33

[9] J. Balogh, J. Békési, G. Galambos, and M. Krész. Model and Algorithm for a Vehicle Scheduling Problem with Refueling, In Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems, 229–231, 2009. [10] J. Békési, A. Brodnik, D. Pash, and M. Krész. An integrated framework for bus logistic management: case studies, In Logistik Management, PhysicaVerlag, 389–411, 2009. [11] F.C.G. Bellanti, F. Della Croce, and R. Tadei. A greedy-based neighborhood search approach to a nurse rostering problem, European Journal of Operational Research, 153(1), 28–40, 2004. [12] A.A. Bertossi, P. Carraresi, and G. Gallo. On Some Matching Problems Arising in Vehicle Scheduling Models, Networks, 17, 271–281, 1987. [13] L. Bodin, B. Golden, A. Assad, and M. Ball. Routing and Scheduling of Vehicles and Crews: The State of the Art, Computers and Operations Research, 10, 63–211, 1983. [14] R. Bornd¨ orfer. Discrete Optimization in Public Transportation, IB-Report 08–56, Konrad-Zuse-Zentrum f¨ ur Informationstechnik Berlin, Germany, 2008. [15] R. Bornd¨ orfer, A. L¨ obel, and S. Weider. A bundle method for integrated multi-depot vehicle and duty scheduling in public transit, In Computeraided Systems in Public Transport, (eds. M. Hickman, P. Mirchandani, and S. Voß), Lecture Notes in Economics and Mathematical Systems, 600, 3–24, Springer-Verlag, Heidelberg, 2008. [16] S. Bunte and N. Kliewer. An overview on vehicle scheduling models, Journal of Public Transport, 1(4), 299–317, 2009. [17] P. Cappanera and G. Gallo. A Multicommodity Flow Approach to the Crew Rostering Problem, Operations Research, 52(4), 583–596, 2004. [18] A. Caprara, P. Toth, D. Vigo, and M. Fischetti. Modeling and Solving the Crew Rostering Problem, Operations Research, 46, 820–830, 1998. [19] B.M.W. Cheng, J.H.M. Lee, and J.C.K. Wu. A nurse rostering system using constraint programming and redundant modeling, IEEE Transactions in Information Technology in Biomedicine, 1(1), 44–54, 1997. [20] B. D´ avid. Heuristics for the Multiple-Depot Vehicle Scheduling Problem, In Proceedings of the 2010 Mini-Conference on Applied Theoretical Computer Science, Koper, Slovenia, 13-14 October, 2010, University of Primorska Press, 2011, pp. 23–28. (ISBN: 978-961-6832-10-6) [21] B. D´ avid and M. Krész. Application Oriented Variable Fixing Methods for the Multiple Depot Vehicle Scheduling Problem, Acta Cybernetica-Szeged, 21(1), 53–73, 2013. 34

[22] S.W. de Groot and D. Huisman. Vehicle and crew scheduling: Solving large real-world instances with an integrated approach, In Computer-aided Systems in Public Transport, (eds. M. Hickman, P. Mirchandani, and S. Voß), Lecture Notes in Economics and Mathematical Systems 600, 43–56, Springer-Verlag, Heidelberg, 2008. [23] M. Dell’ Amico, M. Fischetti, and P. Toth. Heuristic algorithms for the multiple depot vehicle scheduling problems, Management Science, 39, 115– 125, 1993. [24] G. Desaulniers and M.D. Hickman. Public Transit, In Handbook in OR & MS, (eds. C. Barnhart and G. Laporte), Vol. 14, Chapter 2, Elsevier B.V., 2007. [25] M. Desrochers, J. Gilbert, M. Sauve, and F. Soumis. CREW-OPT: subproblem modeling in a column generation approach to urban crew scheduling, In Computer-aided transit scheduling, (eds. M. Desrochers and J.-M. Rousseau), Lecture Notes in Economics and Mathematical Sytems, 386, 395–406, Springer-Verlag, Berlin, 1992. [26] M. Desrochers and F. Soumis. A column generation approach to the urban transit crew scheduling problem, Transportation Science, 23(1), 1–13, 1989. [27] T.G. Dias, J.P. de Sousa, and J.F. Cunha. Genetic algorithms for the bus driver scheduling problem: a case study, Journal of the Operational Research Society, 53(3), 324–335, 2002. [28] A.T. Ernst, H. Jiang, M. Krishnamoorthy, and D. Sier. Staff scheduling and rostering: A review of applications, methods and models, European Journal of Operational Research, 153, 3–27, 2004. [29] European Union. Regulation (EC) No. 561/2006 of the European Parliament and of the Council of 15 March 2006 on the harmonisation of certain social legislation relating to road transport and amending Council Regulations (EEC) 3821/85 and (EC) 2135/98 and repealing Council Regulation (EEC) 3820/85. Official Journal of the European Union, L 102, 11.04.2006. [30] J.C. Falkner and D.M. Ryan. EXPRESS: set partitioning for bus crew scheduling in Christchurch, In Computer-aided transit scheduling, (eds. M. Desrochers and J.-M. Rousseau), Lecture Notes in Economics and Mathematical Systems, 386. 359–378, Springer-Verlag, Berlin, 1992. [31] R. Freling, C.G.E. Boender, and J.M.P. Paixao. An integrated approach to vehicle and crew scheduling, Technical Report 9503/A, Econometric Institute, Erasmus University Rotterdam, Rotterdam, 1995. [32] R. Freling. Models and Techniques for Integrating Vehicle and Crew Scheduling, PhD thesis, Tinbergen Institute, Erasmus University Rotterdam, 1–151, 1997.

35

[33] R. Freling, A.P.M. Wagelmans, and J.M.P. Paixao. An overview of models and techniques for integrating vehicle and crew scheduling. In ComputerAided Transit Scheduling, (ed. N.H.M. Wilson), Lecture Notes in Economics and Mathematical Systems, 471, 441–460, Springer, Berlin, 1999. [34] R. Freling, D. Huisman, and A.P.M. Wagelmans. Models and algorithms for integration of vehicle and crew scheduling. Journal of Scheduling, 6, 63–85, 2003. [35] A. Gaffi and M. Nonato. An integrated approach to the extra-urban crew and vehicle scheduling problem, In Computer-Aided Transit Scheduling, (ed. N.H.M. Wilson), Lecture Notes in Economics and Mathematical Systems, 471, 103–128, Springer, Berlin, 1999. [36] M. Gamache, F. Soumis, G. Marquis, and J. Desrosiers. A column generation approach for large-scale aircrew rostering problems, Operations Research, 47(2), 247–263, 1999. [37] M.R. Garey and D.S. Johnson. Computers and Interactability: A Guide to the Theory of NP-Completness, Freeman, San Fransisco, 1979. [38] V. Gintner, I. Steinzen, and L. Suhl. A time-space network based approach for integrated vehicle and crew scheduling in public transport, In Proc. EWGT2006 Joint Conf., (eds. M. Binetti, F. Civitelle, E. De Liddo, M. Dell’orco, M. Ottomanlli), Bari, Italy, 371–377, 2006. [39] V. Gintner, N. Kliewer, and L. Suhl. A Crew Scheduling Approach for Public Transit Enhanced with Aspects from Vehicle Scheduling, In Computeraided Systems in Public Transport, (eds. M. Hickman, P. Mirchandani, and S. Voß), Lecture Notes in Economics and Mathematical Systems, 600, 25–42, Springer-Verlag, Heidelberg, 2008. [40] N. Guerinik and M.V. Caneghem. Solving Crew Scheduling Problems by Constraint Programming, In Proceedings of the 1st Conference of Principles and Practice of Constraint Programming, pp. 481–498, 1995. [41] K. Haase and C. Friberg. An exact branch and cut algorithm for the vehicle and crew scheduling problem, In Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, 471, (ed. N.H.M. Wilson), 63–80, Springer, Berlin, 1999. [42] K. Haase, G. Desaulniers, and J. Desrosiers. Simultaneous vehicle and crew scheduling in urban mass transit systems, Transportation Science, 35(3), 286–303, 2001. [43] A. Hadjar, O. Marcotte, and F. Soumis. A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem, Tech. Rept. G–2001–25, Les Cahiers du Gerad, Montreal, 2001.

36

[44] C. Hane, C. Barnhart, E.L. Johnson, R.E. Marsten, G.L. Nemhauser, and G. Sigismondi. The fleet assignment problem: Solving a large integer program, Mathematical Programming, 70(2), 211–232, 1995. [45] D. Huisman. Integrated and Dynamic Vehicle and Crew Scheduling, PhD thesis, Erasmus University of Rotterdam, Rotterdam, 2004. [46] D. Huisman, R. Freling, and A.P.M. Wagelmans. Multiple-depot integrated vehicle and crew scheduling, Transportation Science, 39, 491–502, 2005. [47] N. Kliewer, T. Mellouli, and L. Suhl. Solving large multiple-depot multiplevehicle-type bus scheduling problems in practice, OR Spectrum, 27(4), 507– 523, 2005. [48] N. Kliewer, T. Mellouli, and L. Suhl. A time-space network based exact optimization model for multi-depot bus scheduling, European Journal of Operational Research, 175, 1616–1627, 2006. [49] A. Kokott and A. L¨ obel. Lagrangean Relaxations and Subgradient Methods for Multiplie-Depot Vehicle Scheduling Problems, ZIB-Report 96–22, Konrad-Zuse-Zentrum f¨ ur Informationstechnik, Berlin, Germany, 1996. [50] R.S.K. Kwan, A.S.K. Kwan, and A.S.K. Wren. Evolutionary Driver Scheduling with Relief Chains, Evolutionary Computation, 9, 445–460, 2001. [51] B. Laurent and J-K. Hao. Simultaneous Vehicle and Crew Scheduling for Extra Urban Transports, In New Frontiers in Applied Artificial Intelligence, (eds. N.T. Nguyen, L. Borzemski, A. Grzech, and M. Ali), Lecture Notes in Computer Science Volume, 5027, 466–475, 2008. [52] J. Li. A Self-Adjusting Algorithm for Driver Scheduling, Journal of Heuristics, 11, 351–367, 2005. [53] J-Q. Li and K.L. Head. Sustainability provisions in the bus-scheduling problem, Transportation Research, Part D, 49, 50–60, 2009. [54] A. L¨ obel. Optimal Vehicle Scheduling in Public Transit, Ph.D. thesis, Technische Universitaet at Berlin, 1997. [55] A. L¨ obel. Vehicle Scheduling in Public Transit and Lagrangian Pricing. Management Science, 44, 1637–1649, 1998. [56] M. Meilton. Selecting and implementing a computer aided scheduling system for a large bus company, Algorithms: Combinatorial Analysis. In Computer-Aided Scheduling of Public Transport, (eds. S. Voss and J.R. Daduna), 203–214, Springer-Verlag, Berlin, 2001. [57] M. Mesquita and J. Paixao. Multiple Depot Vehicle Scheduling Problem: A New Heuristic Based on Quasi-Assignment Algorithms, In Computer-Aided Transit Scheduling, (eds. M. Desrochers and J.-M. Rousseau), Lecture Notes in Economics and Mathematical Systems, 386, 167–180, Springer-Verlag, Berlin, 1992. 37

[58] M. Mesquita and A. Paias. Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem, Computers and Operations Research, 35(5), 1562–1575, 2008. [59] M. Moz, A. Respcio, and M. Vaz Pato. Bi-objective Evolutionary Heuristics for Bus Drivers Rostering, Working Paper 1–2007, Centro de Investigaao Operacional, Universidade de Lisboa, 2007. [60] K. Nurmi, J. Kyngas, and G. Post. Driver Rostering for Bus Transit Companies, Engineering Letters, 19(2), 125–132, 2011. [61] A.-S. Pepin, G. Desaulniers, A. Hertz, and D. Huisman. Comparison of Heuristic Approaches for the Multiple Depot Vehicle Scheduling Problem, Journal of Scheduling, 12(1), 17–30, 2009. [62] A. Rabl. Environmental benefits of natural gas for buses, Transportation Research, Part D, 7, 391–405, 2002. [63] C.C. Ribeiro and F. Soumis. A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem, Operations Research, 42(1), 41–52, 1994. [64] J.L. Saha. An algorithm for bus scheduling problems, Operational Research Quarterly, 21(4), 463–474, 1972. [65] M. Segal. The operator-scheduling problem: A network-flow approach, Operations Research, 24, 808–823, 1974. [66] B.M. Smith and A. Wren. A bus crew scheduling system using a set covering formulation, Transportation Research, 22A, 97–108, 1988. [67] I. Steinzen. Instances for integrated vehicle and crew scheduling problems with multiple depots, Online elérhet˝o: http://dsor.uni-paderborn.de/index.php?id=bustestset& L=0. [68] I. Steinzen, V. Gintner, L. Suhl, and N. Kliewer. A Time-Space Network Approach for the Integrated Vehicle- and Crew-Scheduling Problem with Multiple Depots, Transportation Science, 4(3), 367–382, 2010. [69] U.U. Suhl, S. Friedrich, and V. Waue. Progress in solving large scale multi-depot multi-vehicle-type bus scheduling problems with integer programming, Wirtschaftinformatik Proceedings, Paper 81, 2007. http://aisel.aisnet.org/wi2007/81 [70] A. T´ oth and M. Krész. A flexible framework for driver scheduling, In Proceedings of the 11th International Symposium on Operational Research in Slovenia – SOR’11, 341–346, 2011. (ISBN: 978-961-6165-35-8)

38

[71] A. T´ oth and M. Krész. An efficient solution approach for real-world driver scheduling problems in urban bus transportation, Central European Journal of Operations Research, 21(Supplement 1), 75–94, 2013. DOI: 10.1007/s10100-012-0274-3. [72] A. Wren, S. Fores, A.S.K. Kwan, R.S.K. Kwan, M.E. Parker, and L. Proll. A flexible system for scheduling drivers, Journal of Scheduling, 6(5), 437– 455, 2003. [73] A. Wren and B.M. Smith. Experiences with a crew scheduling system based on set covering, In Computer-aided transit scheduling, (eds. J.R. Daduna and A. Wren), Lecture Notes in Economics and Mathematical Systems, 308, 104–118, Springer-Verlag, Berlin, 1988. [74] T. Yunes, A. Moura, and de C. Souza. Hybrid Column Generation Approaches for Solving Real World Crew Management Problems, Transportation Science, 39(2), 273–288, 2005.

39

Kivonat. elősegíthető. Egy ilyen optimalizálási feladat nagyon komplex, ezért a

Recommend Documents