A new solution method for the capacitated traveling purchaser problem


Thesis Type: Postgraduate

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

Approval Date: 2010

Thesis Language: English

Student: SELİN SERT

Supervisor: SEROL BULKAN

Abstract:

KAPASİTE KISITLI GEZGİN SATIN ALICI PROBLEMİNE YENI BİR ÇÖZÜM YOLU GELİŞTİRİLMESİ Gezgin satın alıcı problemi en çok bilinen tümleşik optimizasyon problemidir. Bu problemin amacı, bir şehirden başlayarak, belirlenen şehirleri de gezerek, tekrar başladığı şehire dönmek için en kısa yolu bulmaktır. Gezgin Alıcı Problemi, Gezgin Satıcı Probleminin bir genelleştirilmesidir. Bu problem, genellikle; rotalama, çizelgeleme ve depolama alanlarında kullanılabilmektedir. Bu problemin polinom zamanda bir çözümü yoktur ve NP-hard bir problemdir. Litaretürde bu problem için genellikle, sezgisel ve optimala yakın çözümler mevcuttur. Bu problemle ilgili kesin algoritmalar; Ramesh’in sözlüksel algoritması, Singh ve Van Oudheusden’in Branch and Bound algoritması ve Laporte et al.’in Branch and Cut Algoritmasıdır. En iyi sonuç elde edilen metotlarla problemleri çözmek çok uzun zaman gerektirmektedir. Bu çalışmada, literatürde Kapasite Kısıtlı Gezgin Satın Alıcı problemi için en iyi sonuç elde edilen metotlar, en iyi sonucu bulunamayan problemler için geliştirilen sezgisel, yarı sezgisel birçok metot ve bunların Kapasite Kısıtlı Gezgin Satın Alıcı örnekleri üzerinde çözülebilirliği ve yeni geliştirilen yöntemler incelenmiştir. Bu çalışmanın temel amacı, Kapasite Kısıtlı Gezgin Satın Alıcı Problemi’nin daha iyi anlaşılması için Kapasite Kısıtlı Gezgin Satın Alıcı Problemi’nin tanımlanması, günümüze kadar literatürde yapılan çalışmaların ve bu çalışmaların incelenmesidir. Kullanılan tekniklerin incelenmesi, yapılacak olan diğer çalışmalara yol gösterecek ve yeni çalışmalar için kaynak teşkil edebilecektir. ABSTRACT A NEW SOLUTION METHOD FOR THE CAPACITATED TRAVELING PURCHASER PROBLEM The traveling salesman problem (TSP) is perhaps the most well known combinatorial optimization problem. Objective of TSP is to find the shortest route that starts at a home city visits prescribed cities and return to starting city again. Traveling Purchaser Problem (TPP) is a generalization of the most known TSP. This problem arises in several applications, mainly in routing, scheduling contexts and warehousing. It is NP-hard in the strong sense because it reduces to the TSP if each product is available only at one market and each market sells only one product. The literature on TPP is mostly directed towards the development of heuristic or near optimal methods. The only available exact algorithms are the lexicographic algorithm of Ramesh, the branch-and-bound algorithm of Singh and Van Oudheusden, and the branch-and-cut algorithm of Laporte et al. In this thesis, exact algorithms, heuristic and meta-heuristic algorithms are studied. The main objective for this study is to determine recent studies and solution techniques until now for understanding what Capacitated Traveling Purchaser Problem is obviously. According to the analysis of the solution techniques, this project can instruct other researches that will be generated and this can be a basic resource for new researches.