Optimising and automating work planning by approximating the vehicle routing problem

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Berger, Florian
dc.contributor.author Saarela, Juho
dc.date.accessioned 2016-12-22T11:24:18Z
dc.date.available 2016-12-22T11:24:18Z
dc.date.issued 2016-12-12
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/24013
dc.description.abstract The vehicle routing problem is a classic combinatorial problem with numerous real world applications. The basic problem is as follows: considering a depot and a list of service targets that all need to be visited, one needs to find the paths starting and ending at the depot with which the travelling time is as low as possible. In other words, VRP is the same as travelling salesman problem, except that there can be numerous routes and there are capacity limits to a single route. Because the problem is NP hard, finding the optimal solution is often out of the question. However, through heuristics, very good solutions can be found and used. From package delivery to cargo transports and taxi services, VRPs are a part of our everyday life. In this thesis we present that an algorithmic approach can be applied to a construction company's job planning process to automate manual labour and produce more optimal results. This is accomplished by abstracting the company's business logic, such as job target locations and estimated working times into parameters for the algorithm. The algorithm then creates routes for technicians covering all upcoming job targets so that the driving time is minimized. Due to the simplicity of the routing, the main benefit in this case comes from the automatization itself, as the quality of the plans is close to the results of manual labour. Though the jobs are still manually assigned to technicians and the algorithm only optimizes the order in which the jobs are done, it is shown that further development would make it possible to fully automate the process. The conclusion is that many companies could potentially benefit from this kind of automatization. en
dc.description.abstract Ajoneuvon reititysongelma (Vehicle Routing Problem, VRP) on klassinen kombinatorinen ongelma, jota voidaan soveltaa lukuisiin tosielämän ongelmiin. Ajoneuvon reititysongelma voidaan kuvata seuraavasti: Etsi reitit, joita käyttämällä käydään kaikissa työkohteissa siten, että matka-aika minimoidaan ja jokainen reitti alkaa ja päättyy tukikohtaan. Se muistuttaa vahvasti kaupparatsun ongelmaa (Travelling Salesman Problem, TSP), paitsi että reittejä voi olla useita ja yksittäinen reitti ei voi ylittää sille asetettuja kapasiteettirajoituksia. Ajoneuvon reititysongelma on NP-täydellinen, joten optimaalisen ratkaisun tuottaminen on usein laskennallisesti mahdotonta. Kehittyneet heuristiikat kykenevät kuitenkin tuottamaan erittäin hyviä ja käyttökelpoisia ratkaisuja. Pakettien ja rahdin toimituksesta aina taksiliikenteeseen, ajoneuvon reititysongelma liittyy vahvasti jokapäiväiseen elämäämme. Tässä opinnäytetyössä esitetään algoritminen lähestymistapa rakennusyrityksen työnsuunnittelun automatisointiin. Sen avulla pystytään vähentämään ihmistyön tarvetta ja tuottamaan parempia tuloksia. Abstrahoimalla yrityksen toimintalogiikkaa, kuten työkohteiden sijainteja ja työmääräarvioita voidaan näitä käyttää parametreina algoritmille, joka luo reitit työkohteiden kautta siten, että ajoaika minimoidaan. Reitityksen yksinkertaisuuden vuoksi tässä tapauksessa suurin hyöty saavutettiin itse automatisaatiosta, sillä reittisuunnitelmien laatu on likimain käsityöllä tehtyjen suunnitelmien tasoa. Vaikka työt edelleen allokoidaan käsityöllä asentajille ja algoritmi ainoastaan optimoi asennustöiden järjestyksen, tässä opinnäytetyössä todetaan, että jatkokehityksen myötä koko prosessi olisi automatisoitavissa. Johtopäätöksenä todetaan, että monet yritykset voisivat hyötyä tämänkaltaisesta automatisaatiosta. fi
dc.format.extent 49+3
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Optimising and automating work planning by approximating the vehicle routing problem en
dc.title Ajoneuvon reititysongelman hyödyntäminen työnsunnittelun optimoinnissa ja automatisoinnissa fi
dc.type G2 Pro gradu, diplomityö fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword vehicle routing problem en
dc.subject.keyword heuristic en
dc.subject.keyword optimization en
dc.subject.keyword automatization en
dc.identifier.urn URN:NBN:fi:aalto-201612226306
dc.programme.major Ohjelmistotekniikka fi
dc.programme.mcode SCI3042 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Malmi, Lauri
dc.programme Master’s Programme in Computer, Communication and Information Sciences fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account