Network Design and Analysis Problems in Telecommunication, Location-Allocation, and Intelligent Transportation Systems - PDF

Please download to get full document.

View again

of 38
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Pets & Animals

Published:

Views: 6 | Pages: 38

Extension: PDF | Download: 0

Share
Related documents
Description
Network Design and Analysis Problems in Telecommunication, Location-Allocation, and Intelligent Transportation Systems Taehyung Park Dissertation submitted to the Faculty of the Virginia Polytechnic Institute
Transcript
Network Design and Analysis Problems in Telecommunication, Location-Allocation, and Intelligent Transportation Systems Taehyung Park Dissertation submitted to the Faculty of the Virginia Polytechnic Institute and State University in the partial fulfillment of the requirements for the degree of Doctor of Philosophy in Industrial and Systems Engineering Hanif D. Sherali, Chair Sheldon H. Jacobson Youngho Lee Subhash C. Sarin Antonio A. Trani June 22, 1998 Blacksburg, Virginia Copyright 1998, Taehyung Park Network Design and Analysis Problems in Telecommunication, Location-Allocation, and Intelligent Transportation Systems by Taehyung Park (ABSTRACT) This research is concerned with the development of algorithmic approaches for solving problems that arise in the design and analysis of telecommunication networks, locationallocation 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 flows 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 flows in a general network, we propose a parametric optimization approach to estimate time-dependent path flows, 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 flow 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 iii proposed approach for use in an off-line mode in practice. Finally, we present a summary of our developments and results, and offer several related recommendations for future research. iv Acknowledgments I would like to thank my advisor, Dr. Hanif D. Sherali, for his patience and guidance at each stage of this work. Without his support, this dissertation would not have been completed. I would also like to thank Dr. Sheldon H. Jacobson, Dr. Youngho Lee, Dr. Subhash C. Sarin, and Dr. Antonio A. Trani for serving on the dissertation committee and for their helpful suggestions. Special thanks go to my previous teachers, including Dr. Sheung-Kown Kim and Dr. Seong-in Kim at Korea University, for their support and encouragement. I could not thank enough my parents and my brother s family for their love and faith in me. Finally, I wish to thank my beloved wife, Hyekyung, and children, Junwoo and Junseong, for their support and inspiration. v Contents 1 Introduction 1 2 Background and Literature Review Hierarchical Structure of a LATA Network Previous Research on Designing Telecommunication Networks Discrete Equal Capacity p-median Problem Dynamic Origin-Destination Trip Table Estimation Problem Reformulation-Linearization Technique Local Access and Transport Area Network Problem Formulation of a LATA Network Design Problem Valid Inequalities Enhanced Model Representations via a Reformulation-Linearization Technique 37 i 3.4 Lagrangian Relaxation - Deflected Subgradient Approach Alternative Reformulations of Problem CFE A Primal Heuristic Discrete Equal-Capacity p-median Problem Valid Inequalities and Construction of Enhanced Reformulations Deriving a Heuristic Solution Enhanced Model Representation via a Reformulation-Linearization Technique 71 5 Estimation of Dynamic Path Flows in a General Network Constrained Least Squares Model Projected Conjugate Gradient Solution Scheme Overall Path/Column Generation Algorithm Computational Results Computational Results for the LATA Network Problem Problems LAN and CFE Generation of Additional Test Cases of LAN and CFE Computational Results for the Primal Heuristic ii 6.2 Computational Results for the Discrete Equal-Capacity p-median Problem Computational Results for the Dynamic O-D Trip Tables Estimation Algorithm Simulated Test Problem Massachusetts Turnpike Test Problem Summary, Conclusions, and Recommendations for Future Research 123 Bibliography 130 Vita 140 iii List of Figures 2.1 LATA networks in Virginia Switched access traffic structure Special access traffic structure Typical route of a local loop Cost structure of the model Feasible region in the aggregate (x, y) space Facet of conv(r) in( x, ỹ) space Flow chart for a separation routine to generate a cut (4.22) Corridor network iv List of Tables 6.1 Comparison of LAN and CFE using various e(t) functions Comparison of LAN and CFE using e(t) = 12323t Comparison for various RLT relaxations for Problems 1-30 of Table Comparison for various RLT relaxations for Problems 1-30 of Table 6.1 (continued) Comparison for various RLT relaxations for Problems of Table Comparison for various RLT relaxations for Problems of Table 6.2 (continued) Additional test runs using p-median type problems Results for the primal heuristic based on solving the Lagrangian dual to Problem RLT(CFE) Evaluation of the various relaxations v 6.7 Evaluation of the various relaxations (continued) Evaluation of the heuristic procedures Evaluation of the heuristic procedures (continued) Comparison of methods for deriving exact solutions via CPLEX-MIP Comparison of methods for deriving exact solutions via CPLEX-MIP (continued) Computational results for the simulated test problem using an arbitrary start Effect of µ on the results for the simulated test problem using an arbitrary start Experiment using different historical and actual link delay functions Computational Results for the Massachusetts Turnpike Example Computational Results for the Massachusetts Turnpike Example (continued) Computational Results for the Massachusetts Turnpike Example using modified P kpr lh Computational Results for the Massachusetts Turnpike Example using modified P kpr lh (continued) vi Chapter 1 Introduction This dissertation is concerned with a class of decision problems that arise in the design of telecommunication networks, location of facilities on distribution networks, and the analysis of intelligent transportation system (ITS). The first problem addresses the determination of the location and the capacity of hub facilities in a telecommunication network along with the design of a set of clusters of central offices (CO) for which the demand for communication is specified can be clustered in a manner such that each cluster has one hub to which the associated central offices are connected. The demand signal from each central office would then be sent to the hub facility where it would be aggregated and multiplexed, then transmitted to the required location through high capacity fiber optic cables. This problem arises in the context of providing a special access service provided by a local exchange company (LEC). Compared with previous research on the hub (or concentrator) location problem, this model offers additional features that permit each central office to be connected 1 Chapter 1. Introduction 2 either to a hub or to a Point of Presence (POP) node on a Local Access and Transport Area (LATA) network. Also, the total cost of installing hubs includes general nonlinear cost functions that exhibit economies of scale, and the capacity of each hub is represented as integer multiples of a standard unit capacity. Related with the first problem is a discrete equal-capacity p-median problem. This problem seeks the location of exactly p facilities having equal capacities in a network, such that the specified demand at each of the nodes is satisfied. The structure of this problem admits poor linear programming relaxations, leading to difficult and challenging problem instances. Hence, we devise improved formulations of this problem which possess tighter linear programming relaxations. Also, this problem is a generalization of a capacitated facility location problem and belongs to the class of location-allocation problems. This class of problems seeks to determine the number, location, and capacities of facilities to be located on a given region or network so as to minimize the total location and distribution costs (see Cooper, 1964, Francis et al., 1992, and Sherali and Adams, 1984). Moreover, if we fix the number of multiplexers to be constructed in the LATA network design problem to p and suitably modify its cost structure, the resulting problem turns out to be a special case of this p-median location problem. The third decision problem considered herein is to estimate the time-varying path flows based on information regarding dynamic link flows on a general network. Time-dependent origin-destination (OD) trip tables are accordingly obtained by adding the path flows corresponding to the same origin-destination pairs for each time interval. The estimation of Chapter 1. Introduction 3 dynamic OD trip tables is important in the management of traffic networks and in particular, in dynamic traffic assignment models in the context of Advanced Traveller Information Systems (ATIS). The OD trip table information can be used in controlling the traffic flow entering ramps, or in the diversion of traffic flow in the event of an accident. This estimation problem is a generalization of previous research effort concerned with estimating OD trip tables for the corridor case (for which there is a unique path for each OD pair) and for static networks. The principal modeling issue of relevance here is the representation of the dynamic relationships between the path flows and link flows on a general network. For general 0-1 mixed-integer linear (or polynomial) programming problems, including the first two classes of problems considered in this research effort, the Reformulation- Linearization Technique (RLT) generates a hierarchy of equivalent formulations leading ultimately to the convex hull representation of the original feasible solution set (see Sherali and Adams, 1990, 1994, and Sherali et al., 1996). Thus, applying RLT ingeniously, we can design effective enhanced model reformulations that possess tighter linear programming relaxations. Using this tool along with suitable relaxation and restriction strategies, our research effort in this dissertation focuses on both modeling as well as algorithmic issues related to the various classes of problems addressed herein. The remainder of this dissertation is organized as follows. In Chapter 2, we introduce relevant background material and discuss previous research on designing telecommunication networks, on location-allocation problems, including the discrete equal-capacity p-median problem, and on Origin-Destination (OD) trip table estimation problems for transportation Chapter 1. Introduction 4 networks. In Chapter 3, we develop a model for the telecommunication network design problem considered herein, and apply the 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. In Chapter 4, we introduce a model for the discrete equal-capacity p-median problem and 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. In Chapter 5, we propose a parametric optimization approach to estimate time-dependent path flows, 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 flow 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. In Chapter 6, we present extensive computational experience on these three classes of problems. Finally, Chapter 7 presents a summary and conclusions, along with recommendations for future research. Chapter 2 Background and Literature Review In this chapter, we present a brief overview of the extensive literature on telecommunication network design problems, location-allocation problems including discrete equal-capacity p- median problem, and OD trip table estimation problems. In reviewing telecommunication network design problems, we first summarize the structure of a LATA network and then discuss related research. If the total number of multiplexers to be installed is pre-specified, then the discrete equal-capacity p-median problem can be used to determine the locations of hubs and the clustering of End Offices (EO). We briefly describe previous research on p-median problems and location-allocation problems. Next, we summarize the existing research on OD trip table estimation problems ranging from the static estimation problem to the time-varying general network problems. Finally, we discuss the basic elements of the Reformulation-Linearization Technique. 5 Chapter 2. Background and Literature Review Hierarchical Structure of a LATA Network The 1982 Modification of Final Judgement (MFJ) required AT&T to divest itself of the twenty-two Bell Operating Companies (BOCs). One of the consequences of the divestiture was that the nationwide Bell System network was divided into two components: a set of exchanges provided by the divested BOCs, and an inter-exchange facility provided by inter-exchange carriers (IXCs) such as AT&T, MCI, and Sprint. Prior to the divestiture, the term exchange area wasusedtodescribeanareainwhich there was a single, uniform set of charges imposed for telephone service. Calls between points in an exchange area were classified as local calls. The MFJ defines an exchange area, or exchange, to be generally equivalent to a Standard Metropolitan Statistical Area (SMSA), which is a geographic area defined by the United States government for statistical purposes. The MFJ concept is to group large segments of population having common social and economic interests within a single exchange. The territory served by the Bell System has been divided into 163 of these exchanges which are also referred to as local access and transport areas (LATAs). Figure 2.1 displays LATA networks managed by the Bell Atlantic Company in Virginia. Appendix B of the MFJ requires each BOC to offer equal access with respect to local exchanges in a LATA to all IXCs. Within each LATA, a Point of Presence (POP) node is designated by each inter-exchange carrier for the connection of its facilities with those of a local exchange carrier (LEC). Each IXC can have one POP node in each LATA, and the connection for each IXC should be identical in terms of type, price, and quality. The Chapter 2. Background and Literature Review 7 Figure 2.1: LATA networks in Virginia. Chapter 2. Background and Literature Review 8 E.O. Direct inter-lata connecting trunk E.O. Tandem connecting trunk A.T. Tandem inter-lata connecting trunk POP E.O. Figure 2.2: Switched access traffic structure. connection between a POP and an EO can have at most one intermediate switch. Thus, each EO can connect to the POP node either via a direct inter-lata connecting trunk group (DIC), or via a tandem inter-lata connecting trunk group (TIC). For facilitating interconnections, the LEC provides the IXCs switched-access service and special (non-switched) access service to the LATA networks through various imposed tariffs. A switched-access service is a physical connection that allows messages to pass through the switching equipment to the EO or Access Tandem (AT) where the control of calls, lines, and trunks is exercised. This service is used to transfer calls between LATAs, and is depicted in Figure 2.2. Chapter 2. Background and Literature Review 9 E.O. DS3 Transport 44.7Mb=28 DS1s Mux E.O. S.W.C. E.O. DS1 Transport 1.54Mb=24 voice lines IXC POP Channel Term S.W.C.: Serving Wire Center Figure 2.3: Special access traffic structure. Special access service is a dedicated flat-rate service that provides a connection between an end-user and an IXC, an end-user and an end-user, or an end-user and a broadband fast packet service. Special access service can be provided through a serving wire center (SWC) or routed through a hub where bridging or multiplexing functions are performed. It can be used for voice, data, or video transmission. The structure of a special access service is illustrated in Figure 2.3. In this figure, Mux denotes a multiplexer, DS1 (Digital Signal level 1) is a standard 24 channel pulse-code modulation (PCM) system (1.544 Mbps), and DS3 is a Mbps high capacity digital service. In the lower hierarchy of the switched-access network, local loop covers area from the cus- Chapter 2. Background and Literature Review 10 Customer Premises Allocation Area Distribution Network Feeder Routes Switching Center Lateral Cable Feeder Section Distribution Points Figure 2.4: Typical route of a local loop. tomer premise to a local switch office. Like the overall communication systems, a local loop is also hierarchical; it consists of three levels referred to as routes, feeder network, and distribution networks. Aroute is a portion of the local access network containing all customer nodes that communicate with the switching center via a common link incident to the center. Figure 2.4 illustrates the structure of a route in a local loop. Each switching office might serve as the termination point for three to five routes. Typically, each route is considered independently for capacity planning purposes.
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks