nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

6. Application of a Knowledge Discovery Process to Study Instances of Capacitated Vehicle Routing Problems

verfasst von : Tommi Kärkkäinen, Jussi Rasku

Erschienen in: Computation and Big Data for Transport

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Vehicle Routing Problems (VRP) are computationally challenging, constrained optimization problems, which have central role in logistics management. Usually different solvers are being developed and applied for different kind of problems. However, if descriptive and general features could be extracted to describe such problems and their solution attempts, then one could apply data mining and machine learning methods in order to discover general knowledge on such problems. The aim then would be to improve understanding of the most important characteristics of VRPs from both efficient solution and utilization points of view. The purpose of this article is to address these challenges by proposing a novel feature analysis and knowledge discovery process for Capacitated Vehicle Routing problems (CVRP). Results of knowledge discovery allow us to draw interesting conclusions from relevant characteristics of CVRPs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Maritime Transport and the Threat of Bio Invasion and the Spread of Infectious Disease

Nächstes Kapitel A New Multi-objective Solution Approach Using ModeFRONTIER and OpenTrack for Energy-Efficient Train Timetabling Problem

Nur mit Berechtigung zugänglich

Asta S (2015) Machine learning for improving heuristic optimisation. PhD thesis, University of Nottingham

Augerat P, Belenguer JM, Benavent E, Corberán A, Naddef D, Rinaldi G (1995) Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical report 949-M. Universite Joseph Fourier, Grenoble, France

Äyrämö S (2006) Knowledge mining using robust clustering. Jyväskylä studies in computing, vol 63, University of Jyväskylä, Faculty of Information Technology

Äyrämö S, Kärkkäinen T, Majava K (2007) Robust refinement of initial prototypes for partitioning-based clustering algorithms. Recent advances in stochastic modeling and data analysis. World Scientific, Singapore, pp 473–482

Becker S, Gottlieb J, Stützle T (2006) Applications of racing algorithms: an industrial perspective. In: Proceedings of the 7th international conference on artificial evolution - EA’05. Springer, Berlin, pp 271–283

Borg I, Groenen PJF (2005) Modern multidimensional scaling: theory and applications, 2nd edn. Springer, Berlin

Bramer M (2007) Principles of data mining, vol 180. Springer, Berlin

Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. In: Christofides N, Mingozzi A, Toth P Sandi C (eds) Combinatorial optimization. Wiley, New York, pp 315–338

Cord A, Ambroise C, Cocquerez J-P (2006) Feature selection in robust clustering based on Laplace mixture. Pattern Recognit Lett 27(6):627–635CrossRef

10.

Csorba K, Vajk I (2007) Term clustering and confidence measurement. Advances in information systems development: new methods and practice for the networked society 1:481CrossRef

11.

Czech ZJ (2010) A parallel simulated annealing algorithm as a tool for fitness landscapes exploration. In: Ros A (ed) Parallel and distributed computing. InTech

12.

Dantzig GB, Ramser JH (1959) The truck dispatching problem. Manag Sci 6(1):80–91MathSciNetCrossRef

13.

Dheeru D, Taniskidou EK (2017) UCI machine learning repository. http://archive.ics.uci.edu/ml

14.

Eksioglu B, Vural AV, Reisman A (2009) The vehicle routing problem: a taxonomic review. Comput Ind Eng 57(4):1472–1483CrossRef

15.

Fayyad U, Piatetsky-Shapiro G, Smyth P (1996) From data mining to knowledge discovery in databases. AI Mag 17(3):37–54

16.

Fayyad U, Piatetsky-Shapiro G, Smyth P (1996) The KDD process for extracting useful knowledge from volumes of data. Commun ACM 39(11):27–34

17.

Fayyad UM, Piatetsky-Shapiro G, Smyth P (1996) From data mining to knowledge discovery: an overview. Advances in knowledge discovery and data mining. AAAI Press, Menlo Park, pp 1–30

18.

Fisher ML (1994) Optimal solution of vehicle routing problems using minimum k-trees. Oper Res 42(4):626–642MathSciNetCrossRef

19.

Gillett BE, Johnson JG (1976) Multi-terminal vehicle-dispatch algorithm. Omega 4(6):711–718CrossRef

20.

Gomes JPP, Mesquita DPP, Freire AL, Junior AHS, Kärkkäinen T (2017) A robust minimal learning machine based on the M-estimator. In: Proceedings of the European symposium on artificial neural networks, computational intelligence and machine learning - ESANN 2017, pp 383–388

21.

Hämäläinen J, Jauhiainen S, Kärkkäinen T (2017) Comparison of internal clustering validation indices for prototype-based clustering. Algorithms 10(3):105MathSciNetCrossRef

22.

Hämäläinen J, Kärkkäinen T, Rossi T (2018) Scalable robust clustering method for large and sparse data. In: Proceedings of the European symposium on artificial neural networks, computational intelligence and machine learning - ESANN 2018, 6 pp

