Alkalmazott Matematikai Lapok 31 (2014), alkalmazott modellek és az azokat megoldó algoritmusok olyan jelentősen fejlődtek,

Alkalmazott Matematikai Lapok 31 (2014), 1-40.

´ FELADATOK AZ AUTOBUSZOS ´ ´ ´ ¨ ¨ OSS ¨ EGI ¨ UTEMEZ ESI KOZ KOZLEKED ES ´ ´ ´ ´ ´ OPERATIV TERVEZESEBEN: EGY ATTEKINTES ´ ´ VIKTOR, BALOGH JANOS, ´ ´ ESI ´ JOZSEF, ´ ´ ´ ARGIL AN BEK DAVID BALAZS, ´ ´ ´ TOTH ´ GALAMBOS GABOR, KRESZ MIKLOS, ATTILA

A k¨ ozlekedési t´ arsas´ agok sz´ am´ ara lényeges szempont 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 o¨temezésével is el˝ seg´ıthet˝ o. Egy ilyen optimaliz´ al´ asi feladat nagyon komplex, ezért a m˝ uveletek u arom f´ azisra bontva t´ argyaljuk. Ezek a j´ arm˝ uu ¨temezését h´ ¨temezés, a vezet˝ ou uszakkioszt´ as feladatai. Ezek a részfeladatok ´ alta¨temezés és a m˝ l´ 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 ´ attekintj¨ 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 ´ altalunk tanulm´ anyozott és bevezetett megold´ asi m´ odszereire is.

1. Bevezet´ es A k¨ oz¨ osségi közlekedési szolgáltató v´ allalatok kiad´ asainak nagy részét az operat´ıv k¨ oltségek alkotják. Ez jórészt a járm˝ uflotta költségéb˝ol, a járm˝ uvek u ¨zemanyag- és karbantartási költségéb˝ol, valamint a járm˝ uvezet˝ok fizetéséb˝ ol tev˝ odik ol k¨ ovetkez˝oen az operat´ıv költségekben mutatkoz´ o megtakar´ıtás sz´ aössze. Ebb˝ mottev˝ o jav´ıt´ ast adhat költségvetés¨ ukben. A leggyakrabban haszn´ alt módszer ezeknek a k¨ oltségeknek a csökkentésére egy hatékony, sz´ am´ıtógéppel támogatott informáci´ os rendszer kialak´ıtása és haszn´ alata. Az IKT (információs és telekommunik´ aci´ os technológia) fejl˝ odésének köszönhet˝oen napjainkra szinte minden közösségi k¨ ozlekedési társaság – modern v´ allalatirány´ıtási környezetet biztos´ıtva – rendelkezik saját informáci´ os rendszerrel. Ezeknek a rendszereknek a f˝o funkciói az u asokon t´ ul (´ ugymint ¨zleti alkalmaz´ könyvelés, sz´ amvitel stb.) olyan modulokat is tartalmaznak, amelyek – el˝ okész´ıtik a járm˝ uvek u ¨temezését a vállalat által kiszolgált vonalakhoz, Alkalmazott Matematikai Lapok (2014)

2

´ ´ VIKTOR, BALOGH JANOS, ´ ´ ESI ´ JOZSEF, ´ ´ ´ ARGIL AN BEK DAVID BALAZS, ´ ´ ´ TOTH ´ GALAMBOS GABOR, KRESZ MIKLOS, ATTILA

– illesztik a járm˝ uvek és a járm˝ uvezet˝ok m˝ uszakjainak u ¨temezését a vonalakhoz, – képesek a járm˝ uflotta nyomon követésére és monitorozására egy-egy nap során, – jelzik a diszpécsernek a szokatlan eseményeket (meghib´ asodás, késés stb.), – nyomon k¨ ovetik a járm˝ uflotta járm˝ uveinek állapotát, és más hasonl´ o tevékenységeket. Az IKT-k¨ ornyezet alapvet˝o h´ attérként szolgál a hatékony logisztikai irány´ıtásra (l´ asd pl. [56]), ugyanakkor a folyamatban jelen van egy másik elv´ arás, amely azt k´ıv´ anja, hogy találjuk 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öntéstámogatási eszköz létezik, amely a logisztikai rendszertervezési és optimalizálási feladatok komplett megoldását célozza. A gyakorlatban ennek ellenére kider¨ ul, hogy sok v´ allalatspecifikus részlet, korlátoz´ o feltétel van jelen, amelyeket az általános rendszerek nem kezelhetnek egységesen, de amelyek fontosak a k¨ ozlekedési v´ allalatok sz´ am´ ara. Példaként eml´ıtj¨ uk, hogy amennyiben a k¨ ozlekedési társaság alternat´ıv u u járm˝ uveket is alkalmaz flottáj´ anál, ¨zemanyag´ akkor ezek u ¨temezésénél figyelembe kell venni a szaknyelven rádiusznak nevezett, egy tankol´ assal megtehet˝o kilométerek sz´ am´ at, amely jóval kevesebb lehet, mint a hagyom´ anyos u uköd˝ o járm˝ uvek futási teljes´ıtménye. Ilyen ese¨zemanyagokkal m˝ teket vizsgáltak [62]-ben és [53]-ban. Alternat´ıv u u járm˝ uveknél fontos ¨zemanyag´ tényez˝ o a tankolás id˝otartama is. Am´ıg hagyományos u al (pl. d´ızel¨zemanyagokn´ olaj) 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öbbszöröse 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 uljön, ezeket a feltételeket sz´ am´ıtásba kell venni a napi u ¨temezés kész¨ ¨temezést elkész´ıt˝ o szoftvernél. Legjobb tudom´ asunk szerint napjaink u o szoftve¨temez˝ rei nem kezelnek ilyen jelleg˝ u feltételeket, vagy azokat csak korlátozott mértékben veszik figyelembe. K¨ ovetve a közösségi közlekedé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ároz´ 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örfer [14] a stratégiai és a taktikai tervezést közös, u ń. szolg´ al” tat´ astervezési” fázisba vonja össze. Megeml´ıt olyan kapcsolódó – a szolgáltatástervezés k¨ orébe sorolható – feladatokat (pl. jegy´ araz´ as, tarifatervezés és -kialak´ıtás), Alkalmazott Matematikai Lapok (2014)

´ FELADATOK A KOZ ´ ´ ¨ ¨ OSS ¨ EGI ¨ UTEMEZ ESI KOZLEKED ESBEN

3

amelyek az utazási igényeket is meghatározhatják. Az ilyen jelleg˝ u feladatokat – és a hozzájuk tartoz´ o modelleket – ebben a cikkben nem tárgyaljuk. Annak, hogy mi csak az eml´ıtett operat´ıv tervezési részfeladatok t´ argyalására szor´ıtkozunk, a terjedelmi korlátokon t´ ul az is az oka, hogy a közösségi közlekedési szolgáltató vállalatoknak a többi eml´ıtett stratégiai és taktikai tervezési feladatra kevés befolyásuk van: ezek általában az állami kormányzati vagy helyi anyzati (pl. városi) szervek által meghatározottak. Azon k´ıv¨ ul, hogy a önkorm´ járatok milyen s˝ ur˝ un kövessé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áltat´ ast ell´ ató járm˝ uvek speciális tulajdons´ agaira is lehetnek el˝o´ırások. Egy jellemz˝o példa az, hogy melyik vonalon milyen id˝oközzel közlekedjenek alacsonypadl´ os járm˝ 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át járm˝ uflottájukat hogyan u uvezet˝oiket hogyan oszt¨temezik, és a járm˝ ják be m˝ uszakokba rövid- és hossz´ utávon egyar´ ant. Az már 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 ozel´ıtés megvalós´ıthatatlannak látszik, ezért olyan részproblémákra összetett megk¨ 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ázis, ha nem is szorosan, de általában mégis hatnak egymásra annak érdekében, hogy glob´ alisan hatékonyabb – vagy legalább lehetséges – megold´ as legyen nyerhet˝o. A tudom´ anyos közössé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ális – vagy k¨ ozel optimális – megold´ asok 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´ any sz´ azezer f˝os lakoss´ ag´ u v´ arosok – esetén is elég összetett, komplex feladattal állunk szemben, amely még ¨ osszetettebbé v´ alik, ha a részleteket is figyelembe kell venn¨ unk. Még bonyolultabb´ a teszi a problémát, ha olyan korl´ atokat is kezelni kell, amelyeket a jogszab´ alyok, a szakszervezetek, az egyéni igények és egyéb gyakorlati feltételek hat´ aroznak meg. Ezek péld´ aul a járm˝ uvezet˝ok vezetési idejére, munkaidejére, pihen˝ oidejére és munkaközi sz¨ uneteire vonatkoz´ o el˝o´ırások. Ilyen további korl´ atozó feltételeket adhatnak a telephelyek kötöttségein, kapacitásán és egyéb feltételein Alkalmazott Matematikai Lapok (2014)

4


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 nem kedvelt m˝ uszakok. Ehhez az ut´ obbihoz kapcsolód´ oan megeml´ıtj¨ uk, hogy például Abbink és szerz˝otársai 2007-ben publikált cikke [1] tárgyal egy vas´ uti m˝ uszakkiosztási példát. Nem célunk sem a hál´ 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ához. Annak ellenére, hogy felv´ azoltuk a (buszos) tömegközlekedési rendszerek által´ anos strukt´ ur´ aját, mi a jelen tanulmányban az operat´ıv tervezés egyes fázisait vizsgáljuk. Ezen bel¨ ul a buszflotta járm˝ uveinek u uvezet˝ok m˝ usza¨temezésére, a járm˝ konkénti u ¨temezésére és beosztására fogunk koncentrálni. A munkaer˝o u ¨temezését tov´ abbi részfeladatokra bontjuk: k¨ ulön fejezetben tárgyaljuk a járm˝ 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övetkez˝o. Mint l´ atni fogjuk, a legutóbbi id˝okig kidolgozott eljár´ asok a két u ¨temezési problémát egymás után végrehajtva oldják meg. A járm˝ uu ¨temezés eredményeire támaszkodva keresnek optimális – vagy közel optimális – 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özel´ıtések, amelyek a járm˝ u- és vezet˝o-¨ utemezési problém´ at egy¨ utt kezelik, és egyszerre pr´ ob´ alják megoldani. Figyelembe véve az algoritmusokban bekövetkez˝ o jav´ıtásokat és a hardverek rohamosan növekv˝o sz´ am´ıtási kapacitását, 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´ alt modellek kidolgozására szolgáló kutatások áttekintésének. A k¨ ovetkez˝ o fejezetekben el˝oször általánosan – moduláris szerkezetben – vizsgáljuk a feladatokat, majd alfejezetenként részletesen tárgyaljuk az ismert megold´ asi módszereket.

2. A j´ arm˝ uu esi feladat ¨ temez´ 2.1. A feladatr´ ol ´ altal´ aban, defin´ıci´ ok, jelo esek ¨l´ A járm˝ uu al (Vehicle Scheduling Problem, VSP) adott a j´ ar¨temezési problémán´ m˝ uflotta j´ arm˝ uveinek és a menetrendi j´ aratoknak a halmaza. 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ázu u). Ha t¨ obb – eltér˝o t´ıpus´ u – járm˝ uv¨ unk van, akkor a járm˝ uvek halmaz´ at ¨zem˝ diszjunkt 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árm˝ uflotta elemeit rendelj¨ uk hozzá az egyes járatokhoz u ´gy, hogy a Alkalmazott Matematikai Lapok (2014)


5

