Abstract

While researchers have studied generalized network flow problems extensively, the powerful addition of fixed charges on arcs has received scant attention. This work describes network-simplex-based algorithms that efficiently exploit the quasi-tree basis structure of the problem relaxations, proposes heuristics that utilize a candidate list, a tabu search with short and intermediate term memories to do the local search, a diversification approach to solve fixed-charge transportation problems, as well as a dynamic linearization of objective function extension for the transshipment fixed-charge generalized problems. Computational testings for both heuristics demonstrate their effectiveness in terms of speed and quality of solutions to these mixed-integer models. Comparisons with a state-of-the-art solver, CPLEX, show that the extreme-point search algorithm runs, on average, for transportation problems five orders of magnitude faster and produces integer solution values within 2.2% of the optimal solution reported by CPLEX; for transshipment problems, the heuristic solver ran 1,000 faster and the solution values were within 2.5% of the optimal reported by CPLEX.

Degree Date

Summer 8-6-2019

Document Type

Dissertation

Degree Name

Ph.D.

Department

EMIS

Advisor

Richard Barr

Second Advisor

Michael Hahsler

Third Advisor

Richard Helgason

Fourth Advisor

Eli Olinick

Fifth Advisor

Halit Uster

Number of Pages

153

Format

pdf

Creative Commons License

Creative Commons Attribution-Noncommercial 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial 4.0 License

Share

COinS