2020/07/13 by Richard S. Barr, Fred Glover, Barr, Richard S. +5
Decision Sciences · Engineering · Social Sciences · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Infrastructure Maintenance and Monitoring #Multi-Criteria Decision Making #Optimization and Control (math.OC) #Optimization and Mathematical Programming #Transportation Planning and Optimization
paper · pdf · doi:10.48550/arxiv.2007.06685
openalex publication_date 2020/07/13 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We propose a new self-organizing algorithm for fixed-charge network flow\nproblems based on ghost image (GI) processes as proposed in Glover (1994) and\nadapted to fixed-charge transportation problems in Glover, Amini and\nKochenberger (2005). Our self-organizing GI algorithm iteratively modifies an\nidealized representation of the problem embodied in a parametric ghost image,\nenabling all steps to be performed with a primal network flow algorithm\noperating on the parametric GI. Computational tests are carried out on an\nextensive set of benchmark problems which includes the previous largest set in\nthe literature, comparing our algorithm to the best methods previously proposed\nfor fixed-charge transportation problems, though our algorithm is not\nspecialized to this class. We also provide comparisons for additional more\ngeneral fixed-charge network flow problems against Cplex 12.8 to demonstrate\nthat the new self-organizing GI algorithm is effective on large problem\ninstances, finding solutions with statistically equivalent objective values at\nleast 700 times faster. The attractive outcomes produced by the current GI/TS\nimplementation provide a significant advance in our ability to solve fixed-cost\nnetwork problems efficiently and invites its use for larger instances from a\nvariety of application domains.\n