Relay Network Design in Logistics and Telecommunications: Models and Solution Approaches

Strategic network design has significant impacts on the operational performance of transportation and telecommunications industries. The corresponding networks are typically characterized by a multicommodity ow structure where a commodity is defined by a unique origin-destination pair and an associated amount of ow. In turn, multicommodity network design and hub location models are commonly employed when designing strategic networks in transportation and telecommunications applications. In this dissertation, these two modeling approaches are integrated and generalized to address important requirements in network design for truckload transportation and long-distance telecommunications networks. To this end, we first introduce a cost effective relay network design model and then extend this base model to address the specific characteristics of these applications. The base model determines relay point (RP) locations where the commodities are relayed from their origins to destinations. In doing this, we explicitly consider distance constraints for the RP-RP and nonRPRP linkages. In truckload transportation, a relay network (RP-network) can be utilized to decrease drivers' driving distances and keep them within their domiciles. This can potentially help alleviate the high driver turnover problem. In this case, the percentage circuitry, load-imbalance, and link-imbalance constraints are incorporated into the base model to control related performance metrics that are affected by the distance constraints. When compared to the networks from other modeling approaches, the RP-network is more effective in controlling drivers' tour lengths and capable of controlling the empty mileage to low levels without adding a large amount of additional travel distance. In telecommunications, an RP-network can be beneficial in long-distance data transfers where the signals' delity must be improved/regenerated at RPs along their travel paths. For this setting, we extend the base model to include fixed link setup costs and capacities. From our computational results, our models provide better network configuration that is cost effective and facilitates a better service quality (shorter delays and better connectivity). Concerning methodology, we develop effcient exact solution algorithms based on Benders decomposition, Lagrangean decomposition, and Lagrangean relaxation. The performance of the typical solution frameworks are enhanced via numerous accelerating techniques to allow the solution of large-sized instances in reduced solution times. The accelerating techniques and solution approaches are transferable to other network design problem settings with similar characteristics.