An extreme‐point tabu‐search algorithm for fixed‐charge network problems. Issue 2 (19th January 2021)

• Record Type: Journal Article
• Authors: Barr, Richard S.; Glover, Fred; Huskinson, Toby; Kochenberger, Gary
• Is Part Of: Networks. Volume 77:Issue 2(2021)
• Page Start: 322
• Page End: 340
• Publication Date: 2021-01-19
• Subjects: combinatorial optimization -- discrete optimization -- fixed‐charge networks -- heuristics -- mixed‐integer optimization -- network optimization -- nonconvex optimization -- tabu search; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22020
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: We propose a new algorithm for fixed‐charge network flow problems based on ghost image (GI) processes as proposed in Glover (1994) and adapted to fixed‐charge transportation problems in Glover et al. (2005). Our GI algorithm iteratively modifies an idealized representation of the problem embodied in a parametric GI, enabling all steps to be performed with a primal network flow algorithm operating on the parametric GI. Computational testing is carried out on well‐known problems from the literature plus a new set of large‐scale fixed‐charge transportation and transshipment network instances. We also provide comparisons against CPLEX 12.8 and demonstrate that the new GI algorithm with tabu search (TS) is effective on large problem instances, finding solutions with statistically equivalent objective values at least 700 times faster. The attractive outcomes produced by the current GI/TS implementation provide a significant advance in our ability to solve fixed‐cost network problems efficiently and invites its use for larger instances from a variety of application domains.