hozz´ arendelés ¨ osszköltsége minimális legyen. Az els˝ o pillanatban egyszer˝ u hozzárendelési feladatnak t˝ un˝o probléma azért bonyolódik meg, mert nem kell minden járm˝ uvet járathoz rendelni, és egy járm˝ u – a járatok id˝obeli eltolódása miatt – több járathoz is hozzárendelhet˝o. További korlátozó feltételt jelenthet az, hogy minden járatot pontosan egyszer kell végrehajtani, és – esetleg további feltételek alapján – minden járm˝ u legyen képes végrehajtani azokat a járatokat, amelyekhez a megold´ asunk 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áratot kompatibilisnek (ebben a sorrendben egymás ut´ an végrehajthatónak, uzhet˝ onek) nevezz¨ uk, ha ugyanaz a járm˝ u képes kiszolgálni egymás ut´ an összef˝ ˝oket, azaz at(ui ) ≤ dt(uj ), és dt(uj ) − at(ui ) kisebb, mint a dg(uj ) és ag(ui ) közti távols´ ag megtételéhez sz¨ ukséges id˝o. Az 1. és a 2. ábra egy-egy, néh´ any járatból áll´ o sematikus szitu´ aciót mutat. A sematikus ábrákon szaggatott nyilak jelzik a kompatibilis járatp´ arokat (itt a v´ızszintes tengely reprezent´ alja az id˝ot, a földrajzi helyek nincsenek ábrázolva), csak akkor köt¨ unk össze szaggatott ny´ıllal két járatot, ha egym´ assal kompatibilisek. Az 1. ábrán jelzett sematikus szituációban ilyen módon 3 járm˝ u elég a 6 járat ell´ atásához, m´ıg a 2. ábráén ehhez már 4 járm˝ u kell.

1. ´ abra. 6 járatot ábrázoló sematikus feladat. A szaggatott nyilak jelzik az egymással kompatibilis járatokat. Az ábra jobb oldali része azt illusztr´ alja, hogy a feladat 3 járm˝ uvel megoldható. Az u uvek dep´ okban állnak, és az u ¨temezési id˝oszak kezdetén a járm˝ ¨temezési id˝ oszak végén oda is térnek vissza. Dep´ oba ker¨ ulhet egy járm˝ u az u ¨temezési id˝oAlkalmazott Matematikai Lapok (2014)

6


2. ´ abra. Az 1. ábráéhoz hasonló sematikus szituáció, de itt az ottaninál kevesebb járat kompatibilis egymással, ´ıgy ez a feladat csak 4 járm˝ uvel oldhat´ o meg.

szak bármely id˝opontjában, ha hosszabb ideig nem rendel¨ unk hozzá járatot. Depó lehet garázs, parkolóhely vagy telephely, attól f¨ ugg˝oen, hogy a járm˝ u hol parkol. A dep´ ok számától f¨ ugg˝oen beszélhet¨ unk egydepós (Single Depot Vehicle Scheduling Problem, SDVSP) és többdepós (Multiple Depot Vehicle Scheduling Problem, MDVSP) járm˝ uu obbdepós esetben az is el˝o lehet ´ırva, ¨temezési feladatról. A t¨ hogy melyik járatot melyik depókhoz tartozó járm˝ uvek hajthatják végre. A menetrendi járatokon k´ıv¨ ul, amelyek sz´ all´ıtanak utast, megk¨ ulönböztet¨ unk aratr´ ol. olyan járatokat is, amelyek nem sz´ all´ıtanak utast. Ekkor beszél¨ unk rezsij´ Ez ut´ obbiak k¨ ozé tartozik a dep´ oból történ˝ o ki- és beáll´ as, valamint két kompatibilis menetrendi járat esetén az els˝ o járat érkezési és a második járat indulási f¨ oldrajzi helye k¨ ozötti átállás. Egy járm˝ uu anca, amelyben minden egymást ¨temezése járatoknak egy olyan l´ ´ követ˝ o két menetrendi járat egymással kompatibilis. Altal´ aban egy járm˝ u u ¨temezése a gyakorlatban egy járm˝ u egy napi munkájának el˝o´ırását jelenti, amit járm˝ um˝ uszaknak (szakszóval járm˝ ufordának vagy eszközford´ anak) is nevez¨ unk. A járm˝ u egy érvényes u allási járattal kezd˝ odik, és egy beállási ¨temezése egy ki´ járattal végz˝ odik. A 3. ábra a 2. ábrának megfelel˝o sematikus szituáció egy érvényes járm˝ uu ov´ıtett megoldását mutatja. Itt feltett¨ uk, hogy ¨temezésekké kib˝ egy dep´ o van (egydep´ os eset), és a depób´ ol valamennyi járat indulási helyére és érkezési helyér˝ol a depóba vezetnek depóki´ all´ asi és -beállási járatok). Alkalmazott Matematikai Lapok (2014)


7

3. ´ abra. A 2. ábrán l´ atható sematikus szituáció megoldása egy depó esetén a dep´ o ki- és beállási járatokkal érvényes járm˝ uu ¨temezéseket alkot.

A járm˝ uu uflotta járm˝ u¨temezés alapfeladata abból áll, hogy adjuk meg a járm˝ veinek u ´gy, hogy minden egyes menetrendi járat hozzá ¨temezését a fenti módon u legyen rendelve pontosan egy járm˝ u u ¨temezéséhez, és minden menetrendi járat a megfelel˝ o depók valamelyikéb˝ol legyen végrehajtva. (Természetesen lehetnek olyan járm˝ uvek is, amelyek az adott, (pl. egy napi) u ¨temezésben nem vesznek részt.) Célf¨ uggvényként kezelhetj¨ uk az u uvek sz´ am´ a¨temezésben használt járm˝ nak a minimalizálását, de definiálható más költségf¨ uggvény is. A cél akkor a k¨ oltségf¨ uggvény minimaliz´ alá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´ o átal´ anyköltséget, valamint operat´ıv költséget is. Az átalányköltségen azt a költséget értj¨ uk, amely abból keletkezik, hogy egy adott járm˝ u a depóban rendelkezésre áll. Ez lehet a beszerzési, fenntartási, karbantartási stb. költségekb˝ ol vet´ıtett átlag. Az operat´ıv költség által´ aban a megtett távolságokkal ar´ anyos, azonban k¨ ulönböz˝ o lehet attól f¨ ugg˝oen, hogy melyik depóból sz´ armaz´ o járm˝ u l´ atja el az adott feladatot. A járatok operat´ıv k¨ oltsége att´ ol is f¨ ugghet, hogy rezsi-, vagy menetrendi járatról van-e sz´ o, mivel k¨ ul¨ onb¨ oz˝ o lehet a kilométerek egység´ ara”. Több modell képes u ´gynevezett ” dep´ okapacit´ asi korl´ atozó feltételek kezelésére is, azaz lehetséges megold´ asnak csak olyan megold´ asokat tekint, amely figyelembe veszi minden depó esetén az ahhoz tartoz´ o járm˝ uvek maximális sz´ am´ at. Alkalmazott Matematikai Lapok (2014)

8


