Accession Number : ADA319843

Title :   Network Design Under Budget Constraints With Application To The Railroad Blocking Problem.

Descriptive Note : Master's thesis,

Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH

Personal Author(s) : Newton, Harry N.

PDF Url : ADA319843

Report Date : 09 JAN 1997

Pagination or Media Count : 117

Abstract : We develop a column generation based, branch-and-bound algorithm for the directed network budget design problem (BDP), also known as the optimal network design problem, when additional budget constraints are placed on some nodes. Our pricing sub-problems identify new paths for the commodities using a shortest path algorithm. We model the railroad blocking problem (RBP) as a BDP with constraints on the capacities at the nodes and restrictions on the legal paths for each commodity. In RBP, the physical rail network (the railroad terminals and tracks) is already defined. The "blocking network" to be constructed is a virtual network that is overlayed on the physical network. The blocks are virtual "express" arcs which a commodity may take to have uninterrupted service between two terminals that are not necessarily connected by a physical link. Solving RBP requires specifying the blocking network and assigning paths through the blocking network for each commodity. Our solution technique to RBP is unique in constraining the use of resources at the nodes and allowing multiple priority classes for the commodities. Computational results for our algorithm show solutions Within 2.3% of a known lower bound for a real-world RBP instance (with 150 nodes, 1300 commodities, and up to 6,800 candidate arcs after preprocessing) for a large domestic railroad and within 5.5% for randomly generated instances of the same size.

Descriptors :   *RAILROADS, *SYSTEMS ENGINEERING, *PROBLEM SOLVING, *TOPOLOGY, *BLOCKING, *COMPUTER NETWORKS, ALGORITHMS, OPTIMIZATION, COMPUTATIONS, PHYSICAL PROPERTIES, RAILS, PATHS, NODES, SOLUTIONS(GENERAL), LIMITATIONS, RESOURCES, BUDGETS, DOMESTIC, LAW ENFORCEMENT, COMMODITIES, TERMINALS.

Subject Categories : Administration and Management
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE