Analyzing the Performance of a Hybrid Heuristic for Solving a Bilevel Location Problem under Different Approaches to Tackle the Lower Level
The problem addressed here is a combinatorial bilevel programming problem called the uncapacitated facility location problem with customer’s preferences. A hybrid algorithm is developed for solving a battery of benchmark instances. The algorithm hybridizes an evolutionary algorithm with path relin...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2016
|
| Online Access: | http://eprints.uanl.mx/14843/1/63.pdf |
| _version_ | 1824414160419553280 |
|---|---|
| author | Maldonado Pinto, Carmen Sayuri Casas Ramírez, Martha Selene Camacho Vallejo, José Fernando |
| author_facet | Maldonado Pinto, Carmen Sayuri Casas Ramírez, Martha Selene Camacho Vallejo, José Fernando |
| author_sort | Maldonado Pinto, Carmen Sayuri |
| collection | Repositorio Institucional |
| description | The problem addressed here is a combinatorial bilevel programming problem called the uncapacitated facility location problem
with customer’s preferences. A hybrid algorithm is developed for solving a battery of benchmark instances. The algorithm
hybridizes an evolutionary algorithm with path relinking; the latter procedure is added into the crossover phase for exploring the
trajectory between both parents. The proposed algorithm outperforms the evolutionary algorithm already existing in the literature.
Results show that including a more sophisticated procedure for improving the population through the generations accelerates the
convergence of the algorithm. In order to support the latter statement, a reduction of around the half of the computational time is
obtained by using the hybrid algorithm. Moreover, due to the nature of bilevel problems, if feasible solutions are desired, then the
lower level must be solved for each change in the upper level’s current solution. A study for illustrating the impact in the algorithm’s
performance when solving the lower level through three different exact or heuristic approaches is made. |
| format | Article |
| id | eprints-14843 |
| institution | UANL |
| language | English |
| publishDate | 2016 |
| record_format | eprints |
| spelling | eprints-148432019-08-27T16:52:35Z http://eprints.uanl.mx/14843/ Analyzing the Performance of a Hybrid Heuristic for Solving a Bilevel Location Problem under Different Approaches to Tackle the Lower Level Maldonado Pinto, Carmen Sayuri Casas Ramírez, Martha Selene Camacho Vallejo, José Fernando The problem addressed here is a combinatorial bilevel programming problem called the uncapacitated facility location problem with customer’s preferences. A hybrid algorithm is developed for solving a battery of benchmark instances. The algorithm hybridizes an evolutionary algorithm with path relinking; the latter procedure is added into the crossover phase for exploring the trajectory between both parents. The proposed algorithm outperforms the evolutionary algorithm already existing in the literature. Results show that including a more sophisticated procedure for improving the population through the generations accelerates the convergence of the algorithm. In order to support the latter statement, a reduction of around the half of the computational time is obtained by using the hybrid algorithm. Moreover, due to the nature of bilevel problems, if feasible solutions are desired, then the lower level must be solved for each change in the upper level’s current solution. A study for illustrating the impact in the algorithm’s performance when solving the lower level through three different exact or heuristic approaches is made. 2016 Article PeerReviewed text en cc_by_nc_nd http://eprints.uanl.mx/14843/1/63.pdf http://eprints.uanl.mx/14843/1.haspreviewThumbnailVersion/63.pdf Maldonado Pinto, Carmen Sayuri y Casas Ramírez, Martha Selene y Camacho Vallejo, José Fernando (2016) Analyzing the Performance of a Hybrid Heuristic for Solving a Bilevel Location Problem under Different Approaches to Tackle the Lower Level. Mathematical Problems in Engineering, 2016. pp. 1-10. ISSN 1024-123X http://doi.org/10.1155/2016/9109824 doi:10.1155/2016/9109824 |
| spellingShingle | Maldonado Pinto, Carmen Sayuri Casas Ramírez, Martha Selene Camacho Vallejo, José Fernando Analyzing the Performance of a Hybrid Heuristic for Solving a Bilevel Location Problem under Different Approaches to Tackle the Lower Level |
| thumbnail | https://rediab.uanl.mx/themes/sandal5/images/online.png |
| title | Analyzing the Performance of a Hybrid Heuristic for Solving a Bilevel Location Problem under Different Approaches to Tackle the Lower Level |
| title_full | Analyzing the Performance of a Hybrid Heuristic for Solving a Bilevel Location Problem under Different Approaches to Tackle the Lower Level |
| title_fullStr | Analyzing the Performance of a Hybrid Heuristic for Solving a Bilevel Location Problem under Different Approaches to Tackle the Lower Level |
| title_full_unstemmed | Analyzing the Performance of a Hybrid Heuristic for Solving a Bilevel Location Problem under Different Approaches to Tackle the Lower Level |
| title_short | Analyzing the Performance of a Hybrid Heuristic for Solving a Bilevel Location Problem under Different Approaches to Tackle the Lower Level |
| title_sort | analyzing the performance of a hybrid heuristic for solving a bilevel location problem under different approaches to tackle the lower level |
| url | http://eprints.uanl.mx/14843/1/63.pdf |
| work_keys_str_mv | AT maldonadopintocarmensayuri analyzingtheperformanceofahybridheuristicforsolvingabilevellocationproblemunderdifferentapproachestotacklethelowerlevel AT casasramirezmarthaselene analyzingtheperformanceofahybridheuristicforsolvingabilevellocationproblemunderdifferentapproachestotacklethelowerlevel AT camachovallejojosefernando analyzingtheperformanceofahybridheuristicforsolvingabilevellocationproblemunderdifferentapproachestotacklethelowerlevel |