Return to search

Heuristic Clustering Methods for Solving Vehicle Routing Problems

Vehicle Routing Problems are optimization problems centered around determining optimal travel routes for a fleet of vehicles to visit a set of nodes. Optimality is evaluated with regard to some desired quality of the solution, such as time-minimizing or cost-minimizing. There are many established solution methods which makes it meaningful to compare their performance. This thesis aims to investigate how the performances of various solution methods is affected by varying certain problem parameters. Problem characteristics such as the number of customers, vehicle capacity, and customer demand are investigated. The aim was approached by dividing the problem into two subproblems: distributing the nodes into suitable clusters, and finding the shortest route within each cluster. Results were produced by solving simulated sets of customers for different parameter values with different clustering methods, namely sweep, k-means and hierarchical clustering. Although the model required simplifications to facilitate the implementation, theresults provided some significant findings. The thesis concludes that for large vehicle capacity in relation to demand, sweep clustering is the preferred method. Whereas for smaller vehicles, the other two methods perform better.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-331116
Date January 2023
CreatorsNordqvist, Georgios, Forsberg, Erik
PublisherKTH, Skolan för teknikvetenskap (SCI)
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess
RelationTRITA-SCI-GRU ; 2023:161

Page generated in 0.0023 seconds