A célf¨ uggvényben az u uvek általános (pl. a fenntartási költsé¨temezett járm˝ gekb˝ ol ad´ od´ o) és utazási (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 által´ aban a megfelel˝o u ´t hosszával ar´ anyos, ugyanakkor a menetrendi járatok és a rezsij´ aratok kilométereihez eltér˝o költségek is tartozhatnak. Természetesen a rezsijáratok k¨ oltségei ´ıgy f¨ uggenek a megfelel˝o földrajzi helyek közötti távolságoktól, k¨ ovetkezésképpen eltér˝o lehet a rezsijáratok k¨ oltsé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ára, amelyeket az el˝oz˝ o évtizedekben dolgoztak ki. A következ˝ o alfejezetekben áttekintj¨ uk a feladatok néhány alapvet˝o megoldási módszerét. A napjainkban talán legszélesebb kör˝ uen haszn´ alt MDVSP-modellekben a probléma egy egészérték˝ u többtermékes h´ alózati folyam problémaként fogalmaz´ odik meg (l´ asd [13, 48, 54]). Ebben a modellben az optimális u u ¨temezést egy egészérték˝ line´ aris programozási feladat megoldásaként sz´ am´ıthatjuk ki. A probléma megfogalmazhat´ o halmazlefedési vagy halmazpart´ıcionálási feladatként is (lásd péld´ aul [43, 63]). 2.2. Az egydep´ os j´ arm˝ uu esi feladat ¨ temez´ Az SDVSP-problémára adott els˝ o megold´ asi módszert Saha [64] publik´ alta. Az U járathalmaz elemeire egy részleges rendezést definiál, és bevezetésre ker¨ ul egy β rendezési rel´ ació, mely szerint akkor szolgálható ki u2 leg´ alisan u1 után, ha ag(u1 ) = dg(u2 ), valamint at(u1 ) ≤ dt(u2 ). A megkötésekb˝ol l´ atható, 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ározott β rel´ ació a fent definiált kompatibilitásnál gyengébb. Az SDVSP-re több p´ aros gráfon alapul´ o modellt is publikáltak. Ezekr˝ol b˝ ovebb áttekintés található Bunte és Kliewer [16] munkáj´ aban. Mi az alábbiakban Bertossi és társai [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, minden i ∈ G1 cs´ ucs egy-egy járat érkezésének (érkezési földrajzi helyének), m´ıg minden j ∈ G2 cs´ ucs egy-egy járat 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ábbá, 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áf a következ˝o módon értelmezhet˝o (l´ asd a 4. ábrán egy egyszer˝ u, sematikus feladat illusztrációját). Az (i, j) ∈ E1 élek két kompatibilis ui és uj járat érkezési és indulási földrajzi helyei közti lehetséges rezsijáratot jelképezik, Alkalmazott Matematikai Lapok (2014)


9

4. ´ abra. Az 1. ábrán l´ atható sematikus szitu´ aci´ ohoz tartoz´ o p´ aros gr´ af 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 ábrázolják itt. m´ıg minden (i, j) ∈ E2 él két egymás ut´ ani rezsijáratnak felel meg. Ezek köz¨ ul az els˝ o az ui járat érkezési földrajzi helyér˝ol a depóba, majd a másik a depób´ ol az uj járat indul´ asi földrajzi helyére. Ezek seg´ıtségével l´ atható, hogy a G gr´ af egy M teljes p´ aros´ıt´ asa egy lehetséges járm˝ uu uvek ¨temezést fog adni, melyben a járm˝ sz´ ama |M ∩ E2 |. Az (i, j) élekhez ci,j költségeket rendelve az SDVSP feladata megfeleltethet˝o egy minimális költség˝ u teljes páros´ıtás keresésének a G gr´ afban. – Ha ci,j = 1 minden (i, j) ∈ E2 esetén, és ci,j = 0 egyébként, u ´gy a feladat megoldásával 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öltségek valamely kombin´ aciója is használható. A gyakorlati életben a probléma kiegész¨ ul még a járm˝ uvek darabszám´ ara adott korláttal. Legyen ez a korlát k. Ekkor egy korl´ atos p´ aros´ıtási feladatot kapunk, ahol a feladat a minimális költség˝ u p´ aros´ıtást megkeresni a gráfban az |M ∩ E2 | ≤ k feltétel mellett. A probléma formálisan a következ˝oképpen adható meg: legyen x bináris v´ altoz´ ok vektora, ahol xi,j = 1, ha az (i, j) él az M p´ aros´ıtáshoz tartozik, k¨ ulönben xi,j = 0, és legyen c a költségvektor. Az X lehetséges megoldások halmaz´ at az Alkalmazott Matematikai Lapok (2014)

10


alábbi feltételeknek megfelel˝o vektorok határozzák meg: ∑ xi,j = 1, i = 1, 2, . . . , n∗ , j

∑

xi,j = 1,

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

i

∑

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ális költség˝ u h´ alózati folyamproblémaként is megoldható (lásd [16]). A h´ alózat konstruálása ekkor annyiban tér el a fent definiált gráftól, 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árat indulását és a járat érkezését reprezentáló cs´ ucsra, melyeket egy, a járatot jelz˝o éllel köt¨ unk össze. Ezeknek a járat éleknek az als´ o és fels˝ o korlátja is 1 lesz, ´ıgy biztos´ıtva azt, hogy minden járat pontosan egy alkalommal ker¨ uljön teljes´ıtésre. Ennek az a következménye, hogy az ezeken az éleiken felmer¨ ul˝o költségek egy konstans többletként jelentkeznek, ami a feladat célf¨ uggvényére nincs hatással. A járatok cs´ ucsaihoz hasonlóan a depót jelképez˝ o cs´ ucs helyett is egy depóindulási, illetve depóérkezési cs´ ucsot vezet¨ unk be. Ezeket egy 0 k¨ oltség˝ u éllel kötj¨ uk össze, mely a h´ alózat depókörfolyam éle lesz. Ha a fentiek szerint korlátozzuk a rendelkezésre áll´ o eszközök sz´ am´ at, u ´gy ennek az élnek a kapacit´ asa k lesz. Ezt a fajta formalizmust használva Ahuja és munkatársai bebizony´ıtott´ ak, hogy a feladat er˝ osen polinomiális id˝oben megoldható [3]. 2.3. A t¨ obbdep´ os j´ arm˝ uu esi feladat ¨ temez´ A járm˝ uu asára leggyakrabban haszn´ alt modell az u ´gy¨temezési feladat megold´ nevezett t¨ obbdepós járm˝ uu ¨temezési probléma (Multiple Depot Vehicle Scheduling Problem, MDVSP) modellje. A valós életben a k¨ ulönböz˝ o menetrendi járatokra és a járm˝ uvekre speciális igények vonatkozhatnak. Az eltér˝o járm˝ ut´ıpusok, valamint a járm˝ uvek tart´ ozkod´ asi helye alapján a járm˝ uveket k¨ ulönböz˝ o depókba oszthatjuk, ´ıgy a járatok kiszolgálása – az igényekt˝ol f¨ ugg˝ oen – k¨ ulönböz˝ o depókb´ ol történhet. A t¨ obbdep´ os járm˝ uu ¨temezé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˝ uu ¨temezési probléma legfontosabb komponenseit. A matematikai modellek ismertetése során jelöléseinkben a L¨ obel által haszn´ alt terminológi´ at követj¨ uk [54]. A t¨ obbdep´ os járm˝ uu al minden menetrendi járat esetén a fel¨temezési feladatn´ haszn´ al´ o megadja azokat a depókat, ahonnan az adott járat kiszolgálható. A gyakorlatban ez jelentheti péld´ aul azt, hogy bizonyos járatok csak csukl´ os busszal Alkalmazott Matematikai Lapok (2014)


11

l´ athat´ ok el, és az is megadható, hogy mely esetben mely telephelyhez tartozzanak. Ezeket az el˝o´ır´ asokat a telephely és az állom´ as elhelyezkedése, valamint a forgalom jellemz˝oi hat´ arozhatjá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ál´ o hál´ ozat felép´ıtésének módszerében rejlik. Ezek alapján megk¨ ulönböztet¨ unk kapcsolatalap´ u és id˝o-tér hálózati modellt. Egy másik megközel´ıtésben a problém´ at halmazpart´ıcion´ alási, illetve halmazlefedési feladatként modellezik. Ezt a modellt elemezték például Ribeiro és Soumis [63], vagy Hadjar és szerz˝otársai [43]. 2.3.1. A kapcsolatalap´ u t¨ obbterm´ ekes h´ al´ ozati modell A kapcsolatalap´ u többtermékes h´ alózati folyam (connection-based multicommodity network flow) modell széleskör˝ uen használt az MDVSP-probléma megold´ asára. Sok, a témába v´ ag´ o kutatás fókuszált ennek alkalmazására. Intenz´ıven tanulmányozt´ ak a generált egészérték˝ u programozási feladat megold´ asi módszereinek fejlesztésében rejl˝o lehet˝oségeket. Sz´ amos megközel´ıtés alapul heurisztikus, k¨ ozel´ıt˝ o módszerekre (l´ asd [23, 54, 57]), m´ıg mások pontos megold´ ast szolgáltató, egzakt algoritmusokat tárgyaltak (lásd [49, 55]). Miel˝ ott rátér¨ unk a modell le´ırására, a kor´ abban bevezetett jelölések mellé u ´j defin´ıci´ okat is meg kell adnunk. Jelölje D a depók halmaz´ at, és Du ⊆ D egy u menetrendi járat depóhalmaz´ at: ez azokat a depókat tartalmazza, amelyekb˝ol ki lehet kiszolg´ alni az u járatot. Jelölje Ud ⊆ U azoknak a járatoknak a halmazát, amelyek kiszolg´ alhatók a d depób´ ol. Hasonlóan, minden d ∈ D esetén definiálunk két, dt(d) és at(d) – depóindul´ asi és depóérkezési – cs´ ucspontot a h´ alózatban; ezek szimboliz´ alják azt, hogy a járm˝ u a d depóból indul, és oda érkezik vissza. A h´ alózat cs´ ucspontjainak N halmazát ezek ut´ an a következ˝o módon definiáljuk 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ához vezess¨ uk be a következ˝o jelöléseket. Egy d dep´ ohoz tartoz´ o menetrendi járatok halmaz´ ahoz rendelj¨ uk a következ˝o irány´ıtott éleket: Ed = {(dt(u), at(u))|u ∈ Ud },

∀d ∈ D.

Rendelj¨ unk irány´ıtott élt a d depó minden u járatának érkezési idejét reprezentál´ o cs´ ucsb´ ol az u-val kompatibilis – szintén d-beli – járatok indulási id˝opontjához rendelt cs´ ucsba: Bd = {(at(u), dt(u′ )) | u, u′ ∈ Ud kompatibilis járatok},

∀d ∈ D.

Bd élei rezsijáratok. További, a d depóhoz tartoz´ o nem menetrendi járatok, amelyekhez éleket kell rendelni a h´ alózatban, alkotják a depóhoz tartozó kiállási Alkalmazott Matematikai Lapok (2014)

12


5. ´ abra. A kapcsolatalap´ u modell h´ alózata egy kétdepós feladat péld´ aja 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 o¨ssze éllel, ahol a megfelel˝o járatok kompatibilisek.) és beáll´ asi élek halmazát: 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´ o járm˝ uvek sz´ am´ ara, akkor sz¨ ukség¨ unk van az u ń. dep´ ok¨ orfolyam” élek halmazának definiá” l´ asára is: Kd = {(at(d), dt(d))}, ∀d ∈ D. Ezek alapján meg tudjuk adni a hálózat d dep´ ohoz tartoz´ o éleinek a halmazát: Ad = Ed ∪ Bd ∪ Rd ∪ Kd ,

∀d ∈ D,

és a gr´ af ¨ osszes éleinek halmaza E = ∪d∈D Ad . A kapcsolatalap´ u modell hálózatának felép´ıtését az 5. ábra szemlélteti. Ezen el˝okész¨ uletek után most már készen állunk arra, hogy defini´ aljuk az MDVSP-feladatot a G = (N, E) hálózaton. Ehhez definiálunk egy egészérték˝ u x vektort, amely egy többtermékes folyamként is tekinthet˝o. A vektor dimenziója Alkalmazott Matematikai Lapok (2014)


13

megegyezik a hálózat éleinek sz´ am´ aval. A vektor e ∈ E élhez tartoz´ o komponensét xde -vel jel¨ olj¨ uk, ha az e él a d depóhoz tartozik (e ∈ Ad ). Az xde komponens é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ól 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´ atozó feltételeket definiálunk, amelyek a feladat k¨ ovetelményeit biztos´ıtják. ¨ Utemez´ es¨ unkben biztos´ıtani kell azt, hogy minden menetrendi járatot pontosan egyszer hajtsunk végre. Ez azt jelenti, hogy egy lehetséges megold´ asban csak olyan járm˝ uu ¨temezések szerepelhetnek, amelyeknek – a depókörfolyam élekt˝ol eltekintve – nincs k¨ oz¨ os él¨ uk. Ezt a következ˝o feltételekkel érhetj¨ uk el: ∑ xde = 1, ∀u ∈ U. d∈Du ,e=(dt(u),at(u))∈Ed

Biztos´ıtanunk kell azt is, hogy az u u visz¨temezési id˝oszak végére minden járm˝ szaálljon egy depóba. Ez más megfogalmazásban azt jelenti, hogy ha egy adott dep´ ohoz tartoz´ o járm˝ u egy – depótól eltér˝o valamelyik – cs´ ucsra (állom´ asra) megérkezik, azt el is kell hagynia. ∑ ∑ xde = 0, ∀u ∈ U, ∀n ∈ N, xde − e∈n+

e∈n−

ahol n+ jel¨ oli az n ∈ N cs´ ucsból induló élek halmazát, és hasonl´ oan, n− az n ∈ N cs´ ucsba fut´ o élek halmaza. Ha vannak depókapacitást korlátozó feltételek, akkor azokat a depókörfolyam élekhez kell kapacitásként, vagyis a folyamértékre vonatkoz´ o 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ása lesz. Amennyiben optimális 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´ asá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árat k¨ oltségét reprezentálja. Amennyiben egyszer˝ uen a járm˝ uvek sz´ amát szeretnénk minimalizálni (ekkor a flottaminimalizálási feladatnak nevezett problémár´ ol van sz´ o), akkor a kiáll´ asi é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öltséget, akkor a feladat célf¨ uggvénye: ∑ min c e xe . e∈E

Alkalmazott Matematikai Lapok (2014)

14


Ez a fenti korl´ atoz´ o feltételekkel egy¨ utt tekintve egy egészérték˝ u (IP) programozási feladatot hat´ aroz meg, amelynek megold´ asa – bizonyos értelemben – rutinfeladat. Ennek megold´ asával 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ózatra. Ez már egy közepes, néhány sz´ azezer lakos´ u v´ arosnál is el˝ofordulhat, és egy ilyen esetben a lehetséges rezsiátmenetek sz´ ama milliós nagys´ agrend˝ u is lehet. Ennek az oka az, hogy a kapcsolatalap´ u hálózat minden élt tartalmaz, ahol akár csak elméletileg is lehetséges (rezsi)átmenet (az adott két járat elméletileg kompatibilis egymással). A végs˝o megold´ asba 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ökkenté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ársai 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 (rep¨ ul˝ oj´ aratok u alták kor´ abban (lásd pl. [44]), a járm˝ uu ¨temezésénél) már haszn´ ¨temezés ter¨ uletén [48] az els˝ o id˝o-tér módszert tárgyaló publikáci´ o. A modell f˝o v´ıvmánya, hogy nagyobb méret˝ u, a gyakorlatban el˝ oforduló problém´ akat is meg lehet vele oldani. A modell két dimenzi´ ot haszn´ al, ezek az id˝o és a tér. A tér sz´ o jelentése itt az, hogy melyik f¨ oldrajzi helyr˝ol (állomásról) van sz´ o, 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 állom´ ashoz tartozik egy id˝ovonal, és az állom´ as minden lehetséges indul´ asi és érkezési id˝opontjához egy cs´ ucspontot definiálunk annak id˝ovonalán. (Ha több, k¨ ulönböz˝ o járat ucspont tarindul´ asi, vagy érkezési id˝opontja egybeesik, azokhoz egy összevont” cs´ ” tozik.) K¨ onny˝ u észrevenni, hogy a két modell közötti alapvet˝o k¨ ulönbség az, hogy az id˝ opontok itt helyekhez vannak kötve. Így a hálózat N cs´ ucshalmaz´ at az állomásokhoz tartozó indulási és érkezési id˝opontok adják. Minden d ∈ D depó esetén hasonl´ oan definiálhatjuk Ed -t, mint a kapcsolatalap´ u modellben. Természetesen a dep´ okhoz is id˝ovonalakat adunk meg, ´ıgy hasonlóan definiálható Rd is. A legf˝ obb k¨ ulönbség azonban a két modell között a rezsijáratok defin´ıciójában rejlik. Az id˝o-tér h´ alózati modellben ugyanis az id˝ovonalak haszn´ alatával lehet˝oujts¨ uk”, összevonjuk több rezsijárat lehetséges folyaség ny´ılik arra, hogy összegy˝ ” mát. Így nem feltétlen¨ ul sz¨ ukséges minden egyes lehetséges rezsijáratot k¨ ulön éllel reprezent´ alni, hanem megfelel˝ o rezsiátmenetekhez tartoz´ o éleket összevonhatunk egyetlen éllé. A szerz˝ok [48]-ban az u ´gynevezett utols´ o-els˝ o egyezési stratégiát alkalmazt´ ak. Ennek alapgondolata egy kétfázis´ u összevonási stratégia: Alkalmazott Matematikai Lapok (2014)


15

6. ´ abra. Egy egyszer˝ u példa id˝o-tér h´ alózatra [10]. – Az els˝ o fázisban minden egyes járat érkezését jelképez˝ o cs´ ucspontból az osszes t¨ obbi állomás esetén csak a másik állom´ as els˝ o olyan járatához ve¨ zet˝ o, rezsijáratot jelent˝o élt h´ uzzuk be, amely járatunkkal id˝oben az els˝o kompatibilis járat a másik állom´ ason. 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ázis után egy adott állomásnak az indulást jelképez˝ o cs´ ucspontjaiba mindegyik másik állom´ asró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´ amát. Most ker¨ ul sor arra, hogy összevonjuk a beérkez˝ o rezsiéleket. A második fázisban egy adott állom´ as 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´ asról érkez˝o, els˝ o egyezést jelent˝o élek köz¨ ul csak a legkés˝ obb indulót hagyjuk meg. Ezt nevezz¨ uk utols´ o-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´ abbi cs¨ okkentése lehetséges. Ezért a Bd halmaz az összes rezsijáratnak csak egy részét fogja tartalmazni. Ezen a módon csökkenthet˝o a k¨ ulönböz˝ o állomások között rezsiélek sz´ ama. Azonban, hogy teljessé tegy¨ uk a modellt, ahhoz mindegyik állomáshoz be kell vezetni az állom´ ason bel¨ uli cs´ ucspontokat összeköt˝o, u ´gynevezett v´ arakoz´ o élek Wd halmazát, minden d ∈ D depó esetén. Ezek az élek mindig az állom´ as id˝ovonalát követik, éllel ¨ osszekötve az egymást követ˝o (indulási) id˝opontokat, összegy˝ ujtve azok folyam´ at. Ebben az esetben az Ad élhalmaz defin´ıciója a következ˝ o lesz: Ad = Ed ∪ Bd ∪ Rd ∪ Kd ∪ Wd ,

∀d ∈ D,

és a gr´ af ¨ osszes éleinek halmaza E = ∪d∈D Ad . A 6. ábra mutat egy egyszer˝ u péld´ at egy id˝o-tér h´ alózatra. Alkalmazott Matematikai Lapok (2014)

16


Ebben az esetben az IP-modell a kapcsolatlap´ u modelléhez hasonló lesz. Az egyetlen k¨ ulönbség, hogy több él folyam´ at egyetlen élbe gy˝ ujthetj¨ uk össze, ´ıgy az xde ∈ {0, 1} feltétel helyett az xde ≥ 0, xde egész” feltételt kell szerepeltetn¨ unk. ” 2.3.3. A halmazpart´ıcion´ al´ asi modell Ebben az alfejezetben Ribeiro és Soumis [63] cikke alapján megadjuk a probléma egy halmazpart´ıcion´ alási megfogalmaz´ as´ at. Az MDVSP a 2.3.1. alfejezetben megfogalmazott G gr´ afon megadott körfolyamok seg´ıtéségével u ´jrafogalmazható. 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 ∪ Hd H= d∈D

az ¨ osszes 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:  1, ha a p ∈ H u asban, d ´ t szerepel a megold´ ypd = 0, k¨ ulönben.

Defini´ aljuk tov´ abbá ade,p -t az alábbi módon:  1, ha a p ∈ H u elt, d ´ t tartalmazza az e ´ ade,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. Minimalizáljuk a ∑ ∑ cp ypd d∈D p∈Hd

célf¨ uggvényt a ∑

∑

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átos, 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: ∑ ypd ≤ kd , ∀d ∈ D. p∈Hd



17

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ával (az eml´ıtett cikkben k¨ ulön SDVSP-problémákat oldanak meg az eredeti MDVSP minden depój´ ara) olyan járatsorozatokat találjon, melyek minden egyszer˝ us´ıtett problém´ aban egymás ut´ an következnek. Ezeket a sorozatokat leköti, és a felép´ıtend˝ o id˝ o-tér modellben egy¨ utt kezeli ˝oket. Suhl és szerz˝otársai [69] egy kerek´ıtéses heurisztikát alkalmaztak. Módszer¨ uk alap¨ otlete, hogy az MDVSP-feladat LP-relaxációj´ anak értéke és az optimális egész megold´ as értéke közötti k¨ ulönbség meglehet˝osen kicsi, néha nulla, és az LPrelax´ aci´ o optim´ alis megoldásában sok v´ altozó 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´ ot (ez lehet a bejárt cs´ ucsok sz´ am´ anak korl´ atja, vagy az aktu´ alis feladat értéke és az LP-relaxáció értéke k¨ oz¨ otti k¨ ulönbség), majd az ´ıgy kézben lév˝o” részmegoldáson végrehajt egy ” kerek´ıtési algoritmust. Az algoritmus által meghatározott két kerek´ıtési tartomány [0, rl ] és [ru , 1], ahol 0 ≤ rl ≤ ru ≤ 1. Legyen xj egy v´ altozó, és xj − ⌊xj ⌋ = fj , ahol 0 ≤ xj ≤ 1. A heurisztika az xj értékét az alábbi szabályok szerint kerek´ıti:  ⌊x ⌋, j xj := ⌈xj ⌉,

ha fj ∈ [0, rl ], ha fj ∈ [ru , 1].

Egym´ as ut´ an több kerek´ıtési iterációt is végrehajthatunk, feltéve, hogy az ´ıgy létrej¨ ott LP még mindig lehetséges megold´ ast ad. Ha nem tudtunk egy v´ altozót sem kerek´ıteni, akkor a kezdeti kerek´ıtési intervallumok növelhet˝ok. Az ´ıgy kapott feladatra u ´jra lefuttatjuk a korl´ atozás-szétválasztás módszerére alapuló IPmegold´ ot. A folyamatot addig ismételj¨ uk, am´ıg minden v´ altoz´ ot fixáltunk, vagy a feladatnak nincs lehetséges megoldása. Pepin és szerz˝otársainak dolgozata több heurisztikus módszert hasonl´ıt össze [61]. A publik´ acióban öt k¨ ulönböz˝ o heurisztikus megközel´ıtést vizsgálnak: – egy szétv´ alasztás és v´ ag´ as (branch-and-cut) t´ıpus´ u megoldást, – Lagrange-relaxációra alapuló heurisztik´ at, – oszlopgenerálást, – egy nagy szomszédsági keresést, – valamint egy tabu-keresést. A szétv´ alasztás és vág´ as t´ıpus´ u megoldás alkalmaz´ asán´ al a feladat id˝o-tér modelljét ép´ıtik fel, majd oldják meg CPLEX-szel, m´ıg az oszlopgenerálásn´ al lényegében szintén CPLEX-szel kapnak eredményt. Alkalmazott Matematikai Lapok (2014)

18


A probléma folyammegmaradási feltételének Lagrange-relaxálásával a kapott feladat SDVSP-részproblémákkal lesz ekvivalens, amit egy aukciós algoritmussal oldanak meg. Az ´ıgy kapott als´ o korlátot szubgradiens módszerrel jav´ıtják. A nagy szomszéds´ agi keresés egy kezdeti megold´ asb´ ol kiindulva minden iterációban r k¨ ul¨ onb¨ oz˝ o járm˝ um˝ uszakot választ ki, több v´ alasztási stratégia valamelyikével. Az ´ıgy kiválasztott m˝ uszakokat u ´jraoptimalizálják, az oszlopgenerálást haszn´ alva. A választási stratégiák valósz´ın˝ usége minden iterációban v´ altozik att´ ol f¨ ugg˝oen, hogy az el˝oz˝ oek mennyire voltak hatékonyak. A tabukeresés szintén egy kezdeti megold´ asb´ ol indul, és minden iterációban az aktu´ alis megoldás egy szomszédjára tér át. Kétféle módon definiálják a szomszéds´ agot: 1-mozgatás, é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ásik, vj eszk¨ oz hajtja végre. A csere-mozgatás olyan szomszédokat ad, melyeknél, ha a tk járatot a vi eszköz, valamint a tk′ járatot a vj eszköz hajtotta végre az eredeti u ´gy a szomszédban a tk járatot a vj , valamint a tk′ járatot a vi ¨temezésben, u eszk¨ oz hajtja végre (valamely k, k ′ , i és j értékekre).

3. A j´ arm˝ uvezet˝ o-¨ utemez´ esi feladat A munkaer˝ o költsége egy nagyon fontos, kiemelt összetev˝ oje az egész operat´ıv u oltségének, ´ıgy a dolgozók munkájának beosztása, u ¨temezés k¨ ¨temezése manaps´ ag k¨ ozponti kérdés. Tipikus személyzetbeosztási alkalmazások jelennek meg a k´ orh´ azak u atorok), légitár¨zemeltetésénél (pl. n˝ovérek), a call-centerekben (oper´ sas´ agokn´ al (stewardessek, pilóták), és a közlekedési vállalatoknál (járm˝ uvezet˝ok munk´ aj´ anak u osen szakma¨temezésére). A beosztások elkész´ıtésekor a feltételek er˝ specifikusak, ´ıgy a problémák megfogalmazása, a modellek és megoldási módszerek is meglehet˝osen v´ altozatosak [28]. A járm˝ uvezet˝o-¨ utemezés során (amelyet r¨ oviden vezet˝ou ¨temezésnek is fogunk nevezni) adott az ellátandó, operat´ıv feladatok halmaza. Ezt kell olyan módon 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árm˝ uvezet˝ ok sz´ amára el˝o´ırt – szab´ alynak megfeleljenek. A hozzárendelést u ´gy kell megadni, hogy eközben minimalizáljuk az u uszakok ¨temezés során kialak´ıtott m˝ költségeinek ¨ osszegét. Sok olyan feltétel van, amelyet a vonatkozó jogszab´ alyok és az adott közlekedési v´ allalat dolgoz´ oira vonatkozó szab´ alyok, el˝o´ır´ asok határoznak meg. Ilyenek a napi munkaid˝ o-beosztásra vonatkozó szab´ alyok, a maximális munkaid˝ o és a napi pihen˝ oid˝ o minimális hossza, a kell˝o sz´ am´ 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áratokon és a rezsimeneteken k´ıv¨ ul sokféle technikai és adminisztrációs feladat is van, amelyeknek pontosan meghatározott id˝obeli hossza van. Ilyenek az utasok kiAlkalmazott Matematikai Lapok (2014)


19

és beszáll´ asi ideje a járatok végállomásain: a tankolás, a parkolás, a m˝ uszakkezdet és -befejezés stb. Megjegyezz¨ uk, hogy a vezetési id˝o és a munkaid˝ o k¨ ulönböz˝ o fogalmak, ´ıgy ezekre eltér˝o szabályok vonatkozhatnak, miként arra is, hogy melyik technikai tevékenység ideje melyikbe sz´ am´ıt bele. Ehhez járulhat még hozzá az, hogy k¨ ul¨ onb¨ oz˝ o v´ allalatokn´ al további korl´ atoz´ o feltételek és szab´ alyok is el˝ofordulhatnak (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árulékoknak) megfelel˝oen az egyes feladatokhoz költségeket tudunk rendelni. Így az egyes m˝ uszakok költségeit u ´gy sz´ am´ıtjuk ki, hogy összeadjuk a k¨ ul¨ onb¨ oz˝ o tevékenységek költségeit. A legnépszer˝ ubb megközel´ıtés a probléma megoldására a halmazpart´ıcionálás (lásd pl. [30]), valamint az annak relaxáci´ oját jelent˝o halmazlefedési modell (pl. [66, 73]) vizsgálata. A megold´ as el˝oáll´ıtása 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örtén˝ o jav´ıt´ as´ aval, vagy nagyszám´ u legenerált lehetséges megoldás köz¨ ul a legjobbak kiv´ alaszt´ asával [50]. K¨ ulönböz˝ o jelleg˝ u algoritmusokat alkalmaztak a probléma megold´ as´ ara. Ezek köz¨ ul érdemes kiemelni az egészérték˝ u programozási modelleket (l´ asd pl. [72]), az evol´ uci´ os elvekre ép¨ ul˝o metaheurisztikus eljárást [50], vagy a Fuzzy-módszeren alapuló [52] algoritmusokat. A helyes modell kialak´ıtását nagymértékben nehez´ıti az, hogy a k¨ ulönböz˝ o közlekedési társas´ agok más-más elveket, bels˝ o szab´ alyokat alkalmaznak a vezet˝ou ¨temezésnél. Ilyen lehet péld´ aul annak el˝o´ırása, hogy mely pontokon (mely földrajzi 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´ o 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´ aul a maximális munkaid˝o, a néh´ any r¨ ovid é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´ ama 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övidebb munkaszakaszok után, de ezekre is vonatkozhatnak bonyolultabb szabályok); több k¨ ul¨ onb¨ oz˝ o vari´ ació 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ástól. A munkaid˝ obe belesz´ amolódhatnak más, el˝o´ırt technikai id˝ok is, péld´ aul a végállom´ 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áltuk felv´ azolni azt is, hogy milyen elvár´ asokat támasztanak egy matematikai modell elkész´ıtése és alkalmazása során az egyes felhaszn´ alók. A vezet˝ ou ¨temezés központi logisztikai probléma a tömegközlekedésben, hiszen a járm˝ uvezet˝ okkel kapcsolatos költségek a teljes, közlekedéssel kapcsolatos költséAlkalmazott Matematikai Lapok (2014)

20


gek nagy részét alkotják. A vezet˝ou ¨temezés alapproblémája a következ˝o módon hat´ arozhat´ o meg: Adottak a járm˝ uvek közlekedései/tevékenységei, fix indulási és érkezési idej¨ ukkel és hely¨ ukkel. A feladat az, hogy mindegyikhez járm˝ 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´ asokat. Ennek klasszikus matematikai megfogalmazása egy halmazlefedési problém´ at 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ási módszer és alkalmazás található. A következ˝okben ezeket tekintj¨ uk át r¨ oviden. Részletesebb áttekintéshez például a [28] tanulmány ajánlhat´ o az ez ir´ ant érdekl˝od˝ oknek. 3.1. Modellek ´ es algoritmusok a CSP-re Az alfejezetet az alapvet˝o jelölé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árm˝ u egy v´ altási helyhez ér, lehetséges v´ alt´ asi pontr´ ol (relief oppurtunity ) beszél¨ unk. A járm˝ u két egymást követ˝o lehetséges v´ altási pont közötti feladatait munkaszakasznak (work piece ) nevezz¨ uk. A vezet˝ou ¨temezési feladat megoldására két által´ anos megközel´ıtés létezik. 3.1.1. A gener´ al´ as ´ es kiv´ alaszt´ as m´ odszere A módszerre az angol elnevezés (Generate and Select ) rövid´ıtése alapján GaSsel fogunk hivatkozni. GaS-technikát haszn´ altak az [50, 52, 72] cikkekben. A módszer 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´ alasztási lépésben keress¨ unk egy olyan részhalmazt a generált m˝ uszakokból, amely minimális költség˝ u és lefedi a feladatokat. Az els˝ o fázis jelent˝os sz´ am´ıtási id˝ot igényel. A sz´ am´ıt´ asi igény nagyban f¨ ugg a járatok mennyiségét˝ol, a szabályok sz´ amától és bonyolults´ ag´ ató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éma – komplexitását. A GaS kiv´ alasztási fázisa hagyom´ anyosan egy halmazlefedési vagy halmazpart´ıcion´ al´ asi feladatként fogalmazható meg. Jelölje n′ a lehetséges m˝ uszakok és m′ 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, . . . , m′ , j = 1, 2, . . . , n′ ), ahol