23.

Hänninen J, Kärkkäinen T (2016) Comparison of four-and six-layered configurations for deep network pretraining. In: European symposium on artificial neural networks, computational intelligence and machine learning - ESANN 2016, pp 533–538

24.

Haykin SS, Haykin SS, Haykin SS, Haykin SS (2009) Neural networks and learning machines, vol 3. Pearson, Upper Saddle River

25.

Hoff A, Andersson H, Christiansen M, Hasle G, Løkketangen A (2010) Industrial aspects and literature survey: fleet composition and routing. Comput Oper Res 37(12):2041–2061MathSciNetCrossRef

26.

Hutter F, Hoos HH, Leyton-Brown K (2013) Identifying key algorithm parameters and instance features using forward selection. In: International conference on learning and intelligent optimization. Springer, pp 364–381

27.

Jauhiainen S, Kärkkäinen T (2017) A simple cluster validation index with maximal coverage. In: Proceedings of the European symposium on artificial neural networks, computational intelligence and machine learning - ESANN 2017, pp 293–298

28.

Kanda J, Carvalho A, Hruschka E, Soares C (2011) Selection of algorithms to solve traveling salesman problems using meta-learning. Int J Hybrid Intell Syst 8(3):117–128CrossRef

29.

Kanda J, de Carvalho A, Hruschka E, Soares C, Brazdil P (2016) Meta-learning to select the best meta-heuristic for the traveling salesman problem: a comparison of meta-features. Neurocomputing 205:393–406CrossRef

30.

Kärkkäinen T (2002) MLP in layer-wise form with applications to weight decay. Neural Comput 14(6):1451–1480CrossRef

31.

Kärkkäinen T (2015) Assessment of feature saliency of MLP using analytic sensitivity. In: European symposium on artificial neural networks, computational intelligence and machine learning - ESANN2015. Presses universitaires de Louvain, pp 273–278

32.

Kärkkäinen T, Glowinski R (2019) A Douglas-Rachford method for sparse extreme learning machine. Methods Appl Anal 1–19 (to appear)

33.

Kärkkäinen T, Heikkola E (2004) Robust formulations for training multilayer perceptrons. Neural Comput 16(4):837–862CrossRef

34.

Kärkkäinen T, Saarela M (2015) Robust principal component analysis of data with missing values. International workshop on machine learning and data mining in pattern recognition. Springer, pp 140–154

35.

Kotthoff L (2016) Algorithm selection for combinatorial search problems: a survey. In: Bessiere C, De Raedt L, Kotthoff L, Nijssen S, O’Sullivan B, Pedreschi D (eds) Data mining and constraint programming: foundations of a cross-disciplinary approach. Springer, pp 149–190

36.

Kotthoff L, Kerschke P, Hoos H, Trautmann H (2015) Improving the state of the art in inexact TSP solving using per-instance algorithm selection. In: International conference on learning and intelligent optimization. Springer, pp 202–217

37.

Kruskal WH, Wallis WA (1952) Use of ranks in one-criterion variance analysis. J Am Stat Assoc 47(260):583–621CrossRef

38.

Kubiak M (2007) Distance measures and fitness-distance analysis for the capacitated vehicle routing problem. In: Doerner KF, Gendreau M, Greistorfer P, Gutjahr W, Hartl RF, Reimann M (eds) Metaheuristics: progress in complex systems optimization. Springer US, Boston, MA, pp 345–364

39.

Laporte G (2009) Fifty years of vehicle routing. Transp Sci 43(4):408–416CrossRef

40.

Laporte G, Ropke S, Vidal T (2014) Heuristics for the vehicle routing problem. Vehicle routing: problems, methods, and applications, 2nd edn. SIAM, Philadelphia, pp 87–116

41.

Marmion M-É, Jourdan L, Dhaenens C (2013) Fitness landscape analysis and metaheuristics efficiency. J Math Model Algorithms Oper Res 12(1):3–26MathSciNetMATH

42.

Mersmann O, Bischl B, Trautmann H, Wagner M, Bossek J, Neumann F (2013) A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem. Ann Math Artif Intell 69(2):151–182MathSciNetCrossRef

43.

Nallaperuma S, Wagner M, Neumann F, Bischl B, Mersmann O, Trautmann H (2013). A feature-based comparison of local search and the Christofides algorithm for the travelling salesperson problem. In: Proceedings of the twelfth workshop on foundations of genetic algorithms XII. ACM, pp 147–160

44.

Nallaperuma S, Wagner M, Neumann F (2015) Analyzing the effects of instance features and algorithm parameters for max-min ant system and the traveling salesperson problem. Front Robot AI 2:18CrossRef

45.

