A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery Problems
<i>Background</i>: The Multi Depot Pickup and Delivery Problem with Time Windows and Heterogeneous Vehicle Fleets (MDPDPTWHV) is a strongly practically oriented routing problem with many real-world constraints. Due to its complexity, solution approaches with sufficiently good quality ide...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-02-01
|
| Series: | Logistics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2305-6290/8/1/14 |
| _version_ | 1797240286528667648 |
|---|---|
| author | Cornelius Rüther Julia Rieck |
| author_facet | Cornelius Rüther Julia Rieck |
| author_sort | Cornelius Rüther |
| collection | DOAJ |
| description | <i>Background</i>: The Multi Depot Pickup and Delivery Problem with Time Windows and Heterogeneous Vehicle Fleets (MDPDPTWHV) is a strongly practically oriented routing problem with many real-world constraints. Due to its complexity, solution approaches with sufficiently good quality ideally contain several operators with certain probabilities.Thus, automatically selecting the best parameter configurations enhances the overall solution quality. <i>Methods</i>: To solve the MDPDPTWHV, we present a Grouping Genetic Algorithm (GGA) framework with several operators and population management variants. A Bayesian Optimization (BO) approach is introduced to optimize the GGA’s parameter configuration. The parameter tuning is evaluated on five data sets which differ in several structural characteristics and contain 1200 problem instances. The outcomes of the parameter-tuned GGA are compared to both the initial GGA parameter configuration and a state-of-the-art Adaptive Large Neighborhood Search (ALNS). <i>Results</i>: The presented GGA framework achieves a better solution quality than the ALNS, even for the initial parameter configuration used. The mean value of the relative error is less than 0.9% and its standard deviation is less than 1.31% for every problem class. For the ALNS, these values are up to three times higher and the GGA is up to 38% faster than the ALNS. <i>Conclusions</i>: It is shown that the BO, as a parameter tuning approach, is a good choice in improving the performance of the considered meta-heuristic over all instances in each data set. In addition, the best parameter configuration per problem class with the same characteristics is able to improve both the frequency of finding the best solution, as well as the relative error to this solution, significantly. |
| first_indexed | 2024-04-24T18:05:01Z |
| format | Article |
| id | doaj.art-980c5c09cb394228a647ff779b0863d1 |
| institution | Directory Open Access Journal |
| issn | 2305-6290 |
| language | English |
| last_indexed | 2024-04-24T18:05:01Z |
| publishDate | 2024-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Logistics |
| spelling | doaj.art-980c5c09cb394228a647ff779b0863d12024-03-27T13:51:35ZengMDPI AGLogistics2305-62902024-02-01811410.3390/logistics8010014A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery ProblemsCornelius Rüther0Julia Rieck1Operations Research Department, Institute for Business Administration and Information Systems, University of Hildesheim, Universitätsplatz 1, 31141 Hildesheim, GermanyOperations Research Department, Institute for Business Administration and Information Systems, University of Hildesheim, Universitätsplatz 1, 31141 Hildesheim, Germany<i>Background</i>: The Multi Depot Pickup and Delivery Problem with Time Windows and Heterogeneous Vehicle Fleets (MDPDPTWHV) is a strongly practically oriented routing problem with many real-world constraints. Due to its complexity, solution approaches with sufficiently good quality ideally contain several operators with certain probabilities.Thus, automatically selecting the best parameter configurations enhances the overall solution quality. <i>Methods</i>: To solve the MDPDPTWHV, we present a Grouping Genetic Algorithm (GGA) framework with several operators and population management variants. A Bayesian Optimization (BO) approach is introduced to optimize the GGA’s parameter configuration. The parameter tuning is evaluated on five data sets which differ in several structural characteristics and contain 1200 problem instances. The outcomes of the parameter-tuned GGA are compared to both the initial GGA parameter configuration and a state-of-the-art Adaptive Large Neighborhood Search (ALNS). <i>Results</i>: The presented GGA framework achieves a better solution quality than the ALNS, even for the initial parameter configuration used. The mean value of the relative error is less than 0.9% and its standard deviation is less than 1.31% for every problem class. For the ALNS, these values are up to three times higher and the GGA is up to 38% faster than the ALNS. <i>Conclusions</i>: It is shown that the BO, as a parameter tuning approach, is a good choice in improving the performance of the considered meta-heuristic over all instances in each data set. In addition, the best parameter configuration per problem class with the same characteristics is able to improve both the frequency of finding the best solution, as well as the relative error to this solution, significantly.https://www.mdpi.com/2305-6290/8/1/14automatic algorithm configurationblack box optimizationGaussian processesmachine learning model |
| spellingShingle | Cornelius Rüther Julia Rieck A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery Problems Logistics automatic algorithm configuration black box optimization Gaussian processes machine learning model |
| title | A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery Problems |
| title_full | A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery Problems |
| title_fullStr | A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery Problems |
| title_full_unstemmed | A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery Problems |
| title_short | A Bayesian Optimization Approach for Tuning a Grouping Genetic Algorithm for Solving Practically Oriented Pickup and Delivery Problems |
| title_sort | bayesian optimization approach for tuning a grouping genetic algorithm for solving practically oriented pickup and delivery problems |
| topic | automatic algorithm configuration black box optimization Gaussian processes machine learning model |
| url | https://www.mdpi.com/2305-6290/8/1/14 |
| work_keys_str_mv | AT corneliusruther abayesianoptimizationapproachfortuningagroupinggeneticalgorithmforsolvingpracticallyorientedpickupanddeliveryproblems AT juliarieck abayesianoptimizationapproachfortuningagroupinggeneticalgorithmforsolvingpracticallyorientedpickupanddeliveryproblems AT corneliusruther bayesianoptimizationapproachfortuningagroupinggeneticalgorithmforsolvingpracticallyorientedpickupanddeliveryproblems AT juliarieck bayesianoptimizationapproachfortuningagroupinggeneticalgorithmforsolvingpracticallyorientedpickupanddeliveryproblems |