VLSN search algorithms for partitioning problems using matching neighbourhoods

ÖNCAN T., Kabadi S. N., Nair K. P. K., Punnen A. P.

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, cilt.59, sa.3, ss.388-398, 2008 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 59 Sayı: 3
  • Basım Tarihi: 2008
  • Doi Numarası: 10.1057/palgrave.jors.2602356
  • Dergi Adı: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Sayfa Sayıları: ss.388-398
  • Galatasaray Üniversitesi Adresli: Evet

Özet

In this paper, we propose a general paradigm to design very large-scale neighbourhood search algorithms for generic partitioning-type problems. We identify neighbourhoods of exponential size, called matching neighbourhoods, comprised of the union of a class of exponential neighbourhoods. It is shown that these individual components of the matching neighbourhood can be searched in polynomial time, whereas searching the matching neighbourhood is NP-hard. Matching neighbourhood subsumes a well-known class of exponential neighbourhoods called cyclic-exchange neighbourhoods. Our VLSN algorithm is implemented for two special cases of the partitioning problem; the covering assignment problem and the single source transportation problem. Encouraging experimental results are also reported.