Dynamic Mean Value Cross Decomposition Algorithm for Capacitated Facility Location Problems

摘要

Šiame straipsnyje pasiūlytas praktinis algoritmas apribotos talpos objektų vietos parinkimo uždaviniams spręsti. Yra keletas būdų, skirtų pirminiam sprendiniui rasti naudojantis pirmine ir antrine struktūromis. Vienas iš šių būdų yra vidutinės vertės kryžminio skaidymo metodas. Anksčiau šis metodas buvo taikytas tik neapribotos talpos objektų vietos parinkimo uždaviniams, nes pajėgumas labai priklauso nuo uždavinio struktūros. Siūlomas algoritmas, vadinamas dinaminio vidutinės vertės kryžminio skaidymo algoritmu, yra efektyvi vidutinės vertės kryžminio skaidymo ir pjaunančiųjų plokštumų metodų integracija. Pateikiami įvairių uždavinių sprendimo pasiūlytu algoritmu rezultatai.%In this article, we propose a practical algorithm for capacitated facility location problems (CFLP). There are some approaches which can obtain primal solutions while simultaneously exploiting the primal structure and the dual structure. One of these approaches is the mean value cross decomposition (MVCD) method that ensures convergence without solving master problems. However, MVCD has been previously applied only to uncapacitated facility location problems (UFLP), due to the fact that the performance is highly dependent on the structure of the problem. The proposed algorithm, named the dynamic mean value cross decomposition algorithm (DMVCD), is effectively integrated with MVCD and cutting plane methods in order to tighten the bounds by reducing the duality gap. Computational results of various instances are also reported to verify the effectiveness and efficiency of DMVCD.