xj =

 1, 0,

ha a j. m˝ uszakot kiválasztjuk, k¨ ulönben.



ai,j =

 1, 0,

21

ha az i. feladatot tartalmazza a j. m˝ uszak, k¨ ulönben.

Ekkor a feladat a következ˝o módon ´ırható fel:   n′ n′ ∑ ∑ min w1 c j xj + w 2 xj  j=1

(1)

j=1

figyelembe véve az alábbi korlátozó feltételeket: ′

n ∑

ai,j xj ≥ 1,

i = 1, 2, . . . , m′ ,

(2)

j=1

ahol cj a j. m˝ uszak költsége, w1 és w2 k¨ ulönböz˝ o s´ ulyok. Az (1) célf¨ uggvény a (2) feltételrendszerrel egy halmazlefedési feladatot generál, 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álásáról is [25, 66]. A part´ıcion´ alási 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ák, hogy NP-nehéz [37]. A probléma megold´ asára sz´ amos eljárás létezik. Például egészérték˝ u programozási módszereket haszn´ alnak [72]-ben, heurisztikus megoldási technikákat alkalmaznak [50]-ben. 3.1.2. A konstrukt´ıv megk¨ ozel´ıt´ es m´ odszere A konstrukt´ıv megközel´ıtés egyetlen megold´ ast ép´ıt fel irány´ıtottan egy optimaliz´ alási 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ódszerrel 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´ as lehetséges megold´ as-e. Ez azt jelenti, hogy – mindkét megközel´ıtés generáló folyamata során – a megold´ ashoz tartoz´ o összes m˝ uszakról el kell dönten¨ unk, hogy azok Alkalmazott Matematikai Lapok (2014)

