Beta 1


Title Disjoint paths in directed networks with length and distribution criteria
Author Rasmussen, Marie-Louise Højlund (Institut for Matematik, Danmarks Tekniske Universitet, DTU, DK-2800 Kgs. Lyngby, Denmark)
Supervisor Bendsøe, Martin P. (Department of Mathematics, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Britz, Thomas Johann (Department of Mathematics, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Stolpe, Mathias (Department of Mathematics, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2005
Abstract The main part of this thesis work is to develop a model for solving the problem of finding arc- or node disjoint paths with different length- and distribution criteria in directed networks. As one result, we present a fairly general mathematical model that can incorporate a multitude of criteria, and which is suitable for computations. The model applies to problems that can be modeled as directed networks and in which one wants to transport commodities of certain sizes from sources to terminals in this directed network. The transportation routes constitute connecting paths. Length criteria can be that connecting paths must equal, be less than, or greater than certain lengths, or they must have equal lengths or approximately equal lengths. The distribution criteria include defining where the connecting paths must begin and where they must end, defining forbidden areas, and defining mandatory areas. Other products of this thesis work are developed algorithms for eliminating occurrences of sub-tours in the solutions and solving large-scale programs. The large-scale programs are decomposed into several sub-programs that are solved separately. There are two kinds of decompositions: using separate regions or overlapping regions. Using overlapping- instead of separate regions gives more flexibility to the solutions. When using overlapping regions, both the number of regions and the size of the overlap decide the behavior of the decomposition algorithm. A last part of this thesis work is to implement and experiment upon the model and the developed algorithms. The level of difficulty of the problem of finding arc- or node disjoint paths with different length- and distribution criteria in directed networks depends on the posed criteria. Using stricter criteria makes the problem more difficult to solve. However, the decomposition algorithm is able to find solutions in most cases when choosing an appropriate number of regions and size of overlap.
Pages 86
Admin Creation date: 2006-06-22    Update date: 2007-02-24    Source: dtu    ID: 184710    Original MXD