• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • Fakultet for informasjonsteknologi og elektroteknikk (IE)
  • Institutt for matematiske fag
  • View Item
  •   Home
  • Fakultet for informasjonsteknologi og elektroteknikk (IE)
  • Institutt for matematiske fag
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Exact Optimization Methods for the Mixed Capacitated General Routing Problem

Gaze, Kevin Anders
Master thesis
Thumbnail
View/Open
651454_COVER01.pdf (184.2Kb)
651454_FULLTEXT01.pdf (2.395Mb)
URI
http://hdl.handle.net/11250/259209
Date
2013
Metadata
Show full item record
Collections
  • Institutt for matematiske fag [1454]
Abstract
This thesis is about using exact optimization algorithms to solve the routing problemknown as the Mixed Capacitated General Arc Routing Problem (MCGRP) that is a generalizationof many other well known routing problems. The Mixed Capacitated RoutingProblem is a routing problem generalized by many other routing problems. The goal is tofind a an optimal set of routes servicing a set of required entities on a mixed network. Theentities being vertices, directed arcs or undirected edges.The mathematical programming model formulation developed by this thesis is a novelpath flow formulation inspired by another well known routing problem by Letchford andOukil (2011). The solution method is based on the exact optimization techniques ColumnGeneration and Branch & Price.The algorithm is implemented in the C# and using the the BCL XPRESS libraries. Acomparison has been given to the results by an exact algorithm by Bosco et al. (2012) aswell as the currently best results known in the literature.The algorithm has been tested on 158 benchmark instances, were 83 of them were solvedto optimum and 14 for the very first time. The algorithm is in addition an excellent lowerbounding 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 thesiswill motivate further research.
Publisher
Institutt for matematiske fag

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit