Fleet inference : importing vehicle routing problems using machine learning

Abstract

Tämä pro gradu -työ tutkii automaattisen päättelyn hyödyntämistä reitinoptimointiongelmien ratkaisemisessa. Reitinoptimointiongelma on kombinatorinen optimointiongelma, jonka ratkaiseminen edellyttää nk. ratkaisujärjestelmän luontia. Ratkaisujärjestelmä toimii ratkaisupalveluna, johon syötetään ongelman tiedot ja järjestelmä tuottaa ongelmasta optimoidun version.

Tämä toimintaketju alkaa ongelman tietojen tulkitsemisella. Tässä työssä esitellään menetelmä tämän askeleen nopeuttamiseksi. Koneoppimisella luodaan järjestelmä, jolle opetetaan esimerkkejä näyttäen miltä reitinoptimointiongelman data näyttää. Menetelmä on kaksiosainen: datasta etsitään rakenne sisäisten viittauksien ymmärtämiseksi ja kun datan rakenne on tulkittu, yhdistetään datassa löytyvä tieto vastaamaan varsinaisen optimointiongelman tietoja.

Aiemmin tämä askel on sisältänyt paljon käsityötä. Lisäksi optimointiympäristöt ovat edellyttäneet, että optimointiongelmat syötetään ratkaisijoihin tietyssä ja vain tietyssä muodossa. Datan muuntaminen tähän muotoon on vaivalloista. Siksi tässä gradussa esitellään tapa, joka automaatiota käyttäen säästää aikaa ja vaivaa operaatiotutkijalta.

Tämän ratkaisemiseksi gradussa tutkitaan kalustopäättelyä koneoppimista käyttäen. Kalustopäättely koostuu liitospäättelystä ja attribuuttiluokittelusta. Liitospäättely analysoi hajautetussa muodossa olevan datan, esimerkiksi useassa Excel R tai CSVtiedostossa sijaitsevan datan, keskinäiset viitteet ja muodostaa näistä rakenteen. Rakenteen muodostamisen jälkeen datasta löydetään se tarvittava tieto, jota optimointiin edellytetään—esimerkiksi datasta tarvitaan kalustoon kuuluvien autojen kapasiteetit, jotta ajoneuvot voidaan järjestellä oikein optimoinnissa.

Ratkaisu koostuu pitkälti menetelmästä, jossa algoritmia opetetaan näyttämällä esimerkkejä siitä, miten liitospäättelyssä liitokset muodostuvat ja miltä kohdeattribuutit näyttävät attribuuttiluokittelussa. Toisin sanoen, algoritmi opetetaan ymmärtämään miten datan sisäiset viitteet toimivat ja miten nämä kuvautuvat reaalimaailmaan eli lopputulokseen.

Esitelty ratkaisu on toteutettu erilaisin koneoppimisen menetelmin. Tässä työssä käymme läpi ratkaisun ymmärtämäisen vaadittavan teorian sekä testaamme kalustonpäättelyä konseptina läpikotaisesti. Tutkimme ensisijaisesti sitä, miten automaattisella datan käsittelyllä voidaan helpottaa vaativien optimointiongelmien ratkaisemista ja miten sellainen järjestelmä toteutetaan.

This thesis studies the use of automated reasoning in speeding up the process of converting vehicle routing problem data into data that is understood by a system that optimises them. The vehicle routing problem is a combinatorial optimisation problem, and we call the optimising system a solver for short. In this thesis, we consider a solver a program that functions using the software-as-a-service paradigm: problem descriptions are entered into the system, and the solver produces an optimised version of the problem.

Traditionally, solvers require the problem descriptions to be in a particular data format. Such data usually exists in other formats, and a great effort must be put in converting them to the accepted format. This is usually done manually by operations researchers, and such conversion can be onerous and time-consuming. In light of this, we study the use of machine learning in creating a system that can understand a variety of input data formats and convert the source data into one target format, letting operations researchers shift their focus away from demanding data processing tasks.

To this end, we implement such a framework, titled fleet inference, using machine learning. The former finds links between data files, usually column oriented CSV or Excel files, and the latter pairs source data entities into target entities.

This thesis implements fleet inference using two separate modules—join inference and attribute classification. The framework consists of an automated classifier that is shown how optimisation problem data is structured, after this training the classifier can be used to understand structure in an otherwise seemingly unstructured data set. After a structure in these files has been obtained, we try to match data in them to data a vehicle routing problem solver needs—e.g., the capacities of vehicles available in the problem.

This system was implemented using a variety of classification techniques, and we present careful evaluations and introduce readers to the concepts of classification and data integration, all the while showing the apparent benefits of what automated reasoning can produce when faced with onerous data processing scenarios.