Optimization models and analysis of routing, location, distribution and design problems on networks

A variety of practical network optimization problems arising in the context of public supply and commercial transportation, emergency response and risk management, engineering design, and industrial planning are addressed in this study. The decisions to be made in these problems include the location of supply centers, the routing, allocation and scheduling of flow between supply and demand locations, and the design of links in the network. This study is concerned with the development of optimization models and the analysis of five such problems, and the subsequent design and testing of exact and heuristic algorithms for solving these various network optimization problems.;The first problem addressed is the time-dependent shortest pair of disjoint paths problem. We examine computational complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent.;Next, we examine a minimum-risk routing problem and pursue the development, analysis, and testing of a mathematical model for determining a route that attempts to reduce the risk of low probability-high consequence accidents related with the transportation of hazardous materials (hazmat).;The third problem deals with the development of a resource allocation strategy for emergency and risk management. An important and novel issue addressed in modeling this problem is the effect of loss in coverage due to the non-availability of emergency response vehicles that are currently serving certain primary incidents.;The fourth problem addressed in this study deals with the development of global optimization algorithms for designing a water distribution network, or expanding an already existing one, that satisfies specified flow demands at stated pressure head requirements.;The final problem addressed in this study is concerned with a global optimization approach for solving capacitated Euclidean distance multifacility location-allocation problems, as well as the development of a new algorithm for solving the generalized lp distance location-allocation problem. Among the problems solved, for the only two test instances previously available in the literature for the Euclidean distance case that were posed in 1979, we report proven global optimal solutions within a tolerance of 0. 1% for the first time.* (Abstract shortened by UMI.);*Originally published in DAI Vol. 60, No. 4. Reprinted here with corrected title and abstract.