论文标题
一个自组织的极端塔布搜索算法，用于扩展的固定电荷网络问题
A Self-Organizing Extreme-Point Tabu-Search Algorithm for Fixed Charge Network Problems with Extensions
论文作者
论文摘要
我们提出了一种基于Glover（1994）中提出的基于幽灵图像（GI）过程的固定电荷网络流问题的新自组织算法，并适用于Glover，Amini和Kochenberger（2005）中的固定充电运输问题。我们的自组织GI算法迭代修改了在参数幽灵图像中体现的问题的理想化表示，从而可以使用在参数GI上运行的原始网络流量算法执行所有步骤。计算测试是在一组广泛的基准问题上进行的，其中包括文献中以前最大的集合，将我们的算法与先前针对固定充电运输问题提出的最佳方法进行了比较，尽管我们的算法并不专门针对此类。我们还提供了与CPLEX 12.8的其他更通用的固定电荷网络流问题进行比较，以证明新的自组织GI算法在大型问题实例上是有效的，找到具有统计上等效目标值的解决方案至少快700倍。当前的GI/TS实施产生的有吸引力的结果为我们有效地解决固定成本网络问题的能力有了重大的进步，并邀请其用于来自各种应用程序域的更大实例。
We propose a new self-organizing 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, Amini and Kochenberger (2005). Our self-organizing GI algorithm iteratively modifies an idealized representation of the problem embodied in a parametric ghost image, enabling all steps to be performed with a primal network flow algorithm operating on the parametric GI. Computational tests are carried out on an extensive set of benchmark problems which includes the previous largest set in the literature, comparing our algorithm to the best methods previously proposed for fixed-charge transportation problems, though our algorithm is not specialized to this class. We also provide comparisons for additional more general fixed-charge network flow problems against Cplex 12.8 to demonstrate that the new self-organizing GI algorithm 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.
