AI utilization in route planning for delivery trucks within the supply chain
(2021) EITL05 20211Department of Electrical and Information Technology
- Abstract
- The supply chain has potential for growth. Many different parts can be optimized, and every possible improvement has not yet been tested. This study focuses on route optimization with the specific goal of figuring out how machine learning can be applied to route planning and how key factors that impact travel time for a route can be taken into account for this problem.
Time was dedicated to learning about machine learning, how it is applicable to route planning, as well as potential key factors that can be used with different machine learning algorithms. Once enough knowledge had been gathered, a prototype was implemented to verify key factors usability in route planning and test different route planning problems, such as point-to-point... (More) - The supply chain has potential for growth. Many different parts can be optimized, and every possible improvement has not yet been tested. This study focuses on route optimization with the specific goal of figuring out how machine learning can be applied to route planning and how key factors that impact travel time for a route can be taken into account for this problem.
Time was dedicated to learning about machine learning, how it is applicable to route planning, as well as potential key factors that can be used with different machine learning algorithms. Once enough knowledge had been gathered, a prototype was implemented to verify key factors usability in route planning and test different route planning problems, such as point-to-point routes and traveling salesman problem.
Key factors were gathered during the thesis work, and based on the result of the thesis, their ability to be used in route optimization was verified. Methods of collecting the key factors were looked into, and two algorithms were tested that had the potential of using these factors. The two algorithms proved the usability of key factors and showed their potential in route planning problems. First, the “Neural Evolution of Augmenting Topologies” algorithm was tested and verified that it could solve simple route planning problems. Although, it was later overshadowed by a genetic algorithm solution, which could solve point-to-point travel better and showed usefulness in the traveling salesman problem.
The thesis work did not provide a full-scale solution to optimizing route planning. However, several conclusions were made on the topic, such as the possibility of training neural networks using supervised learning to calculate edge cost and genetic algorithms showing its potential in multi-stop route planning. We believe that several of the conclusions made in the thesis could show promise in the area of route optimization given enough resources. (Less) - Abstract (Swedish)
- Försörjningskedjan har stor potential till optimering. Många olika delar av kedjan kan optimeras och alla tänkbara förbättringar har inte testats än. Denna studien har sitt fokus på ruttoptimering, med det specifika målet att förstå hur maskininlärning kan användas inom ruttplanering, samt hur nyckelfaktorer som påverkar restiden för en rutt kan tas i åtanke för problemet.
Tid lades på att studera maskininlärning, hur maskininlärning kan användas inom ruttplanering samt vilka potentiella nyckelfaktorer som kan användas i olika maskininlärnings algoritmer. När god kunskap inom maskininlärning hade erhållits, skapades en prototyp för att verifiera om nyckelfaktorerna var användbara inom ruttplanering. Prototypen användes även för att... (More) - Försörjningskedjan har stor potential till optimering. Många olika delar av kedjan kan optimeras och alla tänkbara förbättringar har inte testats än. Denna studien har sitt fokus på ruttoptimering, med det specifika målet att förstå hur maskininlärning kan användas inom ruttplanering, samt hur nyckelfaktorer som påverkar restiden för en rutt kan tas i åtanke för problemet.
Tid lades på att studera maskininlärning, hur maskininlärning kan användas inom ruttplanering samt vilka potentiella nyckelfaktorer som kan användas i olika maskininlärnings algoritmer. När god kunskap inom maskininlärning hade erhållits, skapades en prototyp för att verifiera om nyckelfaktorerna var användbara inom ruttplanering. Prototypen användes även för att testa olika typer av ruttplaneringsproblem, såsom punkt-till-punkt rutter och handelsresandeproblemet.
Nyckelfaktorer samlades in under examensarbetet och baserat på resultatet av examensrapporten så utvärderades möjligheten att använda dem i ruttplanering. Metoder för att samla faktorer undersöktes, och två algoritmer testades som hade möjligheten att utnyttja nyckelfaktorerna. Dessa två algoritmerna visade förmågan att använda nyckelfaktorer samt potential i ruttplanering. Först så testades “Neural Evolution of Augmenting Topologies” algoritmen och dess egenskap att lösa enkla ruttplaneringsproblem verifierades. Dock så överträffades den senare av en genetisk algoritm, som kunde lösa punkt-till-punkt planering bättre men också visade sin användbarhet i handelsresandeproblemet.
Under examensarbetet så skapades ingen helhetslösning för att optimera ruttplanering. Dock så kunde många slutsatser dras under examensarbetets gång, såsom att det kan vara gynnsamt att träna neuronnät med övervakad inlärning för att beräkna kostnader av bågar, samt att genetiska algoritmer visar potential i fler-stop ruttplanering. Vi tror att flera av de slutsatserna som har gjorts i denna examensrapport kan bidra till att förbättra ruttoptimering om tillräckligt mycket resurser läggs på att undersöka dem (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9050694
- author
- Reis, André LU and Nordqvist, Sebastian LU
- supervisor
- organization
- alternative title
- Användning av AI i ruttplanering för varulastbilar inom försörjningskedjan
- course
- EITL05 20211
- year
- 2021
- type
- M2 - Bachelor Degree
- subject
- keywords
- Route optimization, Route planning, NEAT, Genetic algorithm, Key factors, Load planning, Machine learning.
- report number
- LU/LTH-EIT 2021-818
- language
- English
- id
- 9050694
- date added to LUP
- 2021-06-15 11:06:51
- date last changed
- 2021-06-15 11:06:51
@misc{9050694,
abstract = {{The supply chain has potential for growth. Many different parts can be optimized, and every possible improvement has not yet been tested. This study focuses on route optimization with the specific goal of figuring out how machine learning can be applied to route planning and how key factors that impact travel time for a route can be taken into account for this problem.
Time was dedicated to learning about machine learning, how it is applicable to route planning, as well as potential key factors that can be used with different machine learning algorithms. Once enough knowledge had been gathered, a prototype was implemented to verify key factors usability in route planning and test different route planning problems, such as point-to-point routes and traveling salesman problem.
Key factors were gathered during the thesis work, and based on the result of the thesis, their ability to be used in route optimization was verified. Methods of collecting the key factors were looked into, and two algorithms were tested that had the potential of using these factors. The two algorithms proved the usability of key factors and showed their potential in route planning problems. First, the “Neural Evolution of Augmenting Topologies” algorithm was tested and verified that it could solve simple route planning problems. Although, it was later overshadowed by a genetic algorithm solution, which could solve point-to-point travel better and showed usefulness in the traveling salesman problem.
The thesis work did not provide a full-scale solution to optimizing route planning. However, several conclusions were made on the topic, such as the possibility of training neural networks using supervised learning to calculate edge cost and genetic algorithms showing its potential in multi-stop route planning. We believe that several of the conclusions made in the thesis could show promise in the area of route optimization given enough resources.}},
author = {{Reis, André and Nordqvist, Sebastian}},
language = {{eng}},
note = {{Student Paper}},
title = {{AI utilization in route planning for delivery trucks within the supply chain}},
year = {{2021}},
}