Title page for ETD etd-6998-153234


Type of Document Dissertation
Author Park, Taehyung
Author's Email Address tpark@vt.edu
URN etd-6998-153234
Title Network Design and Analysis Problems in Telecommunication, Location-Allocation, and Intelligent Transportation Systems
Degree PhD
Department Industrial and Systems Engineering
Advisory Committee
Advisor Name Title
Sherali, Hanif D. Committee Chair
Jacobson, Sheldon H. Committee Member
Lee, Youngho Committee Member
Sarin, Subhash C. Committee Member
Trani, Antonio A. Committee Member
Keywords
  • Dynamic Origin-Destination Trip Table Estimation
  • Mathematical Programming
  • Telecommunication Networks
  • Reformulation-Linearization Technique
  • Equal-capacity p-median problem
Date of Defense 1998-06-22
Availability unrestricted
Abstract
This research is concerned with the development of algorithmic approaches for solving

problems that arise in the design and analysis of telecommunication networks, location-allocation distribution contexts, and intelligent transportation networks. Specifically, the corresponding problems addressed in these areas are a local access and transport area (LATA) network design problem, the discrete equal-capacity p-median problem (PMED), and the estimation of dynamic origin-destination path ows or trip tables in a general network.

For the LATA network problem, we develop a model and apply the Reformulation-Linearization Technique (RLT) to construct various enhanced tightened versions of the proposed model. We also design efficient Lagrangian dual schemes for solving the linear programming relaxation of the various enhanced models, and construct an effective heuristic procedure for deriving good quality solutions in this process. Extensive computational results are provided to demonstrate the progressive tightness resulting from the enhanced formulations and their effect on providing good quality feasible solutions. The results indicate that the proposed procedures typically yield solutions having an optimality gap of less than 2% with respect to the derived lower bound, within a reasonable effort that involves the solution of a single linear program.

For the discrete equal-capacity p-median problem, we develop various valid inequalities, a separation routine for generating cutting planes via specific members of such inequalities, as well as an enhanced reformulation that constructs a partial convex hull representation that subsumes an entire class of valid inequalities via its linear programming relaxation. We also propose suitable heuristic schemes for solving this problem, based on sequentially rounding the continuous relaxation solutions obtained for the various equivalent formulations of the problem. Extensive computational results are provided to demonstrate the effectiveness of the proposed valid inequalities, enhanced formulations, and heuristic schemes. The results indicate that the proposed schemes for tightening the underlying relaxations play a significant role in enhancing the performance of both exact and heuristic solution methods for solving this class of problems.

For the estimation of dynamic path ows in a general network, we propose a parametric optimization approach to estimate time-dependent path ows, or origin-destination trip tables, using available data on link traffic volumes for a general road network. Our model assumes knowledge of certain time-dependent link ow contribution factors that are a dynamic generalization of the path-link incidence matrix for the static case. We propose a column generation approach that uses a sequence of dynamic shortest path subproblems in order to solve this problem. Computational results are presented on several variants of two sample test networks from the literature. These results indicate the viability of the proposed approach for use in an on-line mode in practice.

Finally, we present a summary of our developments and results, and offer several related recommendations for future research.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  ETD.PDF 714.10 Kb 00:03:18 00:01:42 00:01:29 00:00:44 00:00:03

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.