algorithms and computer programs in deterministic network optimization applied to public systems

摘要

abstract: this book reports on the state of the art in application of deterministic network optimization to public systems. after general remarks on problems of applying mathematical methods to decision problems in public systems in chapter 1, the fundamental definitions for graphs and networks are presented in chapter 2. in chapter 3 the network flow problems are discussed: after presenting algorithms for the well known shortest path and maximum flow problem, the traffic assignment problem is discussed. in case of constant arc costs a minimum cost flow algorithm is presented. for the general case of arc costs, depending on the arc flow together with multiple origin-destination flow, a new algorithmic approach is presented that is based onklein's minimum cost flow algorithm. the relationships between descriptive and normative assignment are shown. chapter 4 deals with algorithms to find optimal subnetwork on a given network for the following problems: optimal waste water canal systemand optimal filter plant location to minimize construction and operating costs optimal location of emergency service facilities to minimize number of locations; optimal routes for airplanes to maximize number of people who fly non-stop from their origin to their destination; optimal spanning tree for an offshore oil-pipeline system to minimize construction and operating costs; optimal investment into a rail network to maximize transportation time reduction and optimal investment into a road network. knowing the optimal network, it might also be of interest how this network should be constructed sequentially. in chapter 5 an algorithm for finding the optimal construction sequence of a waste water canal network is presented which maximizes the amount of purified water during construction period. the similar problem in case of a railway network is treated too. chapter 6 deals with the problem of finding routes with minimum length that either pass through all arcs (chinese postman problem) or pass through all vertices (travelling salesman problem). in case the routes may not exceed a given length different heuristic algorithms are proposed. the applications to street cleaning, garbage collection as well as school bus routing are discussed. in the final chapter 7 the problem of computing optimal routes for an urban public transportation system is discussed in detail, stating a new algorithm for solving it . to most of the presented algorithms computer programs are listed which are able to solve small up to medium sized problems.;