Niemelä M, Äyrämö S, Kärkkäinen T (2018) Comparison of cluster validation indices with missing data. In: Proceedings of the European symposium on artificial neural networks, computational intelligence and machine learning - ESANN 2018, 6 pp

46.

Nygard KE, Juell P, Kadaba N (1990) Neural networks for selective vehicle routing heuristics. ORSA J Comput 2(4):353–364CrossRef

47.

Pellegrini P, Birattari M (2007) Implementation effort and performance. In: Stutzle T, Birattari M, Hoos HH (eds) Engineering stochastic local search algorithms. Designing, implementing and analyzing effective heuristics. Lecture notes in computer science, vol 4638. Springer, Berlin, pp 31–45

48.

Pihera J, Musliu N (2014) Application of machine learning to algorithm selection for TSP. In: IEEE 26th international conference on tools with artificial intelligence (ICTAI). IEEE, pp 47–54

49.

Rasku J, Kärkkäinen T, Hotokka P (2013) Solution space visualization as a tool for vehicle routing algorithm development. In: Collan M, Hämälainen J, Luukka P (eds) Proceedings of the Finnish operations research society 40th anniversary workshop (FORS40), vol 13. LUT Scientific and Expertise Publications, pp 9–12

50.

Rasku J, Musliu N, Kärkkäinen T (2014) Automating the parameter selection in VRP: an off-line parameter tuning tool comparison. In: Fitzgibbon W, Kuznetsov YA, Neittaanmäki P, Pironneau O (eds) Modeling, simulation and optimization for science and technology. Springer, pp 191–209

51.

Rasku J, Kärkkäinen T, Musliu N (2016) Feature extractors for describing vehicle routing problem instances. In: Hardy B, Qazi A, Ravizza S (eds) 5th student conference on operational research (SCOR 2016). OpenAccess series in informatics (OASIcs), vol 50. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp 1–13

52.

Reinelt G (1991) TSPLIB - a traveling salesman problem library. ORSA J Comput 3(4):376–384MathSciNetCrossRef

53.

Rice JR (1976) The algorithm selection problem. Adv Comput 15:65–118CrossRef

54.

Saarela M, Kärkkäinen T (2015) Analysing student performance using sparse data of core bachelor courses. J Educ Data Min 7(1):3–32

55.

Saarela M, Hämäläinen J, Kärkkäinen T (2017) Feature ranking of large, robust, and weighted clustering result. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, pp 96–109

56.

Singhal A et al (2001) Modern information retrieval: a brief overview. IEEE Data Eng Bull 24(4):35–43

57.

Smith-Miles K, Lopes L (2012) Measuring instance difficulty for combinatorial optimization problems. Comput Oper Res 39(5):875–889MathSciNetCrossRef

58.

Smith-Miles K, van Hemert J (2011) Discovering the suitability of optimisation algorithms by learning from evolved instances. Ann Math Artif Intell 61(2):87–104

59.

Steinhaus M (2015) The application of the self organizing map to the vehicle routing problem. PhD thesis, University of Rhode Island

60.

Toth P, Vigo D (2014) Vehicle routing: problems, methods, and applications. MOS-SIAM series on optimization. SIAM, Philadelphia

61.

Tuzun D, Magent MA, Burke LI (1997) Selection of vehicle routing heuristic using neural networks. Int Trans Oper Res 4(3):211–221CrossRef

62.

Van Stein B, Emmerich M, Yang Z (2013) Fitness landscape analysis of NK landscapes and vehicle routing problems by expanded barrier trees. EVOLVE-a bridge between probability, set oriented numerics, and evolutionary computation IV. Springer, pp 75–89

63.

Ventresca M, Ombuki-Berman B, Runka A (2013) Predicting genetic algorithm performance on the vehicle routing problem using information theoretic landscape measures. In: European conference on evolutionary computation in combinatorial optimization - EvoCOP 2013. Springer, pp 214–225

64.

Verleysen M, François D (2005) The curse of dimensionality in data mining and time series prediction. In: International work-conference on artificial neural networks. Springer, pp 758–770

65.

Wartiainen P, Kärkkäinen T (2015) Hierarchical, prototype-based clustering of multiple time series with missing values. In: Proceedings of the European symposium on artificial neural networks, computational intelligence and machine learning - ESANN 2015, pp 95–100

66.

Wink S, Back T, Emmerich M (2012) A meta-genetic algorithm for solving the capacitated vehicle routing problem. In: IEEE congress on evolutionary computation - CEC’12, pp 1–8

Titel: Application of a Knowledge Discovery Process to Study Instances of Capacitated Vehicle Routing Problems
verfasst von: Tommi Kärkkäinen
Jussi Rasku
Verlag: Springer International Publishing
Buch: Computation and Big Data for Transport
Print ISBN: 978-3-030-37751-9

Electronic ISBN: 978-3-030-37752-6

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-37752-6_6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner