Change search
ReferencesLink to record
Permanent link

Direct link
Exact Optimization Methods for the Mixed Capacitated General Routing Problem
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Mathematical Sciences.
2013 (English)MasteroppgaveStudent thesis
Abstract [en]

This thesis is about using exact optimization algorithms to solve the routing problem known as the Mixed Capacitated General Arc Routing Problem (MCGRP) that is a generalization of many other well known routing problems. The Mixed Capacitated Routing Problem is a routing problem generalized by many other routing problems. The goal is to find a an optimal set of routes servicing a set of required entities on a mixed network. The entities being vertices, directed arcs or undirected edges. The mathematical programming model formulation developed by this thesis is a novel path flow formulation inspired by another well known routing problem by Letchford and Oukil (2011). The solution method is based on the exact optimization techniques Column Generation and Branch & Price. The algorithm is implemented in the C# and using the the BCL XPRESS libraries. A comparison has been given to the results by an exact algorithm by Bosco et al. (2012) as well as the currently best results known in the literature. The algorithm has been tested on 158 benchmark instances, were 83 of them were solved to optimum and 14 for the very first time. The algorithm is in addition an excellent lower bounding algorithm giving 58 improved lower bounds for previously unsolved instances. There is still a lot of research that can be done on the MCGRP and we hope that this thesis will motivate further research.

Place, publisher, year, edition, pages
Institutt for matematiske fag , 2013. , 82 p.
URN: urn:nbn:no:ntnu:diva-22695Local ID: ntnudaim:10008OAI: diva2:651454
Available from: 2013-09-25 Created: 2013-09-25 Last updated: 2013-09-25Bibliographically approved

Open Access in DiVA

fulltext(2453 kB)481 downloads
File information
File name FULLTEXT01.pdfFile size 2453 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(184 kB)18 downloads
File information
File name COVER01.pdfFile size 184 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Mathematical Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 481 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: 62 hits
ReferencesLink to record
Permanent link

Direct link