Change search
ReferencesLink to record
Permanent link

Direct link
Solving the Vehicle Routing Problem: using Search-based Methods and PDDL
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2013 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

In this project the optimization of transport planning has been studied. The approach was that smaller transport companies do not have the capability to fully optimize their transports. Their transport optimization is performed at a company level, meaning that the end result might be optimal for their company, but that potential for further optimization exists.

The idea was to build a collaboration of transport companies, and then to optimize the transports globally within the collaboration. The intent was for the collaboration to perform the same driving assignments but at a lower cost, by using fewer vehicles and drivers, or travel shorter distance, or both combined. This should be achieved by planning the assignments in a smarter way, for example using a company's empty return journey to perform an assignment for another company.

Due to the complexity of these types of problems, called Vehicle Routing Problem (VRP), shown to be NP-complete, search methods are often used. In this project the method of choice was a PDDL-based planner called LPG-td. It uses enforced hill-climbing together with a best-first search to find feasible solutions. The method was tested for scaling, performance versus another method and against time, as well as together with a real-life based problem.

The results showed that LPG-td might not be a suitable candidate to solve the problem considered in this project. The solutions found for the collaboration were worse than for the sum of individual solutions, and used more computational time. Since the solution for the collaboration at most should be equal to the sum of individual solutions, in theory, this meant that the planner failed.

Place, publisher, year, edition, pages
2013. , 71 p.
UPTEC F, ISSN 1401-5757 ; 13018
Keyword [en]
vehicle routing problem, PDDL, search-based methods
National Category
Engineering and Technology
URN: urn:nbn:se:uu:diva-202239OAI: diva2:631516
External cooperation
Scania CV
Educational program
Master Programme in Engineering Physics
Available from: 2013-07-04 Created: 2013-06-20 Last updated: 2013-07-04Bibliographically approved

Open Access in DiVA

fulltext(1012 kB)2344 downloads
File information
File name FULLTEXT02.pdfFile size 1012 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 2344 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 854 hits
ReferencesLink to record
Permanent link

Direct link