Research Article
BibTex RIS Cite

VARIABLE NEIGHBORHOOD DESCENT FOR TRAVELLING SALESPERSON PROBLEM WITH HOTEL SELECTION

Year 2020, Volume: 4 Issue: 1, 324 - 335, 30.06.2020

Abstract

The
Travelling Salesperson Problem with Hotel Selection (TSPHS) is a variant of The
Travelling Salesperson Problem (TSP). In case of TSPHS problem, all points
cannot be visited in a single day due to the restriction of working time /
distance. Since this problem belongs to the NP-hard problem class, the use of
heuristic method has an advantage in terms of the solution time. The initial
solution is obtained using The Nearest Neighbor Algorithm (NN). In order to
improve this solution, the Variable Neighborhood Descent (VND) is used. Python
language is used for coding. The algorithms experiments are made on the test
problems in the literature using various criteria and the results obtained are
compared with the best available solutions and the performance of algorithm is
evaluated.




References

  • Baltz, A., Ouali, M.E., Jӓger, G., Sauerland, V., Srivastav, A., "Exact And Heuristic Algorithms For The Travelling Salesman Problem With Multiple Time Windows And Hotel Selection", Journal Of The Operational Research Society, 66(4):615-626, (2014).
  • Castro, M., Sörensen, K., Vansteenwegen, P., Goos, P., "A Simple GRASP+VND For The Travelling Salesperson Problem With Hotel Selection", Technical Report, University of Antwerp, Faculty of Applied Economics, 024, (2012).
  • Castro, M., Sörensen, K., Vansteenwegen, P., Goos, P., "A Memetic Algorithm For The Travelling Salesperson Problem With Hotel Selection", Computers Operations Research, 40(7): 1716-1728, (2013).
  • Castro, M., Sörensen, K., Vansteenwegen, P., Goos, P., "A Fast Metaheuristic For The Travelling Salesperson problem With Hotel Selection", 4OR, 13(1): 15-34, (2014).
  • Divsalar, A., Vansteenwegen, P., Sörensen, K., Cattrysse, D., "A Memetic Algorithm For The Orienteering Problem With Hotel Selection", European Journal Of Operational Research, 237(1): 29-49, (2014).
  • Gencel, C.A., "Otel Seçimli Gezgin Satıcı Problemi İçin Yeni Matematiksel Modeller", Yüksek Lisans Tezi, Başkent Üniversitesi Fen Bilimleri Enstitüsü, Ankara, 2019.
  • Gencel, E., "Otel Seçimli Oryantiring Problemi İçin Yeni Matematiksel Modeller", Yüksek Lisans Tezi, Başkent Üniversitesi Fen Bilimleri Enstitüsü, Ankara, 2019.
  • Hansen, P. and N. Mladenovic, "A Tutorial On Variable Neighborhood Search", Technical Report G-2003-46, Les Cahiers du GERAD, HEC Montreal and GERAD, Canada (2003).
  • Hoek, S.V., "Tabu Search For The Orienteering Problem With Hotel Selection", Econometrics and Operations Research, (2016).
  • Lu, Y., Benlic, U., Wu, Q., "A Hybrid Dynamic programming And Memetic Algorithm To The Travelling Salesman Problem With Hotel Selection", Computers and Operations Research, 193-207, (2017).
  • Radmanesh, M., Kumar, M., Nemati, A., Sarim, M., "Solution Of Traveling Salesman Problem With Hotel Selection In The Framework Of MILP-Tropical Optimization", American Control Conference (ACC), 6-8, (2016).
  • Sousa, M.M., Ochi, L.S., Martins, S.L., "An Efficient Heuristic To The Travelling Salesperson Problem With Hotel Selection", Hybrid Metaheuristics Conference, 31-45, (2019).
  • Toledo, A., Riff, M.C., "HOPHS: A Hyperheuristic That Solves Orienteering Problem With Hotel Selection", International Conference on Digital Information Processing and Communications (ICDIPC), (2015).
  • Vansteenwegen, P., Souffriau, W., Sörensen, K., "The Travelling Salesperson Problem With Hotel Selection", Journal Of The Operational Research Society, 63(2): 207–17, (2011).

OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ

Year 2020, Volume: 4 Issue: 1, 324 - 335, 30.06.2020

Abstract

Otel
Seçimli Gezgin Satıcı Problemi (OSGSP) Gezgin Satıcı Probleminin (GSP) bir çeşididir.
OSGSP'nde çalışma süresi/mesafesi kısıtından dolayı tüm noktalar tek bir günde
ziyaret edilememektedir. Bu problem NP-zor problem sınıfına girdiği için
sezgisel yöntem kullanılması çözüm zamanı açısından avantaj sağlamıştır. İlk
olarak En Yakın Komşu Prensibi (EYKP) kullanılarak başlangıç çözüm elde
edilmiştir. Sonrasında bulunan bu çözümü iyileştirmek amacıyla Değişken Komşu İniş
Algoritması (DKİA)'ndan faydalanılmıştır. Algoritmalar Python dili ile
kodlanmıştır. Literatürde var olan test problemleri üzerinde çeşitli ölçütler
kullanılarak denemeler yapılmıştır ve elde edilen sonuçlar var olan en iyi
çözümler ile karşılaştırılarak algoritmanın performansı değerlendirilmiştir.

