A metaheuristic algorithm to elasticity based shelf space allocation problem


Thesis Type: Doctorate

Institution Of The Thesis: Marmara University, Faculty of Engineering, Computer Engineering, Turkey

Approval Date: 2016

Thesis Language: English

Student: AYŞE HANDE EROL BİNGÜLER

Co-Supervisor: SEROL BULKAN, MUSTAFA AĞAOĞLU

Abstract:

RAF ALANI YERLEŞTİRME PROBLEMLERİ İÇİN METASEZGİSEL ÇÖZÜM ALGORİTMASI Sırt çantası problemi, kombinatoryal eniyileme problemlerinden biridir. Her birinin ağırlığı belli olan, n adet parçayı belli bir kapasitesi olan bir sırt çantasına, maksimum kar getirecek şekilde yerleştirilmesi problemidir. Problem, kaynak dağılımında kullanılmaya başlamış, aynı zamanda kombinatorik (combinatorics), bilgisayar bilimi, karmaşıklık teorisi (complexity theory), uygulamalı matematik, eniyileme gibi alanlarda da kullanılmaktadır. Sırt çantası problemi, kombinatoryal eniyileme problemlerinden biridir. Raf alanı eniyilemesi problemi (shelf space allocation problem) çok kısıtlı sırt çantası problemine benzemektedir. Sırt çantası probleminden farklı olarak kutulama problemi, negatif olmama ve tamsayı kısıtına ek olarak kapasite kısıtı da olan sırt çantası problemidir. Kutulama probleminde bazı kuralları içeren kısıtlar (policy constraints) da mevcuttur. Sırt çantası modeli, bütçe veya insan kaynakları planlaması gibi konular ile ilgili tek baskın kaynak içeren birçok problemde uygulanabilmektedir. Kutulama problemi sınırlı kaynağın dağılımı ile ilgili yönetsel kararlarda uygulanabilmektedir. Karmaşıklığından dolayı raf alanı eniyilemesi problemi, alan yönetim sistemleri için birçok sezgisel yaklaşım geliştirilmiştir. Kutulama problemi ile ilgili literatür araştırmasını yaptıktan sonra kutulama problemi için elastisite bazlı bir model oluşturulmuştur. Çalışmada raf alanı yerleştirme problemi için kapsamlı eniyileme modeli kullanılacaktır. Perakende sektöründe kullanılabilecek tamsayılı programlama modeli tasarlanmıştır. Alan elastikliği faktörü de amaç fonksiyonuna eklenerek ürün kalemlerini amaç fonksiyonu doğrultusunda uygun raf alanına en uygun yerleştirme yapılmıştır. Önerilen algoritma ile belirlenen kısıtlar ve amaç fonksiyonu doğrultusunda raf alanına veya uzunluğuna bağlı olarak en iyi ürün yerleştirmeleri yapılmıştır. Sezgisel yaklaşım kabul edilebilir bir zaman içinde yaklaşık en iyi sonuç elde edilmiştir. ABSTRACT A METAHEURISTIC ALGORITHM TO ELASTICITY BASED SHELF SPACE ALLOCATION PROBLEM A shelf space allocation problem (SSAP) is sort of knapsack problem with multi constraints regarding to shelf capacity and policy constraints. The knapsack model could include variety of implementations used for resource allocation in order to deal with some problems like human resource management, budget planning and etc. Solving the SSAP could improve retail operations and enables retail management to the use of shelf space efficiently. SSAP is good for reaching optimal management decision required for dealing with limited resource allocation. In addition, SSAP is related with NP-hard complexity used to describe some decision problems. Thus, in order to solving the commercial space management allocation issue, some heuristics have been proposed and implemented in the retail industry. In addition using simple intuitive rules for improving the guidelines of operational choices relatively, the decision maker in retailing industry can easily use to practically apply decisions about the allocation of shelf space. The concern for practicability and simplicity for the previous researches, decisions and outcomes in the decisions of space allocation that reach far from the optimum levels of the performance. Yet improvements in the information technology and computer science allowed high computational efficiency and the development of optimization that extended feasible solution to the stage of space management systems to solve SSAP. This study proposes an elasticity based SSAP model which is an inclusive optimization model for the allocation of shelf space. The model adapted a mathematical model used integer programming to increase its applicability in the marketing and the retail industry. Besides that, it aims to identify and define the allocation space for items precisely. Doing that would allow management to improve retail operations and give helps for an efficient use of the limited shelf space. In other words, the model designed to permit maximize the self space by adding space elasticity factor. In addition that Variable Neighborhood Search (VNS) algorithm, based on neighborhoods, used to locate items into shelf space, subject to restrictions, and the benchmarking problems are generated for this proposed algorithm. VNS outperforms other heuristics for test problems.