22


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´ ama nagyon nagy, ezért a technikák többségénél k¨ ulönböz˝ 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´ asi pontokat hagynak el, vagy azzal, hogy csak sz´ am´ıtásilag kezelhet˝o sz´ am´ u m˝ uszakot generálnak le. Ezek az egyszer˝ us´ıtések természetesen befoly´ asolhatják és korl´ atozhatják a módszernél az optimalizálás sikerét. 3.2. A CSP korl´ atoz´ o felt´ eteleir˝ ol A CSP megoldása során a korlátoz´ o feltételek valóban dönt˝o szerepet játszanak a megold´ asi módszer szempontjából. Ezek er˝osen befoly´ asolják a megold´ as milyenségét és a sz´ am´ıtási id˝ot. Er˝os korl´ atozó feltételekkel rendelkez˝o valós problémák esetén nehéz kérdés, hogy megtalálják az egyens´ ulyt a fenti szempontok között. Mivel által´ aban a probléma mérete nagy, és az el˝o´ırt szab´ alyok rögz´ıtettek, a f˝o cél az, hogy találjunk egy hatékony módszert, amely gyakorlati szempontb´ ol jó min˝ oség˝ u, kivitelezhet˝o megold´ ast ny´ ujt. A f˝o korl´ atokat nemzetközi (pl. EU-s szab´ alyok) és nemzeti (minisztériumi, önkormányzati stb.) szinten határozzák meg. A helyi közlekedési v´ allalat is további 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ósá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átoz´ o feltételeknek). Abban az esetben, ha döntéstámogató az u ¨temezés, egyes mérnöki követelmények min˝ oségére vonatkozóan a megold´ ast nem kell, vagy nem is lehet formaliz´ alni. Ekkor a hossz´ utáv´ u tervezés u ¨temezése interakt´ıv mechanizmusként val´ osul meg, azaz interakt´ıv, mérnöki beavatkoz´ as lehetséges vagy sz¨ ukséges is. Egy módszer alkalmazásának lehet˝osége nagymértékben f¨ ugg attól, hogy miként lehet a modellben a sz¨ ukséges szabályokat megfogalmazni, formalizálni, milyen paramétereket képes kezelni, és ezáltal a k¨ ulönböz˝ o megold´ asokat el˝oáll´ıtani. Ez a rugalmass´ ag központi kérdés az optimalizálási folyamat többi szakaszához val´ o viszony tekintetében is: a megold´ as értékelése önmag´ aban nem, csak a járm˝ uu utt lehetséges. ¨temezés, valamint a vezet˝obeosztás eredményének értékelésével egy¨ 3.3. A c´ elfu enyr˝ ol ¨ ggv´ A CSP megoldásának 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 egy járm˝ uvezet˝o foglalkoztatás´ anak van egy általános költsége, ezért minimalizálva az összköltséget, a vezet˝ou uszakok sz´ am´ at is. Másrészt, költsé¨temezés alacsony szinten fogja tartani a m˝ geket rendelhet¨ unk a m˝ uszakokhoz a benn¨ uk szerepl˝ o feladatok szerint is. Ezen k´ıv¨ ul meg lehet határozni egyéb jellemz˝oket, mint például a m˝ uszak t´ıpusa, a v´ arAlkalmazott Matematikai Lapok (2014)


23

hat´ 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öltségét is ehhez kell igaz´ıtani.)

4. Integr´ alt strat´ egi´ ak Ebben a fejezetben a járm˝ 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ópontként a [68] cikket ajánljuk, a részletesebb elmély¨ uléshez javasoljuk a kit˝ un˝ o áttekintést ad´ o [24] tanulmányt. A járm˝ uvezet˝o-¨ utemezés a hagyom´ anyos megközel´ıtést követve a járm˝ uu ¨temezés fázisa ut´ an hajtódik végre. (Ezért ezt szekvenci´ alis megk¨ ozel´ıtésnek is nevezz¨ uk.) Ez általában hatékonyan végrehajtható, ha a v´ altá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árm˝ uu u ideig nem érint megengedett v´ altási helyet, akkor rontha¨temezés hossz´ tunk az el˝oz˝ o fázis eredményén, vesz´ıthet¨ unk a hatékonyságból. A járm˝ uu ¨temezés és a járm˝ 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övetkez˝oképpen fogalmazható meg. Adott menetrendi járatok egy halmaza, adott a járm˝ uflotta, melynek járm˝ uvei k¨ ulönböz˝ o depókhoz tartoznak, adottak tovább´ a a járm˝ uvezet˝okre vonatkoz´ o szabályok. A feladat a járm˝ uveknek és a járm˝ uvezet˝oknek olyan érvényes u ¨temezését adni, hogy az valamennyi – járm˝ ure és járm˝ uvezet˝ore – vonatkoz´ o szab´ alynak megfeleljen, és minimális k¨ oltség˝ u legyen. Ez a feladat egy, az MDVSP-hez hasonl´ o egészérték˝ u programozási feladatként ´ırhat´ o fel, kib˝ov´ıtve olyan feltételekkel, amelyek egyrészt a vezet˝ou ¨temezésnek felelnek meg, másrészt pedig kapcsolatot teremtenek a két u ¨temezés között. Ekkor a célf¨ uggvényben is a két u asd pl. ¨temezés költségének összege jelenik meg (l´ [24]). Mint kor´ abban láttuk, az MDVSP- és a VCSP-feladat kapcs´ an 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ában a lehetséges m˝ uszakok sz´ ama igen nagy, k¨ ulönösen a több´ dep´ 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˝ uu uvezet˝o-¨ utemezési ¨temezési vagy járm˝ Alkalmazott Matematikai Lapok (2014)

