Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP
Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP
复制标题
算法 754：使用 GRASP 近似求解密集二次分配问题的 Fortran 子例程
DOI：
10.1145/225545.225553
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Yong Li
中科院分区：
文献类型：
--
作者：
M. G. Resende;P. Pardalos;Yong Li
在NP-完全二次分配问题（QAP）中，<italic>n个</italic>设备被分配到<italic>n个</italic>站点，以最小的成本。将设施<italic>i</italic>分配给站点<italic>k</italic>并将设施<italic>j分配</italic>给站点<italic>l</italic>对总成本的贡献为<italic>f<subscrpt>ij</subscrpt></italic><italic>d<subscrpt>kl</subscrpt></italic>，其中<italic>f<subscrpt>ij</subscrpt></italic>是设施<italic>i</italic>和<italic>j</italic>之间的流量，<italic>d<subscrpt>kl</subscrpt></italic>是站点<italic>k</italic>和<italic>l</italic>之间的距离。只有非常小的（<italic>n</italic>≤20）的QAP的情况下，已被准确地解决了，因此，算法被用来产生近似的解决方案。本文描述了一组Fortran子程序，用于找到至少有一个对称流或距离矩阵的稠密二次分配问题的近似解。一个贪婪的，随机的，自适应搜索过程（GRASP）是用来产生的解决方案。详细描述了代码的设计和实现，并报告了大量的计算实验，说明了作为运行时间的函数的解决方案质量。
In the NP-complete quadratic assignment problem (QAP), <italic>n</italic> facilities are to be assigned to <italic>n</italic> sites at minimum cost. The contribution of assigning facility <italic>i</italic> to site <italic>k</italic> and facility <italic>j</italic> to site <italic>l</italic> to the total cost is <italic>f<subscrpt>ij</subscrpt></italic> <italic>d<subscrpt>kl</subscrpt></italic>, where <italic>f<subscrpt>ij</subscrpt></italic> is the flow between facilities <italic>i</italic> and <italic>j</italic>, and <italic>d<subscrpt>kl</subscrpt></italic> is the distance between sites <italic>k</italic> and <italic>l</italic>. Only very small (<italic>n</italic>≤20) instances of the QAP have been solved exactly, and heuristics are therefore used to produce approximate solutions. This article describes a set of Fortran subroutines to find approximate solutions to dense quadratic assignment problems, having at least one symmetric flow or distance matrix. A greedy, randomized, adaptive search procedure (GRASP) is used to produce the solutions. The design and implementation of the code are described in detail, and extensive computational experiments are reported, illustrating solution quality as a function of running time.