To access the full text documents, please follow this link: http://hdl.handle.net/2117/171071
dc.contributor | Keiō Gijuku Daigaku |
---|---|
dc.contributor | Daimon, Tatsuru |
dc.contributor.author | Ollé Navarro, Ricard |
dc.date | 2018 |
dc.identifier.uri | http://hdl.handle.net/2117/171071 |
dc.description.abstract | This thesis introduces a new approximate approach to solve the Generalized Vehicle Routing Problem (GVRP). In this variant of the well-known classical Vehicle Routing Problem (VRP), the customers are grouped into clusters and only one customer is visited from each cluster. It has many real-world logistic applications so it provides a useful modelling framework. Its complexity requests the use of metaheuristics or other approximate solution methods rather than exact models to provide satisfactory results in reasonable computational times. The present approach builds upon a previously developed Simulated Annealing (SA) metaheuristic based on a string model as a solution representation method, that is a one-dimensional data structure which expresses the visiting order of the vehicles routes. Hence, the new algorithm proposes to use the same string model but this time with another metaheuristic, the Tabu Search (TS). Thus, it is intended to determine which metaheuristic can provide better outcomes under the same conditions. Both algorithms are implemented in C++ programming language and computational results are presented for the same set of benchmark instances so that conclusions can be drawn. Accuracy, flexibility, robustness and speed are evaluated to demonstrate the effectiveness of both approaches with their strengths and weaknesses. |
dc.description.abstract | Outgoing |
dc.language.iso | eng |
dc.publisher | Universitat Politècnica de Catalunya |
dc.rights | info:eu-repo/semantics/openAccess |
dc.subject | Àrees temàtiques de la UPC::Informàtica::Aplicacions de la informàtica |
dc.subject | Electronic data processing |
dc.subject | Computer science |
dc.subject | Vehicle Routing Problem; Generalized Vehicle Routing Problem; Tabu Search; String Model; metaheuristics |
dc.subject | Informàtica |
dc.title | Tabu search algorithm based on a string data model to solve the GVRP |
dc.type | info:eu-repo/semantics/masterThesis |