| This dissertation is focused on network optimization problems in the planning, analyzing and optimizing of large scale (air) transportation networks with time window constrained routing and scheduling. The motivation for the research comes from the problems encountered in the Strategic Mobility Analysis of the United States military in general, and the Mobility Analysis Support System of the Air Mobility Command, USAF in particular.;In this dissertation, a new mobility analysis model named NETO is proposed to address various limitations of the existing ones. The new model consists of a network optimization engine with time window constrained routing and scheduling that is based on integer and combinatorial optimization methodology, and an analysis system with a Management Information System that is built upon RDBMS and multimedia technology.;The network optimization engine is dealt with as Pickup-delivery Vehicle Routing and Scheduling Problem with Time-Window Constraint(PDPTW), solved by a set-partitioning formulation, column generation and column elimination algorithm(SP-CGCE). The subproblem of the column generation is a Constrained Shortest Path Problem with pairing, precedence, capacity, and time windows constraints and is solved by Dynamic Programming. The computational results indicate a promising and robust performance of the solution algorithm, especially the column elimination technique. The sizes of the problems tested/solved here are larger than what can be found in the literature. In general, the test results indicate that the SP-CGCE algorithm is expected to be at least twice as fast as currently available column generation-branch and bound schemes because of the effectiveness of the column elimination process.;NETO has three distinguishing features: (1) Offering an optimal solution; (2) Addressing both the forward problem and the backward problem; (3) Flexibility, Extendibility and Efficiency. To the best of the author's knowledge, this dissertation is the first research done using the column generation-column elimination scheme to solve PDPTW problems, as well as VRP and VRPTW problems; and it is also the first attempt to model and solve the mobility analysis system using network optimization with time window constrained routing and scheduling. |
