DESIGN AND APPLICATION OF SOLUTION METHODOLOGIES TO OPTIMIZE PROBLEMS IN TRANSPORTATION LOGISTICS (ALGORITHMS, INTEGERS, PROGRAMMING).

摘要

Optimization of operations in transportation logistics may often be mathematically modelled as 0-1 integer programs. As application problems are typically NP-hard, enumeration methods, which embed relaxation techniques such as Lagrangean relaxation, are employed. This thesis focuses on the design and application of solution methodologies to optimize certain combinatorial models that arise in transportation logistics. The solution methodologies considered include interactive optimization, Lagrangean decomposition, Lagrangean dual ascent, model strengthening with surrogate constraints, and branch and bound. The chief contributions of this thesis are to specialize and apply a subset of these modeling and algorithmic tools to optimally solve three NP-hard models.; An interactive optimization system is developed for a bulk cargo scheduling problem. A color graphics user interface enables a decision maker to develop and manage periodic schedules. The system was tested successfully on historical data obtained from the U.S. Navy.; Lagrangean decomposition, a special form of Lagrangean relaxation, is also studied. For the resource-constrained minimum weighted arborescence problem (RMWA), Lagrangean decomposition is empirically shown to generate bounds which significantly improve upon bounds obtained from a traditional Lagrangean relaxation.; Specialized Lagrangean dual ascent procedures are designed and tested for the generalized assignment problem (GAP) and RMWA. The ascent procedure designed for the GAP yields stronger bounds than a previous ascent procedure. The ascent algorithm for RMWA exploits a Lagrangean decomposition model structure.; Surrogate constraints are added to relaxed models of the GAP and RMWA. Bound improvement is achieved, in both cases, by exploiting a violation of a condition required for primal feasibility.; Specialized branch and bound rules are designed for enumeration algorithms that optimally solve the GAP and RMWA. The GAP enumeration algorithm achieves improved performance over previous algorithms due to improved methods of solving the Lagrangean dual and a sophisticated branch and bound scheme. The methodology solves problems up to five times the largest problems solved in existing literature. The enumeration algorithm for RMWA also employs a complex tree search and solves medium-size problem effectively.