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
Engineering Management, Information, and Systems
Advisor
Richard Barr
Second Advisor
Michael Hahsler
Third Advisor
Richard Helgason
Fourth Advisor
Eli Olinick
Fifth Advisor
Halit Uster
Number of Pages
153
Format
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial 4.0 License
Recommended Citation
Leskovskaya, Angelika, "Extreme-point Tabu Search Heuristics for Fixed-charge Generalized Network Problems" (2019). Operations Research and Engineering Management Theses and Dissertations. 5.
https://scholar.smu.edu/engineering_managment_etds/5
