Exact Optimization Methods for the Mixed Capacitated General Routing Problem

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.