Exact Optimization Methods for the Mixed Capacitated General Routing Problem
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.
IdentifiersURN: urn:nbn:no:ntnu:diva-22695Local ID: ntnudaim:10008OAI: oai:DiVA.org:ntnu-22695DiVA: diva2:651454
Eidsvik, Jo, Førsteamanuensis