Fleet inference importing vehicle routing problems using machine learning

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...

Täydet tiedot

Bibliografiset tiedot
Päätekijä: Kalmbach, Antoine
Muut tekijät: Informaatioteknologian tiedekunta, Faculty of Information Technology, Tietotekniikan laitos, Department of Mathematical Information Technology, University of Jyväskylä, Jyväskylän yliopisto
Aineistotyyppi: Pro gradu
Kieli:eng
Julkaistu: 2014
Aiheet:
Linkit: https://jyx.jyu.fi/handle/123456789/44048
_version_ 1826225771827429376
author Kalmbach, Antoine
author2 Informaatioteknologian tiedekunta Faculty of Information Technology Tietotekniikan laitos Department of Mathematical Information Technology University of Jyväskylä Jyväskylän yliopisto
author_facet Kalmbach, Antoine Informaatioteknologian tiedekunta Faculty of Information Technology Tietotekniikan laitos Department of Mathematical Information Technology University of Jyväskylä Jyväskylän yliopisto Kalmbach, Antoine Informaatioteknologian tiedekunta Faculty of Information Technology Tietotekniikan laitos Department of Mathematical Information Technology University of Jyväskylä Jyväskylän yliopisto
author_sort Kalmbach, Antoine
datasource_str_mv jyx
description 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.
first_indexed 2024-09-11T08:51:27Z
format Pro gradu
free_online_boolean 1
fullrecord [{"key": "dc.contributor.author", "value": "Kalmbach, Antoine", "language": null, "element": "contributor", "qualifier": "author", "schema": "dc"}, {"key": "dc.date.accessioned", "value": "2014-08-18T11:00:39Z", "language": "", "element": "date", "qualifier": "accessioned", "schema": "dc"}, {"key": "dc.date.available", "value": "2014-08-18T11:00:39Z", "language": "", "element": "date", "qualifier": "available", "schema": "dc"}, {"key": "dc.date.issued", "value": "2014", "language": null, "element": "date", "qualifier": "issued", "schema": "dc"}, {"key": "dc.identifier.other", "value": "oai:jykdok.linneanet.fi:1444344", "language": null, "element": "identifier", "qualifier": "other", "schema": "dc"}, {"key": "dc.identifier.uri", "value": "https://jyx.jyu.fi/handle/123456789/44048", "language": "", "element": "identifier", "qualifier": "uri", "schema": "dc"}, {"key": "dc.description.abstract", "value": "T\u00e4m\u00e4 pro gradu -ty\u00f6 tutkii automaattisen p\u00e4\u00e4ttelyn\r\nhy\u00f6dynt\u00e4mist\u00e4 reitinoptimointiongelmien ratkaisemisessa. Reitinoptimointiongelma\r\non kombinatorinen optimointiongelma, jonka ratkaiseminen edellytt\u00e4\u00e4 nk. ratkaisuj\u00e4rjestelm\u00e4n\r\nluontia. Ratkaisuj\u00e4rjestelm\u00e4 toimii ratkaisupalveluna, johon sy\u00f6tet\u00e4\u00e4n\r\nongelman tiedot ja j\u00e4rjestelm\u00e4 tuottaa ongelmasta optimoidun version.\r\n\r\nT\u00e4m\u00e4 toimintaketju alkaa ongelman tietojen tulkitsemisella. T\u00e4ss\u00e4 ty\u00f6ss\u00e4 esitell\u00e4\u00e4n\r\nmenetelm\u00e4 t\u00e4m\u00e4n askeleen nopeuttamiseksi. Koneoppimisella luodaan j\u00e4rjestelm\u00e4,\r\njolle opetetaan esimerkkej\u00e4 n\u00e4ytt\u00e4en milt\u00e4 reitinoptimointiongelman data n\u00e4ytt\u00e4\u00e4.\r\nMenetelm\u00e4 on kaksiosainen: datasta etsit\u00e4\u00e4n rakenne sis\u00e4isten viittauksien ymm\u00e4rt\u00e4miseksi\r\nja kun datan rakenne on tulkittu, yhdistet\u00e4\u00e4n datassa l\u00f6ytyv\u00e4 tieto\r\nvastaamaan varsinaisen optimointiongelman tietoja.\r\n\r\nAiemmin t\u00e4m\u00e4 askel on sis\u00e4lt\u00e4nyt paljon k\u00e4sity\u00f6t\u00e4. Lis\u00e4ksi optimointiymp\u00e4rist\u00f6t\r\novat edellytt\u00e4neet, ett\u00e4 optimointiongelmat sy\u00f6tet\u00e4\u00e4n ratkaisijoihin tietyss\u00e4 ja vain\r\ntietyss\u00e4 muodossa. Datan muuntaminen t\u00e4h\u00e4n muotoon on vaivalloista. Siksi t\u00e4ss\u00e4\r\ngradussa esitell\u00e4\u00e4n tapa, joka automaatiota k\u00e4ytt\u00e4en s\u00e4\u00e4st\u00e4\u00e4 aikaa ja vaivaa operaatiotutkijalta.\r\n\r\nT\u00e4m\u00e4n ratkaisemiseksi gradussa tutkitaan kalustop\u00e4\u00e4ttely\u00e4 koneoppimista k\u00e4ytt\u00e4en.\r\nKalustop\u00e4\u00e4ttely koostuu liitosp\u00e4\u00e4ttelyst\u00e4 ja attribuuttiluokittelusta. Liitosp\u00e4\u00e4ttely\r\nanalysoi hajautetussa muodossa olevan datan, esimerkiksi useassa Excel R\r\ntai CSVtiedostossa\r\nsijaitsevan datan, keskin\u00e4iset viitteet ja muodostaa n\u00e4ist\u00e4 rakenteen.\r\nRakenteen muodostamisen j\u00e4lkeen datasta l\u00f6ydet\u00e4\u00e4n se tarvittava tieto, jota optimointiin\r\nedellytet\u00e4\u00e4n\u2014esimerkiksi datasta tarvitaan kalustoon kuuluvien autojen\r\nkapasiteetit, jotta ajoneuvot voidaan j\u00e4rjestell\u00e4 oikein optimoinnissa.\r\n\r\nRatkaisu koostuu pitk\u00e4lti menetelm\u00e4st\u00e4, jossa algoritmia opetetaan n\u00e4ytt\u00e4m\u00e4ll\u00e4 esimerkkej\u00e4\r\nsiit\u00e4, miten liitosp\u00e4\u00e4ttelyss\u00e4 liitokset muodostuvat ja milt\u00e4 kohdeattribuutit\r\nn\u00e4ytt\u00e4v\u00e4t attribuuttiluokittelussa. Toisin sanoen, algoritmi opetetaan ymm\u00e4rt\u00e4m\u00e4\u00e4n\r\nmiten datan sis\u00e4iset viitteet toimivat ja miten n\u00e4m\u00e4 kuvautuvat reaalimaailmaan eli\r\nlopputulokseen.\r\n\r\nEsitelty ratkaisu on toteutettu erilaisin koneoppimisen menetelmin. T\u00e4ss\u00e4 ty\u00f6ss\u00e4\r\nk\u00e4ymme l\u00e4pi ratkaisun ymm\u00e4rt\u00e4m\u00e4isen vaadittavan teorian sek\u00e4 testaamme kalustonp\u00e4\u00e4ttely\u00e4\r\nkonseptina l\u00e4pikotaisesti. Tutkimme ensisijaisesti sit\u00e4, miten automaattisella\r\ndatan k\u00e4sittelyll\u00e4 voidaan helpottaa vaativien optimointiongelmien ratkaisemista\r\nja miten sellainen j\u00e4rjestelm\u00e4 toteutetaan.", "language": "fi", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.abstract", "value": "This thesis studies the use of automated reasoning in speeding up the\r\nprocess of converting vehicle routing problem data into data that is understood by\r\na system that optimises them. The vehicle routing problem is a combinatorial optimisation\r\nproblem, and we call the optimising system a solver for short. In this thesis,\r\nwe consider a solver a program that functions using the software-as-a-service\r\nparadigm: problem descriptions are entered into the system, and the solver produces\r\nan optimised version of the problem.\r\n\r\nTraditionally, solvers require the problem descriptions to be in a particular data format.\r\nSuch data usually exists in other formats, and a great effort must be put in\r\nconverting them to the accepted format. This is usually done manually by operations\r\nresearchers, and such conversion can be onerous and time-consuming. In light\r\nof this, we study the use of machine learning in creating a system that can understand\r\na variety of input data formats and convert the source data into one target\r\nformat, letting operations researchers shift their focus away from demanding data\r\nprocessing tasks.\r\n\r\nTo this end, we implement such a framework, titled fleet inference, using machine\r\nlearning. The former finds links between data files, usually column oriented CSV or\r\nExcel files, and the latter pairs source data entities into target entities.\r\n\r\nThis thesis implements fleet inference using two separate modules\u2014join inference\r\nand attribute classification. The framework consists of an automated classifier that\r\nis shown how optimisation problem data is structured, after this training the classifier\r\ncan be used to understand structure in an otherwise seemingly unstructured\r\ndata set. After a structure in these files has been obtained, we try to match data in\r\nthem to data a vehicle routing problem solver needs\u2014e.g., the capacities of vehicles\r\navailable in the problem.\r\n\r\nThis system was implemented using a variety of classification techniques, and we\r\npresent careful evaluations and introduce readers to the concepts of classification\r\nand data integration, all the while showing the apparent benefits of what automated\r\nreasoning can produce when faced with onerous data processing scenarios.", "language": "en", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Submitted using Plone Publishing form by Antoine Kalmbach (anhekalm) on 2014-08-18 11:00:39.336286. Form: Pro gradu -lomake (https://kirjasto.jyu.fi/julkaisut/julkaisulomakkeet/pro-gradu-lomake). JyX data: [jyx_publishing-allowed (fi) =True]", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Submitted by jyx lomake-julkaisija (jyx-julkaisija@noreply.fi) on 2014-08-18T11:00:39Z\r\nNo. of bitstreams: 2\r\nURN:NBN:fi:jyu-201408182374.pdf: 869385 bytes, checksum: 9a6c482c805040d1419fd8c0a5253b74 (MD5)\r\nlicense.html: 4837 bytes, checksum: 5398f125a70aeb9349287bcddfa9cc39 (MD5)", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Made available in DSpace on 2014-08-18T11:00:39Z (GMT). No. of bitstreams: 2\r\nURN:NBN:fi:jyu-201408182374.pdf: 869385 bytes, checksum: 9a6c482c805040d1419fd8c0a5253b74 (MD5)\r\nlicense.html: 4837 bytes, checksum: 5398f125a70aeb9349287bcddfa9cc39 (MD5)\r\n Previous issue date: 2014", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.format.extent", "value": "1 verkkoaineisto.", "language": null, "element": "format", "qualifier": "extent", "schema": "dc"}, {"key": "dc.format.mimetype", "value": "application/pdf", "language": null, "element": "format", "qualifier": "mimetype", "schema": "dc"}, {"key": "dc.language.iso", "value": "eng", "language": null, "element": "language", "qualifier": "iso", "schema": "dc"}, {"key": "dc.rights", "value": "In Copyright", "language": "en", "element": "rights", "qualifier": null, "schema": "dc"}, {"key": "dc.subject.other", "value": "fleet inference", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "join inference", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "data integration", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "machine learning", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "vehicle routing problem", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "data exchange", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "attribute classification", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "operations research", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.title", "value": "Fleet inference : importing vehicle routing problems using machine learning", "language": null, "element": "title", "qualifier": null, "schema": "dc"}, {"key": "dc.type", "value": "master thesis", "language": null, "element": "type", "qualifier": null, "schema": "dc"}, {"key": "dc.identifier.urn", "value": "URN:NBN:fi:jyu-201408182374", "language": null, "element": "identifier", "qualifier": "urn", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Pro gradu -tutkielma", "language": "fi", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Master\u2019s thesis", "language": "en", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Informaatioteknologian tiedekunta", "language": "fi", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Faculty of Information Technology", "language": "en", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Tietotekniikan laitos", "language": "fi", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Department of Mathematical Information Technology", "language": "en", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "University of Jyv\u00e4skyl\u00e4", "language": "en", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "Jyv\u00e4skyl\u00e4n yliopisto", "language": "fi", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Tietotekniikka", "language": "fi", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Mathematical Information Technology", "language": "en", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "dc.date.updated", "value": "2014-08-18T11:00:40Z", "language": "", "element": "date", "qualifier": "updated", "schema": "dc"}, {"key": "dc.type.coar", "value": "http://purl.org/coar/resource_type/c_bdcc", "language": null, "element": "type", "qualifier": "coar", "schema": "dc"}, {"key": "dc.rights.accesslevel", "value": "openAccess", "language": null, "element": "rights", "qualifier": "accesslevel", "schema": "dc"}, {"key": "dc.type.publication", "value": "masterThesis", "language": null, "element": "type", "qualifier": "publication", "schema": "dc"}, {"key": "dc.subject.oppiainekoodi", "value": "602", "language": null, "element": "subject", "qualifier": "oppiainekoodi", "schema": "dc"}, {"key": "dc.subject.yso", "value": "koneoppiminen", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "tiedonsiirto", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.format.content", "value": "fulltext", "language": null, "element": "format", "qualifier": "content", "schema": "dc"}, {"key": "dc.rights.url", "value": "https://rightsstatements.org/page/InC/1.0/", "language": null, "element": "rights", "qualifier": "url", "schema": "dc"}, {"key": "dc.type.okm", "value": "G2", "language": null, "element": "type", "qualifier": "okm", "schema": "dc"}]
id jyx.123456789_44048
language eng
last_indexed 2025-02-18T10:56:39Z
main_date 2014-01-01T00:00:00Z
main_date_str 2014
online_boolean 1
online_urls_str_mv {"url":"https:\/\/jyx.jyu.fi\/bitstreams\/0c0f9f2c-6a3c-41ad-821c-9996e66c3db7\/download","text":"URN:NBN:fi:jyu-201408182374.pdf","source":"jyx","mediaType":"application\/pdf"}
publishDate 2014
record_format qdc
source_str_mv jyx
spellingShingle Kalmbach, Antoine Fleet inference : importing vehicle routing problems using machine learning fleet inference join inference data integration machine learning vehicle routing problem data exchange attribute classification operations research Tietotekniikka Mathematical Information Technology 602 koneoppiminen tiedonsiirto
title Fleet inference : importing vehicle routing problems using machine learning
title_full Fleet inference : importing vehicle routing problems using machine learning
title_fullStr Fleet inference : importing vehicle routing problems using machine learning Fleet inference : importing vehicle routing problems using machine learning
title_full_unstemmed Fleet inference : importing vehicle routing problems using machine learning Fleet inference : importing vehicle routing problems using machine learning
title_short Fleet inference
title_sort fleet inference importing vehicle routing problems using machine learning
title_sub importing vehicle routing problems using machine learning
title_txtP Fleet inference : importing vehicle routing problems using machine learning
topic fleet inference join inference data integration machine learning vehicle routing problem data exchange attribute classification operations research Tietotekniikka Mathematical Information Technology 602 koneoppiminen tiedonsiirto
topic_facet 602 Mathematical Information Technology Tietotekniikka attribute classification data exchange data integration fleet inference join inference koneoppiminen machine learning operations research tiedonsiirto vehicle routing problem
url https://jyx.jyu.fi/handle/123456789/44048 http://www.urn.fi/URN:NBN:fi:jyu-201408182374
work_keys_str_mv AT kalmbachantoine fleetinferenceimportingvehicleroutingproblemsusingmachinelearning