24


problém´ at. A szám´ıtógépek sz´ am´ı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árgy´ u publik´ aciók. A kis és k¨ ozepes méret˝ u problémák mára megoldhatóvá v´ altak. Már az 1980-as évek elején Bodin és szerz˝otársai komolyan kritizálták a szek´ venci´ alis megk¨ ozel´ıtést [13]. Eszak-amerikai tömegközlekedési péld´ akon kereszt¨ ul bizony´ıtott´ ak azon érvelés¨ uket, hogy a járm˝ uvezet˝ok (bér)költsége sokszor magasabb, mint a járm˝ uvekkel kapcsolatos költségek. Extrém esetekben a bérköltség akár 80%-át is adhatja a kétféle költség összegének. Ebb˝ol az következik, 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ódon. 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ók, amelyekben a VCSP heurisztikus megold´ asa során figyelembe vettek bizonyos, járm˝ uvekre vonatkozó feltételeket is. Az 1997 el˝ott haszn´ alt módszerekr˝ol egy jó áttekintés tal´ alható Gaffi és Nonato 1999-es közleményében [35], vagy Freling 1997es PhD-dolgozatában [32]. Az els˝ o, valóban integrált 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´ altási pontok távol esnek egym´ ast´ ol, péld´ aul helyközi vagy távols´ agi tömegközlekedés esetén. A módszer szintén jól m˝ uködhet azokban az esetekben, amikor egy vezet˝o egy járm˝ uvet haszn´ alhat csak a m˝ uszakja során. A legnépszer˝ ubb megközel´ıtés az integr´ alt VCSP-problémára kétségk´ıv¨ ul az egészérték˝ u programozási modell alkalmaz´ asa. Freling és szerz˝otársai [31] modellje az egydepós esetre három részb˝ ol állt: az SDVSP-t kvázihozzárendelési, a VCSP-t halmazpart´ıcion´ alási feladatként fogalmazták meg. A kett˝ot korlátoz´ o feltételekkel k¨ ot¨ otték össze, biztos´ıtva a kompatibilitást. A feladat megoldására Lagrange-relax´ aciót és oszlopgenerálási módszert kombináló, közel´ıt˝o megoldást adtak. Ez azt´ an további publikációkat inspir´ alt, l´ asd [33, 34, 46]. Freling és szerz˝otársai a [33, 34] cikkeikben szintén az egydepós integr´ alt feladatot tekintették, a buszok sz´ am´ ara vonatkoz´ o fels˝o korlát nélk¨ ul. Ugyancsak oszlopgener´ alást – és ezen bel¨ ul Lagrange-relaxációt – haszn´ altak az ott adódó u ń. mesterprobléma megoldására, a feltételek relaxáci´ ojával. A [34] cikkben valós, kb. 150–250 járatb´ ol álló feladatok megold´ asár´ ol sz´ amoltak be, kezelhet˝o megoldási id˝ oben. Megmutatták, hogy csak kis jav´ıtás érhet˝o el a feladatok szekvenciális, egym´ as ut´ an t¨ ortén˝o megold´ asához képest. Ez a jav´ıtás szignifikánsabb, ha a járm˝ uvezet˝ ok nem válthatnak járm˝ uvet (egy sz¨ unetet követ˝oen). Az els˝ o pontos megoldást ad´ o algoritmust 1999-ben publik´ alta Haase és Friberg [41] az egydep´ os esetre. Modellj¨ ukben mindkét halmazpart´ıcion´ alási megközel´ıtés integr´ alt matematikai megfogalmazását adták: mindkét részfeladatot halmazpart´ıcion´ alási feladatként fogalmazták meg. Eljár´ asukban a járm˝ uvek u ¨temezése Ribeiro és Soumis 1994-es [63], m´ıg a járm˝ uvezet˝ok u ¨temezése DesroAlkalmazott Matematikai Lapok (2014)


25

chers és Soumis 1989-es [26] modelljein alapult. A szétválasztás, vág´ as és árazás (branch-and-cut-and-price) t´ıpus´ u algoritmusukban oszlopgenerálást és v´ ag´ asgenerál´ ast alkalmaztak. Az oszlopgenerálási mesterprobléma az LP-relaxációnak felelt meg, m´ıg az árazásra (pricing) a legrövidebb u ´t problémák megold´ asa szolgált. Algoritmusukkal csak kisméret˝ u példákat tudtak megoldani, legfeljebb 20 járatb´ ol áll´ okat. Egy másik érdekes egzakt algoritmust adtak meg az egydep´ os 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ózati folyam problémaként megfogalmazva oldották meg u ´gy, hogy beleágyazt´ ak az egydepós, járm˝ uvekre vonatkoz´ o feltételeket. Ezt olyan módon tették, hogy mindkét fázist figyelembe véve, a VCSP-feladatra garantált, pontos optimumot adott az algoritmusuk. Itt a szétválasztás és áraz´ as (branch-and-price) t´ıpus´ u algoritmusra sz´ amos gyors´ıtási technik´ at alkalmaztak. Két algoritmusváltozatot is tárgyaltak a szétválasztáskor adódó ágak kezelésére: egy egzakt és egy heurisztikus v´ altozatot. Véletlen feladatokon végeztek sz´ am´ıtógépes szimul´ aciós ´ teszteket. Atlagosan kb. 1,5 ór´ as (b´ ar 10-b˝ol 6 esetben 3 órás) futási id˝ovel tudtak 150 járatméret˝ u péld´ akig pontos megold´ ast szolgáltatni. Ennél nagyobb, 350 járatméret˝ u példákig heurisztikus megoldást alkalmaztak, 2 órán bel¨ uli CPU-id˝ot haszn´ alva. Itt a feladat olyan egyszer˝ us´ıtett megfogalmaz´ asát tekintették, ahol a költségben csak a sz¨ ukséges buszok sz´ ama szerepelt, és ˝ok sem vettek figyelembe korl´ atot ezek számára. Így megfogalmaz´ asuk gyakorlatilag szintén egydep´ os feladatként fogható fel. Fontos kiemelni ugyanakkor, hogy a feladatok nem valós, hanem a t¨ omegközlekedési feladatokat szimul´ aló véletlen adatokból 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ódszert használva. Lagrange-relaxációt és az oszlopgenerál´ as módszerét haszn´ alták, csak a többdepós esetre módos´ıtva a megfogalmazást. ˝ is az egyidej˝ Ok u vezet˝o- és járm˝ uu ¨temezés el˝onyei mellett érveltek olasz tömegközlekedési péld´ akon kereszt¨ ul, amelyek nem v´ arosi (nem helyi) közlekedési példák voltak. De u ´jra felh´ıvja a figyelm¨ unket a sz´ am´ıtási id˝o fontoss´ ag´ ara, kritikus voltára, hogy egy 257 járatb´ ol álló, olasz tömegközlekedési példa esete 24 óránál hosszabb sz´ am´ıtási id˝ot adott, átlagosan 2-6 óra volt a futási id˝o, b´ ar a maiaknál lényegesen lassabb, 180 MHz-es PC gépen. Huisman és szerz˝otársai 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ós probléma els˝ o általános matematikai megfogalmazása. Két megközel´ıtést is javasoltak: az egyik a [32, 34], a másik a [42] tanulmányokban ismertetett módszer által´ anos´ıtása a többdepós esetre. Mindkett˝o esetén az els˝o fázisban egy als´ o korl´ atot sz´ am´ıtanak ki az optimumra. Az els˝ o fázis LP-relaxácón alapszik, oszlopgener´ alást és Lagrange-relaxációt haszn´ al. A második fázis ad egy lehetséges egészérték˝ u megold´ ast a feladatra. A [34]-ben használt Lagrange-relaxációt alkalmazva el˝oször egy járm˝ uu ol aztán a [33, 34] cikkek¨temezést generál, amelyb˝ ¨ ben tárgyalt módszereket használva járm˝ uvezet˝o-¨ utemezést kész´ıt. Osszehasonl´ ıtó Alkalmazott Matematikai Lapok (2014)

26


teszteket kb. 650 járatig kész´ıtettek, amelyek eredményei fel¨ ulm´ ulják a szokásos szekvenci´ alis u aló módszereket. Teszteket végeztek valós és szimulá¨temezést haszn´ ciós tesztadatokon egyaránt. A két megközel´ıtés között nem mutatkozott szignifik´ ans eltérés, de az els˝ o valamennyivel jobbnak bizonyult. Val´ os, nagyméret˝ u, többdep´ os, heterogén járm˝ uflotta esetén az eddig megeml´ıtett módszerek integrálása 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 2000es évek elejéig. A [22] cikkben rövidebb 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 – önmagukban, integrált módon – k¨ ulön oldva meg. A többdep´ os feladatra Borndörfer és szerz˝otársai [15] is Lagrange-relaxáción alapuló megk¨ ozel´ıtést haszn´ altak. A járm˝ uu uvezet˝o-¨ utemezési problém´ aknál ¨temezési és a járm˝ haszn´ alt k¨ ozel´ıt˝o megoldásokat alkalmazták, ezek informáci´ oit felhaszn´ alva egy branch-and-bound t´ıpus´ u algoritmusban. Egészérték˝ u programozási technikát haszn´ altak, k¨ ul¨ onböz˝ o korlátozó feltételekkel összekapcsolva a járm˝ uveket és járm˝ uvezet˝ oket a rezsi és a kiállási, valamint beáll´ asi járatoknál. Heurisztikus módon, Lagrange-relax´ aciót használva, majd az egészérték˝ u megoldásokat egy korlátozás és szétv´ alaszt´ as t´ıpus´ u technikával nyerve nagyméret˝ u, 1500-as járatsz´ am´ 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ár az általuk tárgyalt feladat általánosabb, mint az egydepós eset, de feltételezik, hogy az összes járm˝ u ugyanabban a depóban parkol. Ugyanakkor a járm˝ uvek t´ıpusaik szerint nem kell, hogy homogén flottát alkossanak. Egy mohó, 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árm˝ uvezet˝okre vonatkoz´ o 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´ o korlátot, ” a napi teljes munkaid˝ ore vonatkozó korlátot, és azt a paramétert veszik figyelembe, hogy a járm˝ uvezet˝oknek megengedett-e vagy nem a napon bel¨ uli járm˝ uváltás. 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árm˝ uvezet˝o-¨ utemezési rész vagy halmazparticionálási vagy kombinált halmazparticion´ alási és lefedési megfogalmazás. A relaxált LP-t oszlopgenerálással oldott´ ak meg, amelynek részproblémája korlátoz´ o feltételekkel ellátott legrövidebb u ´t feladat. Amennyiben a relaxált LP megold´ asa nem egésznek ad´ odott, egészérték˝ u megold´ ast kerestek korlátoz´ as és szétválasztás alap´ u hagyományos IPmegold´ oval. A [38]-ban alkalmazott eljárás egy ehhez hasonló megközel´ıtést haszn´ alt, a szerz˝ok korábbi id˝o-tér hálózati modelljét alkalmazva a járm˝ uu ¨temezési komponensben. A részben integrált modellek közé tartoz´ o modellt tárgyal Gintner, Kliewer és Suhl 2008-as cikke [39]. Ez annyiban hasonl´ıt a tradicionális szekvenci´ alis megAlkalmazott Matematikai Lapok (2014)


27

