A partial evaluation approach for the School Bus Routing Problem
Several real-life optimization problems, such as the case of several instances of the School Bus Routing Problem (SBRP), are very complex and expensive to solve with exact algorithms. Metaheuristics are a good alternative in these situations because they are capable of generating good quality soluti...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2022-04-01
|
| Series: | Heliyon |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2405844022005795 |
| _version_ | 1811289391332589568 |
|---|---|
| author | Ana Camila Pérez Eduardo Sánchez-Ansola Alejandro Rosete Omar Rojas Guillermo Sosa-Gómez |
| author_facet | Ana Camila Pérez Eduardo Sánchez-Ansola Alejandro Rosete Omar Rojas Guillermo Sosa-Gómez |
| author_sort | Ana Camila Pérez |
| collection | DOAJ |
| description | Several real-life optimization problems, such as the case of several instances of the School Bus Routing Problem (SBRP), are very complex and expensive to solve with exact algorithms. Metaheuristics are a good alternative in these situations because they are capable of generating good quality solutions to these problems in a reasonable time. Metaheuristics iterate thousands of times by introducing changes concerning the previous solutions. Each new solution must be evaluated, and sometimes, the new solutions have elements unchanged that are unnecessarily re-evaluated. However, an approach avoids repeatedly evaluating parts of different solutions known as partial evaluation. This work applies this technique to the SBRP to reduce its execution time. To apply the partial evaluation approach in this problem, each solution contains the information of the change that was made concerning the solution from which it originates. With this information, when evaluating the objective function, it will be only necessary to analyze the routes that changed. In the literature reviewed, no previous work was found in which the partial evaluation approach has been applied in the context of SBRP. In this paper we apply it in order to reduce the computational cost of SBRP solutions based on metaheuristics. The results show that it is possible to decrease the execution time in 80% of the instances, reducing the execution time on average by 73.6%. |
| first_indexed | 2024-04-13T03:54:19Z |
| format | Article |
| id | doaj.art-130c6d5e5173482abe8237c509117d13 |
| institution | Directory Open Access Journal |
| issn | 2405-8440 |
| language | English |
| last_indexed | 2024-04-13T03:54:19Z |
| publishDate | 2022-04-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Heliyon |
| spelling | doaj.art-130c6d5e5173482abe8237c509117d132022-12-22T03:03:41ZengElsevierHeliyon2405-84402022-04-0184e09291A partial evaluation approach for the School Bus Routing ProblemAna Camila Pérez0Eduardo Sánchez-Ansola1Alejandro Rosete2Omar Rojas3Guillermo Sosa-Gómez4Universidad Tecnológica de La Habana José Antonio Echeverría (Cujae), Facultad de Informática, 19390, Habana, CubaUniversidad Tecnológica de La Habana José Antonio Echeverría (Cujae), Facultad de Informática, 19390, Habana, CubaUniversidad Tecnológica de La Habana José Antonio Echeverría (Cujae), Facultad de Informática, 19390, Habana, CubaUniversidad Panamericana, Facultad de Ciencias Económicas y Empresariales, Álvaro del Portillo 49, Zapopan, 45010, Jalisco, Mexico; Faculty of Economics and Business, Universitas Airlangga, Surabaya, IndonesiaUniversidad Panamericana, Facultad de Ciencias Económicas y Empresariales, Álvaro del Portillo 49, Zapopan, 45010, Jalisco, Mexico; Corresponding author.Several real-life optimization problems, such as the case of several instances of the School Bus Routing Problem (SBRP), are very complex and expensive to solve with exact algorithms. Metaheuristics are a good alternative in these situations because they are capable of generating good quality solutions to these problems in a reasonable time. Metaheuristics iterate thousands of times by introducing changes concerning the previous solutions. Each new solution must be evaluated, and sometimes, the new solutions have elements unchanged that are unnecessarily re-evaluated. However, an approach avoids repeatedly evaluating parts of different solutions known as partial evaluation. This work applies this technique to the SBRP to reduce its execution time. To apply the partial evaluation approach in this problem, each solution contains the information of the change that was made concerning the solution from which it originates. With this information, when evaluating the objective function, it will be only necessary to analyze the routes that changed. In the literature reviewed, no previous work was found in which the partial evaluation approach has been applied in the context of SBRP. In this paper we apply it in order to reduce the computational cost of SBRP solutions based on metaheuristics. The results show that it is possible to decrease the execution time in 80% of the instances, reducing the execution time on average by 73.6%.http://www.sciencedirect.com/science/article/pii/S2405844022005795MetaheuristicsOptimizationPartial evaluationSBRP |
| spellingShingle | Ana Camila Pérez Eduardo Sánchez-Ansola Alejandro Rosete Omar Rojas Guillermo Sosa-Gómez A partial evaluation approach for the School Bus Routing Problem Heliyon Metaheuristics Optimization Partial evaluation SBRP |
| title | A partial evaluation approach for the School Bus Routing Problem |
| title_full | A partial evaluation approach for the School Bus Routing Problem |
| title_fullStr | A partial evaluation approach for the School Bus Routing Problem |
| title_full_unstemmed | A partial evaluation approach for the School Bus Routing Problem |
| title_short | A partial evaluation approach for the School Bus Routing Problem |
| title_sort | partial evaluation approach for the school bus routing problem |
| topic | Metaheuristics Optimization Partial evaluation SBRP |
| url | http://www.sciencedirect.com/science/article/pii/S2405844022005795 |
| work_keys_str_mv | AT anacamilaperez apartialevaluationapproachfortheschoolbusroutingproblem AT eduardosanchezansola apartialevaluationapproachfortheschoolbusroutingproblem AT alejandrorosete apartialevaluationapproachfortheschoolbusroutingproblem AT omarrojas apartialevaluationapproachfortheschoolbusroutingproblem AT guillermososagomez apartialevaluationapproachfortheschoolbusroutingproblem AT anacamilaperez partialevaluationapproachfortheschoolbusroutingproblem AT eduardosanchezansola partialevaluationapproachfortheschoolbusroutingproblem AT alejandrorosete partialevaluationapproachfortheschoolbusroutingproblem AT omarrojas partialevaluationapproachfortheschoolbusroutingproblem AT guillermososagomez partialevaluationapproachfortheschoolbusroutingproblem |