search query: @keyword vehicle routing problem / total: 4
reference: 1 / 4
« previous | next »
| Author: | Saarela, Juho |
| Title: | Optimising and automating work planning by approximating the vehicle routing problem |
| Ajoneuvon reititysongelman hyödyntäminen työnsunnittelun optimoinnissa ja automatisoinnissa | |
| Publication type: | Master's thesis |
| Publication year: | 2016 |
| Pages: | 52 Language: eng |
| Department/School: | Perustieteiden korkeakoulu |
| Main subject: | Ohjelmistotekniikka (SCI3042) |
| Supervisor: | Malmi, Lauri |
| Instructor: | Berger, Florian |
| Electronic version URL: | http://urn.fi/URN:NBN:fi:aalto-201612226306 |
| Location: | P1 Ark Aalto 5960 | Archive |
| Keywords: | vehicle routing problem heuristic optimization automatization heuristiikka optimointi |
| Abstract (eng): | 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. |
| Abstract (fin): | 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. |
| ED: | 2017-01-08 |
INSSI record number: 55344
+ add basket
« previous | next »
INSSI