Alternatywna metoda rozwiązywania kwadratowego zagadnienia przydziału

• Autorzy: Schiff K.

Warianty tytułu

EN

Alternative method for quadratic assignment problem

• Języki publikacji: PL

Abstrakty

PL

Kwadratowy problem przydziału polega na takim umieszczeniu fabryk (obiektów) w lokalizacjach, aby całkowity koszt wyrażony jako suma iloczynów odległości między obiektami i strumieni towarów przepływających między tymi obiektami był jak najmniejszy. Artykuł ten przedstawia nowy sposób modelowania problemu przy wykorzystaniu grafów dwudzielnych i nowy sposób rozwiązania problemu, krok po kroku, polegający na znalezieniu maksymalnego dopasowania o minimalnej wadze z uwzględnieniem fizycznego umiejscowienia fabryk (obiektów) w lokalizacjach.

EN

A new method for quadratic assignment problem is presented. The problem is modeled by a bipartite graph. Hungarian method is used for finding the solution: the assignment with minimum costs is found, but this solution must take into consideration of real objects localizations.

Słowa kluczowe

PL

kwadratowe zagadnienie przydziału; graf dwudzielny

EN

quadratic assignment problem; bipartite graph

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2010
• Tom: nr 2
• Opis fizyczny: Pełny tekst na CD, Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Schiff K.

• Politechnika Krakowska, Wydział Inżynierii Elektrycznej i Komputerowej,

Bibliografia

• [1] Baj W.: Kwadratowe zagadnienie przydziału, praca magisterska 2008, Katedra Automatyki, Politechnika Krakowska.
• [2] Burkard R.E., Cela E.: Handbook of combinatorial optimization, 1999, Kluwer Dordrecht.
• [3] Charnesethikul P.: An exact branch and bound algorithm for the general quadratic assignment problem, 1988, Ph.D dissertation, Texas Tech University.
• [4] Clausen J.: Branch and bound algorithms – principles and examples, 1999, Tech. Raport, Department of Computer Science, University of Copenhagen, Denmark.
• [5] Dolan A., Aldous J.: Networks and algorithms, John Wiley & Sons, England 1993.
• [6] Dorigo M.: Local search and metaheuristic for the quadratic assignment problem, 1999, New idea in optimization, McGraw-Hill.
• [7] Ji P., Wu Y., Liu H.: A solution method for the quadratic assignment problem, 2006, The Sixth International Symposium on Operational Research and Its Applications (ISORA’2006), 106-16.
• [8] Koopmans T.C., Beckmann M.J.: Assignment problems and the location of economics activities, 1957, Econometrica, 25, str. 53-76.
• [9] Povh J.: Assignment problems in Logistics, Logistics and Sustainable Transport, 2006, vol.1, issue.3 ,str. 72-81.
• [10] http://www.intellektik.informatik.tu-darmstadt.de/~meta/QAP/qap.html