References

  • Baltz, A., Ouali, M.E., Jӓger, G., Sauerland, V., Srivastav, A., "Exact And Heuristic Algorithms For The Travelling Salesman Problem With Multiple Time Windows And Hotel Selection", Journal Of The Operational Research Society, 66(4):615-626, (2014).
  • Castro, M., Sörensen, K., Vansteenwegen, P., Goos, P., "A Simple GRASP+VND For The Travelling Salesperson Problem With Hotel Selection", Technical Report, University of Antwerp, Faculty of Applied Economics, 024, (2012).
  • Castro, M., Sörensen, K., Vansteenwegen, P., Goos, P., "A Memetic Algorithm For The Travelling Salesperson Problem With Hotel Selection", Computers Operations Research, 40(7): 1716-1728, (2013).
  • Castro, M., Sörensen, K., Vansteenwegen, P., Goos, P., "A Fast Metaheuristic For The Travelling Salesperson problem With Hotel Selection", 4OR, 13(1): 15-34, (2014).
  • Divsalar, A., Vansteenwegen, P., Sörensen, K., Cattrysse, D., "A Memetic Algorithm For The Orienteering Problem With Hotel Selection", European Journal Of Operational Research, 237(1): 29-49, (2014).
  • Gencel, C.A., "Otel Seçimli Gezgin Satıcı Problemi İçin Yeni Matematiksel Modeller", Yüksek Lisans Tezi, Başkent Üniversitesi Fen Bilimleri Enstitüsü, Ankara, 2019.
  • Gencel, E., "Otel Seçimli Oryantiring Problemi İçin Yeni Matematiksel Modeller", Yüksek Lisans Tezi, Başkent Üniversitesi Fen Bilimleri Enstitüsü, Ankara, 2019.
  • Hansen, P. and N. Mladenovic, "A Tutorial On Variable Neighborhood Search", Technical Report G-2003-46, Les Cahiers du GERAD, HEC Montreal and GERAD, Canada (2003).
  • Hoek, S.V., "Tabu Search For The Orienteering Problem With Hotel Selection", Econometrics and Operations Research, (2016).
  • Lu, Y., Benlic, U., Wu, Q., "A Hybrid Dynamic programming And Memetic Algorithm To The Travelling Salesman Problem With Hotel Selection", Computers and Operations Research, 193-207, (2017).
  • Radmanesh, M., Kumar, M., Nemati, A., Sarim, M., "Solution Of Traveling Salesman Problem With Hotel Selection In The Framework Of MILP-Tropical Optimization", American Control Conference (ACC), 6-8, (2016).
  • Sousa, M.M., Ochi, L.S., Martins, S.L., "An Efficient Heuristic To The Travelling Salesperson Problem With Hotel Selection", Hybrid Metaheuristics Conference, 31-45, (2019).
  • Toledo, A., Riff, M.C., "HOPHS: A Hyperheuristic That Solves Orienteering Problem With Hotel Selection", International Conference on Digital Information Processing and Communications (ICDIPC), (2015).
  • Vansteenwegen, P., Souffriau, W., Sörensen, K., "The Travelling Salesperson Problem With Hotel Selection", Journal Of The Operational Research Society, 63(2): 207–17, (2011).
There are 14 citations in total.

Details

Primary Language Turkish
Journal Section Research Article
Authors

İpek Damla Akpınar 0000-0001-8977-9521

Barış Keçeci 0000-0002-2730-5993

Publication Date June 30, 2020
Submission Date September 10, 2019
Acceptance Date July 14, 2020
Published in Issue Year 2020 Volume: 4 Issue: 1

Cite

APA Akpınar, İ. D., & Keçeci, B. (2020). OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ. Journal of Turkish Operations Management, 4(1), 324-335.
AMA Akpınar İD, Keçeci B. OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ. JTOM. June 2020;4(1):324-335.
Chicago Akpınar, İpek Damla, and Barış Keçeci. “OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ”. Journal of Turkish Operations Management 4, no. 1 (June 2020): 324-35.
EndNote Akpınar İD, Keçeci B (June 1, 2020) OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ. Journal of Turkish Operations Management 4 1 324–335.
IEEE İ. D. Akpınar and B. Keçeci, “OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ”, JTOM, vol. 4, no. 1, pp. 324–335, 2020.
ISNAD Akpınar, İpek Damla - Keçeci, Barış. “OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ”. Journal of Turkish Operations Management 4/1 (June 2020), 324-335.
JAMA Akpınar İD, Keçeci B. OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ. JTOM. 2020;4:324–335.
MLA Akpınar, İpek Damla and Barış Keçeci. “OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ”. Journal of Turkish Operations Management, vol. 4, no. 1, 2020, pp. 324-35.
Vancouver Akpınar İD, Keçeci B. OTEL SEÇİMLİ GEZGİN SATICI PROBLEMİ İÇİN DEĞİŞKEN KOMŞU İNİŞ SEZGİSELİ. JTOM. 2020;4(1):324-35.

2229319697  logo   logo-minik.png 200311739617396