OPTIMALNO PLANIRANJE POTI V GRADBENIŠTVU Z REŠEVANJEM PROBLEMA TRGOVSKEGA POTNIKA OPTIMAL ROUTE PLANNING IN CIVIL ENGINEERING BY SOLVING TRAVELING SALESMAN PROBLEM doc. dr. Uroš Klanšek, univ. dipl. gosp. inž. red. prof. dr. Mirko Pšunder, univ. dipl. inž. grad. Univerza v Mariboru, Fakulteta za gradbeništvo, Smetanova 17, 2000 Maribor Marko Soršak, univ. dipl. gosp. inž. Štajerski inženiring, d. o. o., Hočka cesta 31 h, 2311 Hoče Strokovni članek UDK: 65.012.2:69 Povzetek l Problem trgovskega potnika (PTP) predstavlja enega najbolj znanih problemov kombinatorične optimizacije. Reševanje PTP izkazuje pomemben aplikativni potencial za gradbeništvo. Zato je namen pričujočega članka približati reševanje PTP širši gradbeniški skupnosti. V članku so predstavljeni formulacija PTP, uporabnost optimiza-cijskega modela PTP ter nekateri komercialno dostopni programski paketi, ki se lahko uporabijo za modeliranje in reševanje PTP. Na koncu članka je predstavljen primer optimalnega planiranja poti z reševanjem PTP. Summary l The traveling salesman problem (TSP) represents a well-known combinatorial optimization problem. Solving the TSP includes significant potential for civil engineering. In this way, the aim of this paper is to bring forward the solution of the TSP to the wider construction community. The paper presents the TSP formulation, the applicability of the TSP optimization model and the commercially available program packages for modelling and solving the TSP. An example of the optimal route planning by solving the TSP is presented at the end of the paper. 1«UVOD Problem trgovskega potnika (PTP) predstavlja enega najbolj znanih problemov kombinatorične optimizacije. PTP obravnava optimalno planiranje enkratnega obiska vseh podanih lokacij na seznamu po najkrajši mogoči poti, pri čemer morajo biti znane njihove medsebojne oddaljenosti. Kljub enostavni formulaciji se PTP zaradi svoje kombinatoričnosti uvršča med težko rešljive optimizacijske probleme. Začetek intenzivnega raziskovanja PTP s pomočjo računalnikov lahko umestimo v leto 1954, ko so George Dantzig, Ray Fulkerson in Selmer Johnson [Dantzig, 1954] objavili metodo za optimalno reševanje obsežnega PTP. Dantzig in njegova sodelavca so v omenjeni raziskavi uporabili predlagano metodo za reševanje PTP na množici 49 mest v Združenih državah Amerike in pridobljeni optimalni rezultat tudi predstavili, glej sliko 1. Poznejši razvoj računalnikov in povečevanje njihovih zmogljivosti je številnim uporabnikom omogočil uspešno reševanje vedno bolj kombinatoričnih PTP ob sprejemljivo dolgem računskem času. Pomembnejši mejniki v zgodovini reševanja kombinatoričnih PTP so predstavljeni v preglednici 1. Slika 1 • Optimalna rešitev PTP na množici 49 mest v ZDA [Dantzig, 1954) Leto Avtorji Kombinatoričnost PTP 1954 Dantzig, Fulkerson in Johnson 49 vozlišč 1971 Held in Karp 64 vozlišč 1975 Camerini, Fratta in Maffioli 67 vozlišč 1977 Grötschel 120 vozlišč 1980 Crowder in Padberg 318 vozlišč 1987 Padberg in Rinaldi 532 vozlišč 1987 Grötschel in Holland 666 vozlišč 1991 Padberg in Rinaldi 2392 vozlišč 1995 Applegate, Bixby, Chvatal in Cook 7397 vozlišč 1998 Applegate, Bixby, Chvatal in Cook 13.509 vozlišč 2001 Applegate, Bixby, Chvatal in Cook 15.112 vozlišč 2004 Applegate, Bixby, Chvatal, Cook in Helsgaun 24.978 vozlišč 2007 Cook, Espinoza in Goycoolea 33.810 vozlišč 2009 Applegate, Bixby, Chvatal, Cook, Espinoza, Goycoolea in Helsgaun 85.900 vozlišč Slika 2 • Optimalna rešitev PTP na množici 24.978 švedskih mest [Applegate, 2004) Preglednica 1 • Pomembnejši mejniki v zgodovini reševanja I kombinatoričnih PTP Izmed številnih pomembnih dosežkov zadnjega desetletja na področju raziskav in aplikacij PTP lahko izpostavimo zanimiv prispevek, ki so ga leta 2004 predstavili David Applegate, Robert Bixby, Vašek Chvatal, William Cook in Keld Helsgaun. V omenjenem prispevku so avtorji s pomočjo reševanja PTP izračunali optimalni potek in minimalno dolžino poti (približno 72.500 km), ki jo je treba opraviti za obisk 24.978 švedskih mest, glej sliko 2. Prav tako je treba izpostaviti prispevek [Applegate, 2009], v katerem je bila predstavljena optimalna rešitev za PTP na množici 85.900 vozlišč. Za reševanje ome- njenega PTP je bila uporabljena metoda ve-janja in omejevanja ter posebno generiranje celoštevilskih rezov. Prispevek [Applegate, 2009] je zanimiv, ker poroča o uspešnem izračunu optimalne rešitve za kombinatorični PTP, ki vsebuje rekordno veliko množico vozlišč. Na ta način je mogoče ugotoviti, da reševanje PTP izkazuje pomemben aplikativni potencial za gradbeništvo. Pomembnost PTP za gradbeni menedžment nakazujejo njegove aplikacije, kot so planiranje avtomatizirane vgradnje črpnega betona v objekt z računalniško krmiljeno opremo [Kunigahalli, 1998], planiranje dobave svežega betona [Feng, 2004], planiranje transporta materiala [Lei, 2009], planiranje serijske proizvodnje polizdelkov [Shixin, 2010], planiranje obhodov gradbišč pri zagotavljanju varstva pri delu [Cheng, 2010]. Zato je osnovni namen pričujočega članka približati reševanje PTP širši gradbeniški skupnosti. V nadaljevanju članka so predstavljeni formulacija PTP, uporabnost optimizacijskega modela PTP in nekateri komercialno dostopni programski paketi, ki se lahko uporabijo za modeliranje in reševanje PTP Na koncu članka je predstavljen primer optimalnega planiranja poti v gradbeništvu z reševanjem PTP. 2 • FORMULACIJA PROBLEMA TRGOVSKEGA POTNIKA 2.1 Splošna formulacija optimizacijskega problema PTP v svoji osnovni obliki predstavlja opti-mizacijski problem mešanega celoštevilskega linearnega programiranja (MILP). S pomočjo MILP lahko v splošnem rešujemo linearne opti-mizacijske probleme z zveznimi in diskretnimi spremenljivkami. Pri tem so lahko diskretne spremenljivke definirane kot celoštevilske spremenljivke ali pa kot binarne 0-1 spremenljivke. Splošni optimizacijski problem MILP lahko zapišemo v naslednji obliki: min z=cTx + dTy p.p. (MILP) Ax+By£b xeX = {x|xeR,xspt,= 1 /'=1,2,3,.../7 /=1 (PTP) /;y=1,2,3,.../7 yije{ 0,1} /;y=1,2,3,...n fre {1,2,3,-/7} /=1,2,3,...n kjer so: z namenska funkcija: utež skupne poti, i indeks: obravnavana lokacija, j indeks: sledeča lokacija, n konstanta: število vseh lokacij, t spremenljivka: zaporedna številka obravnavane lokacije na skupni poti, dj konstanta: utež povezave med obravnavano in sledečo lokacijo, yj spremenljivka: odločitev o izboru ali zavrnitvi povezave med lokacijama. Optimizacijski model PTP lahko predstavimo na sledeči način: vozlišča (indeksi) so lokacije, ki jih mora trgovski potnik obiskati, povezave med vozlišči pa so poti, ki jih mora potnik opraviti, da pride iz ene lokacije v drugo. Povezave med vozlišči so lahko različno dolge in lahko imajo različne omejitve (npr. omejitev hitrosti). Namenska funkcija PTP predstavlja utež skupne poti, ki je definirana kot vsota zmnožkov uteži dij in binarnih 0-1 spremenljivk yj po povezavah med lokacijami i in j, kjer sta i, j = 1, 2, 3 ... n. Utež povezave du običajno predstavlja dolžino poti, čas vožnje ali stroške za prevoz od obravnavane lokacije i do sledeče lokacije j. Na ta način lahko namenska funkcija PTP predstavlja skupno dolžino poti, skupni čas vožnje ali pa skupne prevozne stroške za obisk vseh lokacij, ki so določene na seznamu. Binarne 0-1 odločitvene spremenljivke yu so v modelni formulaciji uporabljene za diskretne odločitve o izboru (y = 1) ali pa zavrnitvi (y:j = 0) povezave med lokacijami. Pogojni enačbi % yu = 1 in % yj = 1 zagotavljata, da mora potnik, ki zapusti obravnavano lokacijo, obiskati natanko eno sledečo lokacijo ter da mora potnik prispeti na sledečo lokacijo z natanko ene predhodne lokacije. Omenjeni pogojni enačbi zagotavljata, da bo vsaka lokacija obiskana natanko enkrat, razen prve, ki bo hkrati tudi zadnja obiskana lokacija na skupni poti. Pogojna neenačba t, - tj < n(1 - y) - 1 služi za določitev vrstnega reda, po katerem mora potnik obiskovati lokacije na poti. Omenjena pogojna neenačba deluje na naslednji način. Če je izbrana pot med dvema lokacijama, potem se zaporedna številka sledeče lokacije v primerjavi z zaporedno številko obravnavane lokacije poveča za ena. Pri tem je treba poudariti, da so zaporedne številke lokacij na poti določene s pozitivnimi celimi števili od 1 do n. Če pot med lokacijama ni izbrana, potem desna stran neenačbe tj s t + 1 - n izkazuje negativno vrednost za vse t, ki so manjši od n - 1, in vrednost nič, ko je t enak n - 1. Ob predpostavki pozitivnih zaporednih številk lokacij omenjena neenačba pri yj = 0 ne bo odločilna za izbor tj Sistem predstavljenih pogojnih enačb in neenačb optimizacijskega modela PTP zagotavlja, da izračunana minimalna skupna dolžina poti hkrati predstavlja tudi minimalni Hamiltonov cikel. PTP je lahko simetričen ali pa nesimetričen. Pri simetričnih PTP za uteži povezav med lokacijami velja, da so du = d, To pomeni, da je posamezna utež neodvisna od smeri povezave med lokacijama. Na ta način je, na primer, čas vožnje za pot v smeri od lokacije i do lokacije j enak času vožnje za enako pot v nasprotni smeri, tj. od lokacije j do lokacije i. Pri nesimetričnih PTP je lahko d^ * d,,, kar pomeni, da je vrednost uteži odvisna od smeri povezave. Primer odvisnosti uteži od smeri povezave je, recimo, čas vožnje po avtocesti, ko je pas avtoceste v eni smeri delno zaprt zaradi obnovitvenih del in zaradi tega velja na njego- vem prevoznem delu bolj restriktivna omejitev hitrosti, medtem ko takšne omejitve hitrosti za promet v drugi smeri ni. V takšnem primeru tudi čas vožnje za enako pot po avtocesti, vendar v različnih smereh, ne more biti enak. PTP predstavlja optimizacijski problem MILP z n2 + n odločitvenih spremenljivk in 2n + n (n - 1) pogojnih (ne)enačb. Omenili smo, da se PTP uvršča med težko rešljive pro- bleme kombinatorične optimizacije. PTP pri polnem grafu vsebuje (n - 1)! Hamiltonovih ciklov, tj. možnih rešitev. Prav zaradi tega za PTP še vedno vlada izjemno zanimanje med raziskovalci, čeprav se na tem optimizacij-skem problemu intenzivno raziskuje praktično že od tridesetih let prejšnjega stoletja, glej npr. reference ([Larusic, 2011], [Majumdar, 2011], [Chen, 2011]). 3 • UPORABNOST OPTIMIZACIJSKEGA MODELA PROBLEMA TRGOVSKEGA POTNIKA PTP ni aktualen le v teoretičnem smislu, ampak tudi z vidika praktične uporabnosti. Poleg prikazane osnovne formulacije PTP obstajajo še druge različice tega optimizacijskega problema. Ena od različic je PTP z možnim ponavljanjem obiska lokacij, kjer se pogoj, da mora biti lokacija obiskana natanko enkrat, spremeni v manj restriktivni pogoj, tj., da mora biti lokacija obiskana vsaj enkrat. Poseben primer so PTP z več potniki, pri katerih mora vsako od lokacij obiskati vsaj en potnik. Zelo pogosto je obravnavana tudi različica, ki se imenuje evklidski PTP, kjer so lokacije opredeljene s koordinatami in razporejene v dvo- ali tridimenzionalnem prostoru, dolžine poti med njimi pa so določene z evklidskimi razdaljami. Ena od pogostih aplikacij PTP je optimalno planiranje poti za dostavo blaga poslovnim partnerjem na oddaljenih lokacijah s pomočjo prevoznih sredstev iz voznega parka podjetja [Christofides, 1985]. Z reševanjem omenjene različice PTP se določi optimalni vrstni red obiskov poslovnih partnerjev in se za vsako lokacijo določi prevozno sredstvo iz voznega parka podjetja, s katerim se bo opravil obisk. Pri tem PTP običajno vsebuje dodatne časovne omejitve za obisk poslovnih partnerjev in tudi omejitve kapacitet prevoznih sredstev. Zelo znana je tudi aplikacija PTP, ki obravnava optimalno planiranje zaporedja izvedbe del v proizvodnem obratu [Garfinkel, 1985]. Omenjeno aplikacijo PTP lahko predstavimo na naslednji način. V proizvodnem obratu je treba v delovni izmeni opraviti n-število različnih del. Indeks i = 1, 2, 3 ... n določa obravnavano delo, indeks j =1, 2, 3 ... n pa neposredno sledeče delo. Pri tem se dela ne morejo opravljati vzporedno, lahko pa se izvedejo v kateremkoli zaporedju. Po dokončanju vsakega obravnavanega dela i ter pred pričetkom neposredno sledečega dela j je treba v proizvodnem obratu opraviti pripravljalna dela, ki zahtevajo čas d,. Osnovni namen reševanja omenjene različice PTP je poiskati optimalno zaporedje izvajanja del, tako da bo skupni čas pripravljalnih del najkrajši. Zanimiva je tudi aplikacija PTP za določanje optimalnega zaporedja poti, ki jih mora skladiščnik opraviti, ko prejme naročilo stranke za dostavo raznovrstnega blaga, ki je na več različnih lokacijah v velikem centralnem skladišču [Ratliff, 1983]. Skladiščnik mora ob prejemu naročila obiskati vse lokacije, na katerih so različni kosi naročenega blaga, vse kose prevzeti in jih stranki dostaviti. V obojestranskem interesu stranke in skladiščnika je, da se blago čim prej dostavi. Za skladiščnika to lahko pomeni najkrajšo skupno pot, ki jo mora opraviti po skladišču, za stranko pa to pomeni najkrajši čas od predaje naročila do prevzema blaga. 4 • RAČUNALNIŠKO MODELIRANJE IN REŠEVANJE PROBLEMA TRGOVSKEGA POTNIKA Za računalniško modeliranje in reševanje PTP ima uporabnik na voljo številno komercialno dostopno programsko opremo. Za modeliranje kombinatoričnih PTP je priporočljivo uporabiti algebrajske modelirne jezike, kot so npr. AIMMS [Bisschop, 1999], AMPL [Fourer, 1990], GAMS [Brooke, 1988], LINGO [Lindo, 1988]. Sintaksa algebrajskih modelirnih jezikov je fleksibilna in omogoča, da se lahko s pomočjo indeksiranja tudi obsežni optimizacijski modeli zapišejo v kompaktni obliki. Pri modeliranju PTP je mogoče uporabiti tudi različne interaktivne računalniške jezike, med katerimi lahko izpostavimo programska paketa Mathematica [Wolfram, 1988] in Mat- lab [Moler, 1980], ki se najpogosteje uporabljata. Med uporabniki so zelo priljubljeno orodje za modeliranje PTP tudi modelirne preglednice. Eden najpogosteje uporabljenih programskih orodij za modeliranje optimiza-cijskih problemov s pomočjo preglednic je Microsoftov paket Excel z enim od dodatkov za optimizacijo, kot so npr. Solver, Evolver ali WhafsBest. Modelirne preglednice so uporabno orodje predvsem za modeliranje manj do srednje obsežnih PTP, ki vsebujejo zmerno število parametrov, ki jih je treba vstaviti v preglednico. Omenili smo, da PTP v svoji osnovni obliki predstavlja optimizacijski problem MILP. Za reševanje problemov MILP so uporabniku na razpolago številni učinkoviti in komercialno dostopni optimizacijski algoritmi, kot so npr. CPLEX [CPLEX, 1988], LINDO [Scharge, 1986], OSL [IBM Corporation, 1991]. Ponudniki komercialnih programskih paketov za modeliranje običajno navedejo optimizacij-ske algoritme, ki jih podpira njihov mode-lirnik. Reševanje PTP je mogoče opraviti tudi preko svetovnega spleta. Eden od možnih načinov je uporaba odprtih programov, ki so na strežniku NEOS [Czyzyk, 1998]. Na omenjenem strežniku je mogoče zaslediti številne povezave do komercialnih optimizacijskih programov, priročnike za njihovo uporabo, rezultate testov in raziskav na področju optimizacije, različne publikacije ipd. V nadaljevanju bomo na primeru iz gradbeništva predstavili optimalno planiranje poti s pomočjo reševanja PTP. Primer obravnava optimalno planiranje vrstnega reda obiskov nadzornika na naslednjih gradbiščih: • izgradnja srednjenapetostnega (SN) in nizkonapetostnega (NN) kablovoda v Ožbaltu, • izgradnja deponije drogov v Rušah, • izgradnja vila bloka v Kamnici, • izgradnja transformatorske postaje (TP), SN in NN kablovoda pri Treh kraljih na Pohorju, rekonstrukcija dveh stanovanj v Slovenski Bistrici, »dograditev 110 kV stikališča v Slovenskih Konjicah, izgradnja razdelilne transformatorske postaje (RTp) na Ptuju, »izgradnja stanovanjskega naselja Maj v Rogozi, »adaptacija RTP v Ljutomeru, »izgradnja RTP v Mačkovcih, • rekonstrukcija zgradbe Hotel Ocean v Mariboru in • izgradnja stanovanjsko-poslovnega objekta v Mariboru. Slika 3 predstavlja zemljevid, s katerega je razviden geografski položaj obravnavanih lokacij, ki jih je treba obiskovati pri izvajanju nadzora gradbišč. V proces planiranja so vključene samo tiste poti (povezave med lokacijami), ki jih nadzornik pri svojem delu najpogosteje uporablja. Razdalje med lokacijami gradbišč in časi za premostitev poti so pridobljeni s pomočjo programa Telefonski imenik Slovenije z aplikacijo, ki se uporablja za izdajo oziroma izpolnitev potnih nalogov [TIS, 2011]. Razdalje in časi, ki so potrebni za premostitev poti med lokacijami gradbišč v Mariboru, se zanemarijo. Pri oblikovanju modela za optimalno planiranje poti je predpostavljeno, da sta dolžina poti in potrebni čas pri premostitvi razdalj med gradbišči v obeh smereh enaka. Za boljšo predstavitev obravnavanega opti-mizacijskega problema je na sliki 4 predstavljen graf povezav med lokacijami gradbišč z razdaljami in časi, ki so potrebni za premostitev poti. Pri tem je treba poudariti, da prikazane razdalje in časi za premostitev poti med lokacijami gradbišč niso sorazmerni. Razdalje med lokacijami gradbišč so v grafu na sliki 4 podane v kilometrih in so zaokrožene na celoštevilsko vrednost (glej prvo številko na povezavi). Potrebni časi za premostitev poti med lokacijami gradbišč so na sliki 4 prikazani v minutah in so prav tako zaokroženi na Slika 3 • Geografski položaj lokacij gradbišč Slika 4 • Graf povezav med lokacijami gradbišč z razdaljami in časi za premostitev poti Pot dj M 5 M 15 M 21 7 26 M 70 5 M 23 M M M M M M M M 23 M 16 M M M M M M 15 M 16 M 21 M M M M M M M M 21 M 11 M M M M 21 M M M 11 M 16 25 M M 7 M M M M 16 M 24 M M 26 M M M M 25 24 M 35 55 M M M M M M M 35 M 37 70 M M M M M M 55 37 m Preglednica 2 • Matrika uteži d, za problem minimizacije skupne dolžine poti celoštevilsko vrednost (glej številko v oklepaju na povezavi). Sedež nadzornika je v Mariboru. Izvajanje nalog nadzornika poleg različnih del v pisarni na sedežu podjetja obsega tudi obisk gradbišč na seznamu dvakrat tedensko. Za delo v pisarni je na voljo en dan v tednu, druge štiri dni pa so na voljo za obisk gradbišč. Ob obisku vsakega gradbišča se običajno porabi okoli 30 minut delovnega časa. Prav tako je vsak delovni dan na voljo 30 minut časa za malico. Obisk gradbišč se začne iz pisarne na sedežu podjetja v Mariboru. Z reševanjem PTP je treba določiti najkrajšo možno pot, ki jo je treba opraviti pri izvajanju nadzora na predstavljenih gradbiščih, in tudi vrstni red obiskov gradbišč. Po drugi strani je treba z reševanjem PTP ugotoviti, ali je mogoče v dveh dneh obiskati vsa gradbišča in koliko znaša minimalni čas, ki ga je treba rezervirati za obisk vseh gradbišč. S slike 4 je razvidno, da povezave med lokacijami gradbišč ne tvorijo Hamiltonovega grafa. Namreč, pri Hamiltonovem grafu je mogoče vsako njegovo vozlišče obiskati natanko enkrat, razen prvega vozlišča, ki ga je mogoče obiskati na začetku in potem na koncu opravljene poti. V obravnavanem primeru je treba iti dvakrat skozi Slovensko Bistrico, če želimo obiskati gradbišče v Slovenskih Konjicah. Zato bomo pri reševanju optimizacijskega problema odmislili gradbišče v Slovenskih Konjicah, k pridobljeni optimalni rešitvi pa bomo na koncu prišteli dvakratno razdaljo oziroma dvakratni čas za premostitev poti od Slovenske Bistrice do Slovenskih Konjic. Najprej določimo množico lokacij gradbišč i = 1, 2, 3 ... n brez Slovenskih Konjic: (1) Maribor, (2) Kamnica, (3) Ožbalt, (4) Ruše, (5) Trije kralji, (6) Slovenska Bistrica, (7) Rogoza, (8) Ptuj, (9) Ljutomer in (10) Mačkovci. Obisk gradbišč se začne iz pisarne na sedežu podjetja v Mariboru, kar pomeni, da je t1 = 1. Vse druge lokacije gradbišč na podanem seznamu, to so i = 2, 3 ... 10, se po opravljeni optimizaciji oštevilčijo z zaporedno številko lokacije na skupni poti, za katero velja 2 < t < 10. Matrika uteži namenske funkcije dij (km) za problem minimizacije skupne dolžine poti je predstavljena v preglednici 2. Simbol ^ označuje tista polja matrike dLj, pri katerih ni povezave med lokacijo i in lokacijo j. Za rešitev zastavljene optimiza-cijske naloge je uporabljena predstavljena modelna formulacija za PTP. Za modeliranje PTP je uporabljen algebrajski modelirni jezik GAMS (General Algebraic Modelling System) (Brooke, 1988). Optimizacijski model MILP za obravnavani primer vsebuje namensko funkcijo, 110 pogojnih (ne)enačb (10 enačb Zj Yij = 1, 10 enačb Z yij = 1 in 90 neenačb ti - tj < n (1 - Y,) - 1), spremenljivko namenske funkcije z in 110 odločitvenih spremenljivk (100 spremenljivk yij in 10 spremenljivk t). Za izračun optimalne rešitve obravnavanega PTP je uporabljen programski paket CPLEX (CPLEX Optimization Inc., 1988). Na sliki 5 je predstavljena izračunana optimalna rešitev za obravnavani problem mini- mizacije skupne dolžine poti, ki upošteva minimalni Hamiltonov cikel. Pridobljena minimalna skupna dolžina poti znaša 288 km in vključuje izračunani minimalni Hamiltonov cikel dolžine 258 km, ki mu je naknadno prišteta dvakratna dolžina poti od gradbišča v Slovenski Bistrici do gradbišča v Slovenskih Konjicah, tj. 30 km. S slike 5 je razvidno, da so lokacije gradbišč na skupni poti oštevilčene s številkami od 1 do 10, ki predstavljajo optimalne vrednosti spremenljivk 11 do t10 (gradbišče v Slovenskih Konjicah ni oštevilčeno, ker ni bilo vključeno v optimizacijo). Tako je, na primer, v zaporedju desetih lokacij gradbišče v Rogozi oštevilčeno kot peta lokacija, tj. t7 = 5. Predstavljena rešitev minimalne skupne poti predvideva, da bo gradbišče v Slovenskih Konjicah obiskano takoj za gradbiščem v Slovenski Bistrici, tj. v okviru obiska šeste lokacije. Matrika uteži namenske funkcije d (min) za problem minimizacije skupnega časa za obisk gradbišč je prikazana v preglednici 3. Pri reševanju problema minimizacije skupnega časa za obisk gradbišč je bila izračunana enaka rešitev poteka skupne poti kot pri minimiza-ciji skupne dolžine poti, glej sliko 5. Časovni potek obiskov gradbišč za pridobljeno rešitev, ki upošteva minimalni Hamiltonov cikel, je prikazan v preglednici 4. Slika 5 • Rešitev minimalne skupne dolžine poti, ki upošteva minimalni Hamiltonov cikel Čas di,j: 5 11 12 6 16 50 5 17 17 10 11 10 32 32 14 12 14 9 16 CD 9 15 16 16 15 ^ 30 46 30 31 50 46 31 Preglednica 3 • Matrika uteži d, za problem minimizacije skupnega časa za obisk gradbišč Gradbišče Čas za pot do sledeče lokacije [min) Čas na gradbišču [min) Skupni čas [min) Maribort 50 60 110 Mačkovci 31 30 61 Ljutomer 30 30 60 Ptuj 15 30 45 Rogoza 9 30 39 Slovenska Bistrica 10 30 40 Slovenske Konjice 10 30 40 Slovenska Bistrica 14 0 14 Trije kralji 32 30 62 Ruše 10 30 40 Ožbalt 17 30 47 Kamnica 5 30 35 Malica* 60 Skupaj: 233 360 653 Opombe: t Za ogled dveh gradbišč v Mariboru se porabi 2-krat 30 minut. * V dveh delovnih dneh se za malico porabi 2-krat 30 minut. Preglednica 4 • Časovni potek obiska gradbišč za rešitev, ki upošteva minimalni Hamiltonov cikel Gradbišče Čas za pot do sledeče lokacije [min) Čas na gradbišču [min) Skupni čas [min) Maribort 6 60 110 Rogoza 6 30 61 Maribor 50 0 60 Mačkovci 31 30 45 Ljutomer 30 30 39 Ptuj 16 30 Slovenska Bistrica 10 30 40 Slovenske Konjice 10 30 40 Slovenska Bistrica 14 0 14 Trije kralji 32 30 62 Ruše 10 30 40 Ožbalt 17 30 47 Kamnica 5 30 35 Malica* 60 Skupaj: 237 360 657 Opombe: t Za ogled dveh gradbišč v Mariboru se porabi 2-krat 30 minut. * V dveh delovnih dneh se za malico porabi 2-krat 30 minut. Preglednica 5 • Časovni potek obiska gradbišč za rešitev, ki upošteva ponavljanje obiska lokacij Slika 6* Rešitev minimalne skupne dolžine poti, ki upošteva ponavljanje obiskov lokacij Iz preglednice 4 je razvidno, da minimalni skupni čas za potovanje po celotni dolžini poti znaša 233 minut in vključuje 213 minut časa za minimalni Hamiltonov cikel, ki mu je naknadno prištet dvakratni čas za pot od gradbišča v Slovenski Bistrici do gradbišča v Slovenskih Konjicah, tj. 20 minut. Za obiske gradbišč na seznamu je treba rezervirati najmanj 653 minut. Pridobljeni optimalni načrt obiskov gradbišč kaže, da je treba predvideti 233 minut za premostitev poti od gradbišča do gradbišča, 360 minut za ogled gradbišč in 60 minut za malico. Iz rešitve je razvidno, da je mogoče opraviti enkratni obisk vseh gradbišč na seznamu v okviru dveh delovnih dni (tj. 16 ur oziroma 960 minut), ki sta za to na voljo. Poskusimo zdaj poiskati boljšo rešitev za minimalno skupno dolžino poti, tako da omogočimo ponavljanje obiska lokacij na seznamu. Pogoj, da mora biti lokacija obiskana natanko enkrat, spremenimo v manj restriktivni pogoj, tj., da mora biti lokacija obiskana vsaj enkrat, in ponovimo izračun optimalne rešitve obravnavanega PTP Pridobljena rešitev minimalne skupne dolžine poti, ki upošteva ponavljanje obiska lokacij, je prikazana na sliki 6. Minimalna skupna dolžina poti pri rešitvi, ki upošteva ponavljanje obiska lokacij, znaša 287 km in vključuje izračunano minimalno pot dolžine 257 km za obisk vseh lokacij gradbišč, ki so bile vključene v optimizacijo, in naknadno prišteto dvakratno dolžino poti od gradbišča v Slovenski Bistrici do gradbišča v Slovenskih Konjicah, tj. 30 km. Minimalna skupna dolžina poti za rešitev, ki upošteva večkratni obisk lokacij, je za en km krajša od minimalne skupne dolžine poti za rešitev, ki upošteva minimalni Hamiltonov cikel. Rešitev, ki upošteva večkratni obisk lokacij, predvideva, da se iz pisarne v Mariboru najprej opravi obisk gradbišča v Rogozi in se nato vrne nazaj v Maribor, šele potem pa se nadaljuje z obiskom drugih gradbišč. Zaradi predhodno opravljenega obiska v Rogozi se lahko po obisku gradbišča na Ptuju opravi obisk gradbišča v Slovenski Bistrici in izpusti gradbišče v Rogozi. Pri novi rešitvi je treba prevoziti 14 km za pot Maribor-Rogoza-Mari-bor in 25 km za pot Ptuj-Slovenska Bistrica, tj. skupaj 39 km. Pri rešitvi, ki je upoštevala minimalni Hamiltonov cikel, je bilo treba za obisk istih lokacij gradbišč prevoziti 40 km, tj. 24 km za pot Ptuj-Rogoza in 16 km za pot Rogoza-Slovenska Bistrica. Vidimo, da je mogoče z upoštevanjem manj restriktivnih pogojev, ki omogočajo večkratni obisk lokacij, doseči rešitev, ki izkazuje krajšo skupno dolžino poti. Po drugi strani omenjena rešitev izkazuje štiri minute daljši skupni čas, ki ga je treba rezervirati za obisk vseh gradbišč. V preglednici 5 je predstavljen časovni potek obiska gradbišč za rešitev, ki upošteva ponavljanje obiska lokacij. 6*SKLEP V članku je bilo predstavljeno optimalno planiranje poti v gradbeništvu z reševanjem PTP. Osnovni namen predstavljenega članka je bil približati reševanje PTP širši gradbeniški skupnosti. V ta namen so bili predstavljeni formulacija PTP, uporabnost optimizacijskega modela PTP ter nekateri komercialno dostopni programski paketi, ki se lahko koristno uporabijo pri modeliranju in reševanju PTP. Široka komercialna dostopnost programskih paketov za modeliranje in optimizacijo dajejo reševanju PTP pomemben aplikativni potencial za gradbeništvo. Na koncu članka je bil predstavljen enostaven primer iz gradbeništva, kjer je bilo obravnavano optimalno planiranje poti s pomočjo reševanja PTP. S predstavitvijo uporabnosti optimizacijskega modela PTP smo pokazali, da ga je mogoče (z večjimi ali manjšimi modifikacijami) koristno uporabiti tudi pri reševanju drugih, trgovskemu potniku sorodnih optimizacijskih problemov. Tako je mogoče model PTP v gradbeništvu koristno uporabiti za optimalno planiranje dobave, transporta in vgradnje gradbenih materialov, polizdelkov ali izdelkov, planiranje serijske in masovne proizvodnje, planiranje obhodov gradbišč pri kontroli kakovosti, izvajanju nadzorstva ali zagotavljanju varstva pri delu, planiranje poti in angažiranje prevoznih sredstev, upravljanje skladišč. PTP v splošnem predstavlja težko rešljivi problem kombinatorične optimizacije. Po drugi strani je treba na koncu poudariti, da PTP, s katerimi se največkrat soočamo v vsakdanji gradbeniški praksi, niso pretirano kombinatorični in jih je mogoče povsem zadovoljivo reševati s komercialno dostopnimi programskimi paketi za optimizacijo. Na ta način se lahko model PTP v številnih primerih izkaže kot učinkovito alternativno orodje gradbenega menedžmenta. 7 • LITERATURA Applegate, D., Bixby, R., Chvatal, V., Cook, W., Finding cuts in the TSP (A preliminary report), DIMACS Technical Report 95-05,1995. Applegate, D., Bixby, R., Chvatal, V., Cook, W., On the solution of travelling salesman problems, Documenta Mathematica (Journal der Deutschen Mathematiker-Vereinigung), International Congress of Mathematicians, str. 645-656, 1998. Applegate, D., Bixby, R., Chvatal, V., Cook, W., TSP cuts which do not conform to the template paradigm, Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions, Volume 2241 of Lecture Notes in Computer Science, Springer-Verlag, London, str. 261-304, 2001. Applegate, D., Bixby, R., Chvatal, V., Cook,W., The traveling salesman problem: a computational study, Princeton University Press, Princeton, 2006. Applegate, D., Bixby, R., Chvatal, V., Cook, W. The traveling salesman problem, http://www.tsp.gatech.edu/, 2004. Applegate, D., Bixby, R. E., Chvatal, V., Cook, W., Espinoza, D., Goycoolea, M., Helsgaun, K., Certification of an optimal TSP tour through 85.900 cities. Operations Research Letters, 37(1), str. 11-15, 2009. Bisschop, J. J., Roelofs, M., AIMMS: the language reference, Haarlem: Paragon Decision Technology BV, 1999. Brooke, A., Kendrick, D., and Meeraus, A., GAMS - a user's guide, Redwood City: Scientific Press, 1988. Camerini, P. M., Fratta, L., Maffioli, F., On improving relaxation methods by modified gradient techniques, Mathematical Programming Study, 4, str. 26-34, 1975. Chen, S. M., Chien, C. Y. Parallelized genetic ant colony systems for solving the traveling salesman problem, Expert Systems with Applications 38(4), str. 3873-3883, 2011. Cheng, M. Y., Huang, K. Y. Genetic algorithm-based chaos clustering approach for nonlinear optimization, Journal of Marine Science and Technology 18(3), str. 435-441, 2010. Cook, W., Espinoza, D., Goycoolea, M., Computing with domino-parity inequalities for the TSP, INFORMS Journal on Computing 19(3), str. 356-365, 2007. CPLEX Optimization Inc., Using the CPLEX linear optimizer, Houston, 1988. 1980. Czyzyk, J., Mesnier, M. P., Moré, J. J. The NEOS Server, IEEE Computational Science and Engineering 5(3), str. 68-75, 1998. Dantzig, G. B., Fulkerson, D. R., Johnson, S. M., Solution of a large scale traveling salesman problem, Operations Research 2(4), str. 393-410, 1954. Feng, C. W., Cheng, T. M., Wu, H. T. Optimizing the schedule of dispatching RMC trucks through genetic algorithms, Automation in Construction 13(3), str. 327-340, 2004. Fourer, R., Gay, D. M., Kermighan, B. W. A modelling language for mathematical programming, Management Science 36(5), str. 519-554, 1990. Google Earth, http://www.google.com/earth/index.html. 2011. Grotschel, M., Polyedrische charackterisierungen kombinatorischer optimierungsprobleme, Anton Hain Verlag, Meisenheim/Glan, 1977. Grotschel, M., Holland, O., A cutting plane algorithm for minimum perfect 2-matchings, Computing, 39 (4), str. 327-344, 1987. Held, M., Karp, R. M., The traveling-salesman problem and minimum spanning trees: part II, Mathematical Programming, 1(1), str. 6-25, 1971. IBM Corporation, Optimization subroutine library guide and reference, Release 2, New York, 1991. Kunigahalli, R., Veeramani, D. Computer-aided process planning for CNC pumped-concrete placement, Computer-Aided Civil and Infrastructure Engineering 13(4), str. 275-288, 1998. Larusic, J., Punnen, A. P. The balanced traveling salesman problem, Computers and Operations Research 38(5), str. 868-875, 2011. Lei, Z., Hongqi, H., Stochastic disturbance recovery theory and rotation algorithm on the traveling salesman problem in material transportation, Proceedings of the 2nd International Conference on Transportation Engineering, Chengdu, China, str. 1578-1583, 2009. Lindo Systems Inc., LINGO modelling system, 1988. Majumdar, J., Bhunia, A. K. Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times, Journal of Computational and Applied Mathematics 235(9), str. 3063-3075, 2011. Moler, C. B., MATLAB user's guide, Technical Report CS81-1, Albuquerque: University of New Mexico, Department of Computer Science, 1980. Padberg, M., Rinaldi, G., Optimization of a 532-city symmetric traveling salesman problem by branch and cut, Operations Research Letters 6(1), str. 1-7, 1987. Padberg, M., Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review 33(1), str. 60-100, 1991. Schrage, L., Linear, integer and quadratic programming with LINDO, Palo Alto: Scientific Press,1986. Shixin, L. Model and algorithm for hot rolling batch planning in steel plants, International Journal of Information and Management Sciences 21(3), str. 247-263, 2010. Telefonski imenik Slovenije, http://www.itis.si/, 2011. Wilson, R. J., Watkins, J. J., Graphs: an introductory approach - a first course in discrete mathematics, New York: John Wiley & Sons, 1990. Wolfram, S., Mathematica: A system for doing mathematics by computer. Redwood City: Addison-Wesley, 1988.