k¨ 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ázisa az id˝o-tér h´ alózati MDVSP-modellt haszn´ alja, de annyiban k¨ ulönbözik az eredeti megk¨ ozel´ıtést˝ol, hogy nem egyetlen optimális megoldást ad, hanem többet, minimális járm˝ uszámmal és minimális költséggel. Ezek után a VCSP-t halmazpart´ıcion´ al´ asi feladatként oldja meg, és Lagrange-relaxáci´ ot alkalmaz. A klasszikus megk¨ ozel´ıtéssel összehasonl´ıtva a módszer jobb járm˝ uvezet˝o-¨ utemezéseket eredményez. Steinzen és szerz˝otársai 2010-ben [68] egy teljesen integr´ alt VCSP-megközel´ıtést adnak. A mögöttes, 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´ o feltételekkel ellátott – egy id˝o-tér h´ al´ ozaton alapuló – legrövidebb u ´t feladat megold´ asával modellezték. Egy heurisztikus, szétválasztás és árazás t´ıpus´ u módszerrel generáltak lehetséges megold´ asokat. A numerikus tesztjeik azt mutatják, hogy ez a módszer fel¨ ulm´ ulja a kor´ abbiakat az ismertetett tesztfeladatokon, amelyeket 640 járatot tartalmaz´ o példaméretekig tekintettek. Az o¨sszehasonl´ıt´ as alapjait a [15, 38, 45, 46] cikkek alkott´ ak, amelyek köz¨ ul valamennyit fel¨ ulm´ ulta tesztpéld´ aikon az algoritmusuk. Az alkalmazott tesztpéldáik (kizár´ olag) a Steinzen weblapján található péld´ ak [67] voltak.

5. A m˝ uszakkioszt´ asi feladat A járm˝ 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ókat – sz´ amos általános é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 által´ aban megfelelnek más, tipikus alkalmazások feltételeinek, amelyek egyes személyzetbeosztási [17, 18] és n˝ ovérbeosztási [19, 11] feladatoknál, illetve a callcenterek u atori m˝ uszakkiosztásn´ al [65] is megtalálhatók. ¨zemeltetése esetén az oper´ A járm˝ 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ábbá a rendelkezésre álló járm˝ uvezet˝ok. A m˝ uszakkiosztás által´ aban hosszabb peri´ odusra történik, amelyet tervezési id˝ oszaknak nevez¨ unk. A tervezési id˝oszak tipikusan néh´ any hétb˝ ol álló id˝ointervallum, de ez lehet néhány nap, hónap, vagy akár egy egész év is. A m˝ uszakkiosztási feladat lényege, hogy egy tervezési id˝oszakra az adott m˝ uszakokat rendelj¨ uk valós alkalmazottakhoz u ´gy, hogy az el˝o´ırt szabályokat betartjuk. Ez a feladat több alkalmazási ter¨ uleten fordul el˝o. A leggyakoribb alkalmazások a légiközlekedésben Alkalmazott Matematikai Lapok (2014)

28


(pil´ ota és személyzet), vas´ uti közlekedésben, call-centerekben dolgozók, n˝ovérek és buszsof˝ or¨ ok munk´ ajának tervezése. A módszernek a tervezési id˝oszak minden m˝ uszakjához járm˝ uvezet˝ot (konkrét személyt) kell rendelnie. Van néh´ any általános szab´ aly, rendelkezés, amely korlátoz´ o feltételként veend˝ o figyelembe. Ilyenek például a maximális heti munkaórák sz´ ama, vagy a szabadnapok el˝o´ırt minimális sz´ ama egy adott id˝oszakban, ezen bel¨ ul a vas´ arnapok sz´ ama, stb. A szab´ alyok teljesen k¨ ulönbözhetnek az alkalmazási ter¨ ulett˝ ol f¨ ugg˝oen (légi, vas´ uti közlekedés, v´ arosi tömegközlekedés stb.). Gyakran tov´ abbi speciális 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´ annyal kell rendelkeznie a vezet˝onek bizonyos t´ıpus´ u buszok vezetéséhez. A hozzárendelés költsége a közlekedési cégek esetén nagyban f¨ ugghet a v´ allalatvezetés filoz´ ofiáj´ atól”. Ez lehet egyetlen cél is, de több összetev˝ o is alkot” hatja. Ut´ obbi esetben ezekb˝ ol több is (pl. s´ ulyozott módon) megjelenhet a célf¨ uggvényben. Ilyen lehet a járm˝ uvezet˝ok sz´ am´ anak minimalizál´ asa, a szerz˝odésben szerepl˝ o megállap´ıtott munkaóráktól való eltérések összegének minimalizálása (akár t´ ul´ or´ ar´ ol, akár az abban szerepl˝ onél kevesebb tényleges munkaid˝or˝ol van sz´ o, azaz a t´ ulfoglalkoztatást és az alulfoglalkoztatást egyar´ ant ker¨ ulni kell, a lehetséges mértékben). A fenti okok miatt több célf¨ uggvény˝ u optimalizálási módszerek haszn´ alata is indokolt lehet [59, 60]. Miután az alapfeladat általánosan tekintve hozzárendelési probléma, a szakirodalomban megtalálható néh´ any – a hozzárendelési feladatra alapozott – általános megközel´ıtés is a m˝ uszakkiosztási feladatra. Ilyenek péld´ aul a t¨ obbtermékes folyam algoritmusok [17], a logikai programozás alkalmazása korl´ atoz´ o feltételekkel [74], vagy az evol´ uciós módszert haszn´ aló algoritmusok [59]. A feladatot több 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 össze is lehet vonni ˝oket. A buszközlekedésben legink´ abb el˝ofordul´ o lépések a következ˝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´ am´ ató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ás. A szabadnapok kiosztása f˝oleg akkor sz¨ ukséges, amikor nem teljesen kötöttek 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ól, 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ásképp meghatározott feladatokból) bizonyos id˝ointervallumra (jellemz˝oen egy hétre vagy h´ onapra) adott hossz´ us´ ag´ u sorozatokat hoznak létre. Alkalmazott Matematikai Lapok (2014)


29

– M˝ uszaksorozat-ember hozzárendelés. Vég¨ ul itt az ön´ alló m˝ uszakokat, vagy m˝ uszaksorozatokat tényleges alkalmazottakhoz rendelik. A feladat egy részletesebb, általánosabb felbontása megtalálható [28]-ban. 5.1. Korl´ atoz´ o szab´ alyok A szigor´ u, kemény” szabályok f˝oleg az EU, minisztériumok, önkormányzatok, ” szakszervezetek stb. által el˝o´ırt szab´ alyok, ezek betartása kötelez˝o az u ¨temezés során. Az ajánlott, puha”szab´ alyok f˝oleg személyi igények során ker¨ ulnek el˝otérbe ” (néh´ any szabadnap egymás ut´ an 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´ as jóság´ at”, s´ ulyozva ” beker¨ ulhetnek a célf¨ uggvénybe a kiértékelésnél. Jellemz˝o szigor´ u szabályfajták, amelyek a legtöbb alkalmazási ter¨ uleten el˝ofordulnak: – Adott az egymást követ˝o két m˝ uszak közötti minimális pihen˝oid˝o. – Maximálva van a heti munkaid˝ o. – Adott a heti minimális pihen˝ oid˝o. – Szab´ alyozott, hogy legfeljebb hány egymást követ˝o napon dolgozhat a munkav´ allaló szabadnap nélk¨ ul. – Adott, hogy legal´ abb h´ any szabadnapja legyen egy munkavállalónak egy h´ onapon bel¨ ul. – Adott, hogy hány szabadnapnak kell esnie bizonyos t´ıpus´ u napra (pl. hétvégére, vasárnapra stb.) adott id˝on (egy hónapon) bel¨ ul. – Adott, hogy bizonyos munkav´ allalók csak bizonyos t´ıpus´ u m˝ uszakot kaphatnak, vagy milyen t´ıpusb´ ol 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´ onap). A buszos járm˝ uvezet˝okre vonatkozó szab´ alyok egyfajta osztályozása megtalálható [60]-ban. Alkalmazott Matematikai Lapok (2014)

30


5.2. Ki´ ert´ ekel´ es A m˝ uszakkiosztás min˝oségének meghatároz´ asa 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ároz´ asához több 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ásával kisebb a költsé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´ alyok 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´ alyok 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ás k¨ oltségét nagyban befolyásolja az alkalmazottak szerz˝odése, amely meghatározza a ledolgozand´ o órák sz´ am´ at. Ett˝ol való eltérés alul-, illetve t´ ulfoglalkoztatást jelent. Az el˝ obbi azért költséges, mert a szerz˝odésben foglalt ór´ ak alapján kapja a fizetését, holott nem dolgozott annyit, az ut´ obbi meg t´ ul´ orát jelent, amelynek bérezése által´ aban magasabb az alap órabérnél. Így ezek s´ ulyozott minimalizálása a k¨ oltség cs¨ okkenését jelenti [6]. Az nyilvánvaló, hogy az alul- és t´ ulfoglalkoztatás cs¨ okkentése csak u ´gy érhet˝o el, ha a kiosztás során felhaszn´ alt alkalmazottak sz´ ama és o altozik. ¨sszetev˝oje v´ 5.3. Megold´ asi m´ odszerek Ugyan a m˝ uszakkiosztási feladat az élet eltér˝o ter¨ uletein fordul el˝o, a f˝obb betartand´ o szabályok, illetve az optimalizál´ as 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ási módszerek is elég általánosak a többi alkalmazási környezetbe való illesztéshez. A módszerek közötti k¨ ulönbség egyrészt ink´ abb abból ad´ odik, 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ásrészt az alkalmazott optimalizálási algoritmusok változatoss´ aga jellemzi a szakirodalmat. Egyik megközel´ıtés, hogy a feladatot visszavezetik halmazlefedési vagy part´ıcion´ alási 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ányt követték péld´ aul Gamache és szerz˝otársai, akik 1999-es cikk¨ ukben [36] a halmazpart´ıcion´ alást oszlopgener´ alással oldották meg. A feladat fel´ırható 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öbbtermékességet az adta, hogy háromféle kiosztást kész´ıtettek a kapit´ anyoknak, pil´ otáknak és légi utask´ısér˝oknek [17]. Jellemz˝o még a kombin´ alt megold´ asi módszerek 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ödik elfogadhat´ o id˝on bel¨ ul, m´ıg a pusztán korl´ atoz´ o feltételes logikai programozásAlkalmazott Matematikai Lapok (2014)


31

ként való fel´ır´ as már 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 kombinál´ asával kész´ıtett hibrid módszer, ahol oszlopgenerálást alkalmaztak és az oszlopok generál´ as´ at végezték korl´ atozó 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ált módszert 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ási feladat megoldását [18]. Iterat´ıv kombin´ alt 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ódszert [11]. Nurmi és szerz˝otársai [60] a megoldást két fázisban végzik: el˝osz¨ or a szabadnapokat osztják ki, majd utána a m˝ uszakkiosztást. Mindkét feladathoz ugyanazt a módszert alkalmazzák, amely egy mohó, popul´ acióalap´ u helyi keresés. Egy kiosztás 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ódszere, ahol két szempont szerint történik az optimalizálás. Ez a kett˝o az emberek elv´ art sz´ amától való eltérés minimalizál´ asa és a t´ ulór´ ak egyenletes elosztása. A gener´ alt megoldások kiértékelésénél e két cél szerinti Pareto-dominanciát haszn´ alják fel. 5.4. Sz´ etv´ alaszt´ asi strat´ egi´ ak A fenti részfeladatokat közelebbr˝ol megvizsgálva láthatjuk, hogy k¨ ulönböz˝ o opciók lehetségesek az u urájának megtervezésére. Két ¨temezési rendszer strukt´ alapvet˝ o kérdés, amely fontos ennek a strukt´ ur´ anak a megtervezésével kapcsolatban: – Hol legyen a határvonal a vezet˝ou uszakkiosztás feladatai ¨temezés és a m˝ k¨ oz¨ ott, mely szabályokat melyik részfeladatnál vegy¨ unk figyelembe? Alapvet˝ oen a legf˝obb elv ezzel kapcsolatban az, hogy a dolgozókra vonatkoz´ o olyan szabályok, rendelkezések, amelyek az egy napon bel¨ uli m˝ uszak kialak´ıt´ asában 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ás már nem eredményezhet a szab´ alyoknak megfelel˝ o megoldást. A gyakorlatban ez a probléma inkább csak kisebb v´ arosok társas´ againál életszer˝ u, ott fordulhat el˝o realisztikus módon (jóval sz´ azezer f˝o alatti lakoss´ ag esetén), mivel a kisebb kombin´ aciós lehet˝oség okozhat hozzárendelési problémákat 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ázatát, hogy nem kapunk lehetséges megold´ ast. Alkalmazott Matematikai Lapok (2014)

