reititysongelmat

Reititysongelmat ovat optimointitehtäviä, joissa tavoitteena on löytää optimaalisin reitti tai reittien kokonaisuus tiettyjen kohteiden välillä annettujen rajoitteiden puitteissa. Ne esiintyvät laajasti logistiikassa, liikenteessä, verkkojen suunnittelussa ja robotiikassa. Tavoitteet voivat olla matkan pituuden tai kustannusten minimointi sekä aikataulujen, kapasiteettien tai muiden rajoitteiden noudattaminen.

Keskeisiä malleja ovat esimerkiksi Traveling Salesman Problem (TSP), jossa yhden reissun aikana on tarkoitus vierailla jokaisessa kaupungissa kerran mahdollisimman lyhyellä kokonaismatkalla; Vehicle Routing Problem (VRP), jossa usean ajoneuvon on palveltava asiakkaat siten, että kustannukset minimoidaan ja kapasiteetit sekä aikarajoitteet huomioidaan; sekä lyhyimmän polun ongelma (Shortest Path Problem, SPP), jossa etsitään kahden solmun välinen pienin reitti. Variantteja ovat esimerkiksi Capacitated VRP, VRP with Time Windows (VRPTW), Orienteering- ja Dial-a-Ride -ongelmat.

Ratkaisumenetelmät jakautuvat eksaktiin ja heuristiseen lähestymistapaan. Eksakteja menetelmiä käytetään esimerkiksi leikkausmenetelmissä ja kokonaislaskenta- (integer programming) malleissa, kun taas heuristiikat ja metaheuristiikat (kuten paikallinen haku, simuloitu annealing, tabu-haku, geneettiset algoritmit ja muurahaiskolonia -algoritmit) tarjoavat käytännöllisiä ratkaisuja suurille ongelmille.

Reititysongelmat mallinnetaan tavallisesti grafina: solmut edustavat kohteita ja kaaret reittejä, joiden painot kuvaavat matkan pituutta tai kustannusta. Osa malleista sisältää lisärajoitteita kuten aikataulut, kapasiteetit ja ajankohtiin liittyvät vaatimukset.

Sovelluksia ovat logistiikka, jakelu ja matkustajaliikenteen aikataulutus sekä robotiikka, joissa reititysongelmien ratkaisuilla voidaan parantaa tehokkuutta ja resurssien käyttöä. Tutkimus keskittyy sekä tarkkoihin ratkaisuun että käytännöllisiin, skaalautuviin heuristiikoihin.