Top

Published in:

2020 | OriginalPaper | Chapter

A Novel Solution Encoding in the Differential Evolution Algorithm for Optimizing Tourist Trip Design Problems

Authors : Dimitra Trachanatzi, Manousos Rigakis, Andromachi Taxidou, Magdalene Marinaki, Yannis Marinakis, Nikolaos Matsatsinis

Published in: Learning and Intelligent Optimization

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, a tourist trip design problem is simulated by the Capacitated Team Orienteering Problem (CTOP). The objective of the CTOP is to form feasible solution, as a set of itineraries, that represent a sequence visit of nodes, that maximize the total prize collected from them. Each itinerary is constrained by the vehicle capacity and the total travelled time. The proposed algorithmic framework, the Distance Related Differential Algorithm (DRDE), is a combination of the widely-known Differential Evolution algorithm (DE) and a novel encoding/decoding process, namely the Distance Related (DR). The process is based on the representation of the solution vector by the Euclidean Distance of the included nodes and offers a data-oriented approach to apply the original DE to a discrete optimization problem, such as the CTOP. The efficiency of the proposed algorithm is demonstrated over computational experiments.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Simple Dual-RAMP Algorithm for the Capacitated Facility Location Problem

next chapter Sonar Inspired Optimization in Energy Problems Related to Load and Emission Dispatch

Archetti, C., Feillet, D., Hertz, A., Speranza, M.G.: The capacitated team orienteering and profitable tour problems. J. Oper. Res. Soc. 60(6), 831–842 (2009)CrossRef

Archetti, C., Bianchessi, N., Speranza, M.G.: Optimal solutions for routing problems with profits. Discrete Appl. Math. 161(4–5), 547–557 (2013)MathSciNetCrossRef

Ben-Said, A., El-Hajj, R., Moukrim, A.: An adaptive heuristic for the capacitated team orienteering problem. IFAC-PapersOnLine 49(12), 1662–1666 (2016)CrossRef

Ben-Said, A., El-Hajj, R., Moukrim, A.: A variable space search heuristic for the capacitated team orienteering problem. J. Heuristics 25(2), 273–303 (2018)CrossRef

Butt, S.E., Cavalier, T.M.: A heuristic for the multiple tour maximum collection problem. Comput. Oper. Res. 21(1), 101–111 (1994)CrossRef

Cao, E., Lai, M., Yang, H.: Open vehicle routing problem with demand uncertainty and its robust strategies. Expert Syst. Appl. 41(7), 3569–3575 (2014)CrossRef

Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4), 568–581 (1964)CrossRef

Christofides, N.: The vehicle routing problem. In: Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (eds.) Combinatorial Optimization (1979)

Das, S., Mullick, S.S., Suganthan, P.N.: Recent advances in differential evolution-an updated survey. Swarm Evol. Comput. 27, 1–30 (2016)CrossRef

10.

Dechampai, D., Tanwanichkul, L., Sethanan, K., Pitakaso, R.: A differential evolution algorithm for the capacitated VRP with flexibility of mixing pickup and delivery services and the maximum duration of a route in poultry industry. J. Intell. Manuf. 28(6), 1357–1376 (2017)CrossRef

11.

Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G.: A survey on algorithmic approaches for solving tourist trip design problems. J. Heuristics 20(3), 291–328 (2014)CrossRef

12.

Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Nav. Res. Logist. (NRL) 34(3), 307–318 (1987)CrossRef

13.

Gunawan, A., Lau, H.C., Vansteenwegen, P.: Orienteering problem: a survey of recent variants, solution approaches and applications. Eur. J. Oper. Res. 255(2), 315–332 (2016)MathSciNetCrossRef

14.

Kunnapapdeelert, S., Kachitvichyanukul, V.: Modified DE algorithms for solving multi-depot vehicle routing problem with multiple pickup and delivery requests. In: Kachitvichyanukul, V., Sethanan, K., Golinska- Dawson, P. (eds.) Toward Sustainable Operations of Supply Chain and Logistics Systems. EcoProduction (Environmental Issues in Logistics and Manufacturing, pp. 361–373. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19006-8_25CrossRef

15.

Luo, Z., Cheang, B., Lim, A., Zhu, W.: An adaptive ejection pool with toggle-rule diversification approach for the capacitated team orienteering problem. Eur. J. Oper. Res. 229(3), 673–682 (2013)CrossRef

16.

Mingyong, L., Erbao, C.: An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Eng. Appl. Artif. Intell. 23(2), 188–195 (2010)CrossRef

17.

Onwubolu, G., Davendra, D.: Scheduling flow shops using differential evolution algorithm. Eur. J. Oper. Res. 171(2), 674–692 (2006)CrossRef

18.

Opara, K.R., Arabas, J.: Differential evolution: a survey of theoretical analyses. Swarm Evol. Comput. 44, 546–558 (2019)CrossRef

19.

Storn, R., Price, K.: Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(4), 341–359 (1997)MathSciNetCrossRef

20.

Tarantilis, C.D., Stavropoulou, F., Repoussis, P.P.: The capacitated team orienteering problem: a bi-level filter-and-fan method. Eur. J. Oper. Res. 224(1), 65–78 (2013)MathSciNetCrossRef

21.

Teoh, B.E., Ponnambalam, S.G., Kanagaraj, G.: Differential evolution algorithm with local search for capacitated vehicle routing problem. Int. J. Bio-Inspired Comput. 7(5), 321–342 (2015)CrossRef

22.

Vansteenwegen, P., Souffriau, W., Berghe, G.V., Van Oudheusden, D.: The city trip planner: an expert system for tourists. Expert Syst. Appl. 38(6), 6540–6546 (2011)CrossRef

23.

Wang, W., Wu, B., Zhao, Y., Feng, D.: Particle swarm optimization for open vehicle routing problem. In: Huang, D.-S., Li, K., Irwin, G.W. (eds.) ICIC 2006, Part II. LNCS (LNAI), vol. 4114, pp. 999–1007. Springer, Heidelberg (2006). https://doi.org/10.1007/978-3-540-37275-2_126CrossRef

Title: A Novel Solution Encoding in the Differential Evolution Algorithm for Optimizing Tourist Trip Design Problems
Authors: Dimitra Trachanatzi
Manousos Rigakis
Andromachi Taxidou
Magdalene Marinaki
Yannis Marinakis
Nikolaos Matsatsinis
Publisher: Springer International Publishing
Book: Learning and Intelligent Optimization
Print ISBN: 978-3-030-38628-3

Electronic ISBN: 978-3-030-38629-0

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-38629-0_21

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner