Wøhlk og Søn

Contents of my Master's Thesis

Preface
Summery (English)
Resumé (Dansk)
1. Introduction
2. Notation and Definitions
3. The Euler Tour Problem
4. The Chinese Postman Problem
5. The Capacitated Arc Routing Problem
   5.1 Mathematical Models
      5.1.1 Model with Directed Variables
      5.1.2 Model with Undirected Variables
6. Applications of CARP
   6.1 Mail Delivery
   6.2 Refuse Collection
   6.3 Service of the road network
      6.3.1 Street Sweeping
      6.3.2 Winter Gritting
      6.3.3 Snow Removal
7. Transformations
   7.1 Different Arc Routing Problems
   7.2 Different Node Routing Problems
   7.3 Equivalence of VRP and CARP
   7.3 Equivalence of TSP and RPP
8. Complexity
   8.1 Complexity of CARP
   8.2 Complexity of Other Routing Problems
   8.3 Approximation
   8.4 Special Cases
   9. Lover Bounds
   9.1 Some extra Notation
   9.2 Matching - Node Scanning Lower Bound
      9.2.1 Matching Lower Bound (MLB)
      9.2.2 Node Scanning Lower Bound (NSLB)
      9.2.3 The MNSLB procedure
   9.3 LB1 and LB2
      9.3.1 LB1
      9.3.1 LB2
   9.4 Implementation of Lower Bounds
10. Heuristics for solving CARP
   10.1 Implemantation of Heuristics
   10.2 Displaying Solutions
   10.3 Path-Scanning and Rand Path-Scanning
      10.3.1 Illustration of Path-Scanning
      10.3.2 Implementation of Path-Scanning
   10.4 Argument-Merge
      10.4.1 Illustration of Argument-Merge
      10.4.2 Implementation of Argument-Merge
   10.5 Argument-Insert
      10.5.1 Illustration of Argument-Insert
      10.5.2 Implementation of Argument-Insert
11. Computational Results
12. Conclusion