32


– A sorrend a járm˝ uu uvezet˝ok u ¨temezés és a járm˝ ¨temezése között: mivel a járm˝ uvek napi m˝ uszakjai menetrendi el˝o´ırásokon alapulnak, ´ıgy természetes módszerként ad´ odik els˝ o fázisban az optimális járm˝ uu ¨temezést elkész´ı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 összes, az emberekre vonatkoz´ o szabály ki legyen elég´ıtve. Ez a módszer ugyan hatékony, ´ viszont robusztus sz´ am´ıtógépes optimalizálási h´ atteret igényel. Eppen ezért a gyakorlatban, ahol nem használnak optimalizálási eszközöket automatizált tervezésre, vagy annak támogatására, az alkalmazott mérnöki heurisztik´ ak” ” megcserélik a két lépést: els˝o lépésként (nem automatizált 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án megfelel˝o járm˝ uveket rendelnek a kialak´ıtott m˝ uszakokhoz. Ennek a megközel´ıtésnek az el˝onye az, hogy a feladat komplexitása jelent˝osen csökken, mivel a járm˝ uvezet˝o a m˝ uszakja alatt nem cserélhet járm˝ uvet. Komoly hátrány ugyanakkor, hogy ez magasabb költség˝ uu oen, az egy napon ¨temezéseket eredményezhet. Jellemz˝ haszn´ alt járm˝ uvek sz´ ama ilyenkor szignifik´ ansan nagyobb. A fentiek alapján egy optimalizálásorientált automatizált u ¨temezési rendszer esetén feltételezz¨ uk, hogy az járm˝ uu uleg ¨temezéssel indul, vagy ha nem, akkor ezzel egyidej˝ figyelnie kell a járm˝ 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ársszerz˝okkel közös) cikkeikben a közösségi buszközlekedés operat´ıv tervezési feladataira adott – általában k¨ ulönböz˝ o gyakorlati kih´ıvásokból fakad´ o – megold´ asaikat tárgyalják az alábbi cikkekben, közleményekben: [4, 5, 6, 7, 9, 10, 20, 21, 70, 71]. Az itt tárgyalt felosztás alapján megvalós´ıtott, implementált fázisokat az [5] és a [10] publik´ aciókban egy keretrendszerben mutattuk be. A gyakorlatban is egy olyan, nagy modulokból áll´ o keretrendszernek nevezhet˝o rendszert fejlesztett¨ unk, amelynek moduljai megengedik olyan eljárások beágyaz´ asá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ók opcion´ alis megold´ asként, és néhány esetben kitér¨ unk ezeknek a lehet˝oségeknek a tárgyalás´ ara és vizsgálatára is. A járm˝ uu aciókban az MDVSP-heurisz¨temezési feladatra a [20] és a [21] publik´ tik´ ak kapcs´ an tárgyalt, a [47] cikkben megadott v´ altoz´ ofix´ alási heurisztika néh´ any módos´ıt´ as´ at, tov´ abbfejlesztését tárgyaltuk, k¨ ulönböz˝ o hasonló t´ıpus´ u, tov´ abbi heurisztik´ akat tárgyalva és elemezve. Alkalmazott Matematikai Lapok (2014)


33

7. ´ abra. Egy tipikus példa: egy munkanapon bel¨ ul melyik id˝oszakban h´ any járm˝ u (és járm˝ 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, illetve befejezési id˝opontok) jellegzetesek munkanapokon.

A járm˝ uu u-hozzárendelési feladatokhoz kapcsolódóan tapasz¨temezési és járm˝ talatunk szerint a konkrét, gyakorlati u ¨temezésben a szakirodalomban tárgyalt és alkalmazott modellek h´ atrányaként lehet megeml´ıteni, hogy csak azokat a szabályokat veszik figyelembe, amelyek a menetrendi járatokkal, az azokhoz megk´ıvánt buszt´ıpusokkal és kapacitásokkal, valamint a menetrendi járatok közötti rezsijáratokkal kapcsolatosak. Nem lehet viszont olyan specifikus feltételeket beép´ıteni, amelyek val´ os alkalmaz´ asi környezetb˝ol sz´ armaznak. 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árgyaltuk [7]ben és [9]-ben. Az ezekben tárgyalt módszer el˝onye, hogy heterogén járm˝ uflotta tankol´ asi feladatait is kezeli. Erre sz¨ ukség lehet, amennyiben hossz´ u tankolási idej˝ u, egy tankolással a d´ızel u u járm˝ uvekhez képest kis távolságot meg¨zemenyag´ tenni képes járm˝ uvek (is) vannak a flottában. Egy járm˝ uvezet˝o-barát, azaz olyan módszert tárgyalunk [5]-ben a járm˝ u- és vezet˝ ou uvezet˝oknek nem kell a ¨temezési feladat iterat´ıv megoldására, ahol a járm˝ nap során járm˝ uvet cserélni. Így csak egyazon járm˝ uvet vezetik a nap során a m˝ uszakjuk alatt, kivéve osztott m˝ uszak esetén. Ez olyan napközbeni, több órás otthoni pihen˝ o utáni visszatérést tartalmaz´ o m˝ uszak, amely tulajdonképpen két, Alkalmazott Matematikai Lapok (2014)

34


f¨ uggetlen m˝ uszakrészb˝ ol áll. A 7. ábra mutatja, hogy az osztott szolgálat miért sz¨ ukséges által´ aban munkanapokon: a reggeli és a délutáni cs´ ucs járatainak ell´ at´ asához t¨ obb járm˝ u (és járm˝ uvezet˝o) sz¨ ukséges, mint egyébként napközben. A [71] publikáció a vezet˝ou ¨temezésre ad a gyakorlatban használható heurisztik´ akat, m´ıg [70] a vezet˝ou o tevékenységekre egy általános ¨temezéshez kapcsolód´ keretmunk´ at. A [6] publikáci´ oban a m˝ uszakkiosztási feladatra adott hossz´ u táv´ u, több hetes intervallumokra adott megoldásainkat ismertetj¨ uk. Ko an´ıt´ as. ¨szo ¨netnyilv´ A kutat´ ast a Szuperszám´ıtógép, a nemzeti virtuális laboratórium” c´ım˝ u, ” ´ TAMOP-4.2.2.C-11/1/KONV-2012-0010 azonos´ıtószám´ u projekt támogatta az Eur´ opai Uni´ o és az Európai Szociális Alap társfinansz´ıroz´ asa mellett. A tanul´ mány a TAMOP-4.2.1/B-09/1/KONV-2010-0003 Mobilitás és környezet: J´ arm˝ uipari, energetikai és környezeti kutatások a Közép- és Nyugat-Dunánt´ uli Régióban ´ projekt támogatásával jött létre, a projekt a Magyar Allam és az Európai Unió támogat´ as´ aval, az Európai Szociális Alap társfinansz´ıroz´ asával valósul 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. ´ ´ n, J. Balogh, J. Be ´ ke ´si, B. Da ´ vid, M. Kre ´sz, and A. To ´ th: A flexible system [4] V. Argil a for optimizing public transportation, In Proceedings of the 8th International Conference on Applied Informatics, Vol. 2, 181–190, 2010. ´ ´ n, J. Balogh, J. Be ´ke ´si, B. Da ´ vid, M. Kre ´sz, and A. To ´ th: Driver sche[5] V. Argil a duling 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. ´ ´ n, B. Da ´ vid, Cs. Keme ńy, G. Pongra ´ cz, and A. To ´ th: Greedy heuristics [6] V. Argil a 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)



35

´ ´ n, J. Balogh, J. Be ´ke ´si, B. Da ´ vid, G. Galambos, M. Kre ´sz, and A. To ´ th: [7] V. Argil a An Assignment Model for Real-World Vehicle Scheduling Problem with Refueling, k¨ ozl´ esre 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. ´ ke ´si, G. Galambos, and M. Kre ´sz: Model and Algorithm for a Vehicle [9] J. Balogh, J. Be Scheduling Problem with Refueling, In Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems, 229–231, 2009. ´ ke ´si, A. Brodnik, D. Pash, and M. Kre ´sz: An integrated framework for bus logistic [10] J. Be management: case studies, In Logistik Management, Physica-Verlag, 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 Computer-aided 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. ´ vid: Heuristics for the Multiple-Depot Vehicle Scheduling Problem, In Proceedings of [20] B. Da 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) ´ vid and M. Kre ´sz: Application Oriented Variable Fixing Methods for the Multiple [21] B. Da Depot Vehicle Scheduling Problem, Acta Cybernetica-Szeged, 21(1), 53–73, 2013. [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.


36


[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, SpringerVerlag, 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. [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 Computer-Aided 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.



37

[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 Computer-aided 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. [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 multiple-vehicle-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 MultiplieDepot 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.


38


[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. [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´ erhet˝ 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.



39

[69] U.U. Suhl, S. Friedrich, and V. Waue: Progress in solving large scale multi-depot multivehicle-type bus scheduling problems with integer programming, Wirtschaftinformatik Proceedings, Paper 81, 2007. http://aisel.aisnet.org/wi2007/81 ´ th and M. Kre ´sz: A flexible framework for driver scheduling, In Proceedings of the [70] A. To 11th International Symposium on Operational Research in Slovenia – SOR’11, 341–346, 2011. (ISBN: 978-961-6165-35-8) ´ th and M. Kre ´sz: An efficient solution approach for real-world driver scheduling [71] A. To 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.

(Be´ erkezett: 2013. okt´ ober 4.)

´ ´ VIKTOR ARGIL AN ´ BALOGH JANOS ´ ESI ´ JOZSEF ´ BEK ´ ´ DAVID BALAZS ´ GALAMBOS GABOR ´ ´ KRESZ MIKLOS ´ TOTH ATTILA Szegedi Tudom´ anyegyetem Juh´ asz Gyula Pedag´ ogusk´ epz˝ o Kar Informatika Alkalmaz´ asai Tansz´ ek 6701 Szeged, Pf. 396. {gilan,balogh,bekesi,davidb,galambos,kresz,attila}@jgypk.u-szeged.hu


40


SCHEDULING PROBLEMS IN THE OPERATIVE PLANNING OF PUBLIC BUS TRANSPORTATION ´ ´ n, Ja ´ nos Balogh, Jo ´ zsef Be ´ke ´si, Bala ´ zs Da ´ vid, Viktor Argil a ´ bor Galambos, Miklo ´ s Kre ´sz, Attila To ´ th Ga Optimization of operative costs is an important aim of public transportation companies. Their planning process can be aided by the optimization of scheduling of vehicle journeys, vehicle schedules, and driver shifts. The problem is a complex optimization problem. For this reason, we deal with the whole problem in three separate phases: vehicle scheduling, driver scheduling and driver rostering. Each sub-problem is NP-hard, and there was no possibility to obtain the optimal solution for large or even middle-sized problems until the last decade. Because of the increase in computational speed and the development of new scheduling methods, researchers today can handle larger problems also. We deal with the mathematical models and solution of these efficient methods. We also refer to our solution methods and the role of the special constraints is analyzed based on our experiences.


Alkalmazott Matematikai Lapok 31 (2014), alkalmazott modellek és az azokat megoldó algoritmusok olyan jelentősen fejlődtek,

Recommend Documents