Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario (Comparative analysis of a metaheuristic based on a genetic algorithm versus a branch & cut method for a pickup and delivery problem with time windows constraints)
En la solución de problemas combinatorios, es importante evaluar el costo-beneficio entre la obtención de soluciones de alta calidad en detrimento de los recursos computacionales requeridos. El problema planteado es para el ruteo de un vehículo con entrega y recolección de producto y con restriccio...
| Autor principal: | |
|---|---|
| Formato: | Artículo |
| Lenguaje: | Spanish / Castilian |
| Publicado: |
UANL Facultad de Contaduría Pública y Administración
2004
|
| Materias: | |
| Acceso en línea: | http://eprints.uanl.mx/12375/1/analisis%20comparativo%20de%20una%20metahuristica%20en%20base%20a%20algoritmo%20genetico%20vs%20un%20metodo%20de%20ramificacion%20y%20corte%20para%20un%20caso%20de%20entrega%20y%20recoleccion%20con%20restricciones%20de%20ventana%20de%20horario.pdf |
| _version_ | 1824413500786606080 |
|---|---|
| author | López, Fabián |
| author_facet | López, Fabián |
| author_sort | López, Fabián |
| collection | Repositorio Institucional |
| description | En la solución de problemas combinatorios, es importante evaluar el costo-beneficio entre la obtención de soluciones de alta calidad en detrimento de los recursos computacionales requeridos. El problema planteado es para el ruteo de un vehículo con entrega y recolección de
producto y con restricciones de ventana de horario. En la práctica, dicho problema requiere ser atendido con instancias de gran escala (nodos ≥100). Existe un fuerte porcentaje de ventanas de horario activas (≥90%) y con factores de amplitud ≥75%. El problema es NP-hard y por tal motivo la aplicación de un método de solución exacta para resolverlo en la práctica, está limitado por el
tiempo requerido para la actividad de ruteo. Se propone un algoritmo genético especializado, el cual ofrece soluciones de buena calidad (% de optimalidad aceptables) y en tiempos de ejecución computacional que hacen útil su aplicación en la práctica de la logística. Para comprobar la eficacia de la propuesta algorítmica se desarrolla un diseño experimental el cual hará uso de las soluciones óptimas obtenidas mediante un algoritmo de ramificación y corte sin límite de tiempo. Los resultados son favorables.
In an attempt to sovle the combinatorics problems, it is important to evaluate the costbenefit ratio between obtaining solutions of high quality and the loss of the computational resources required. The problem presented is for the routing of a vehicle with pickup and delivery
of products with time window constraints. This problem requires instances of great scale (nodes≥100). A strong active time window percentage exists (≥90%) with factors of amplitude ≥75%. The problem is NP-hard and hence, the application of an exact method of solution, is limited by the time frame required for routing activity. A specialized genetic algorithm is proposed, which offers solutions of high precision and in computational times that makes its practical
application useful. An experimental design is developed with good results that makes use of
optimum solutions obtained by means of branch and cut algorithm without time limit. |
| format | Article |
| id | eprints-12375 |
| institution | UANL |
| language | Spanish / Castilian |
| publishDate | 2004 |
| publisher | UANL Facultad de Contaduría Pública y Administración |
| record_format | eprints |
| spelling | eprints-123752020-05-22T21:47:25Z http://eprints.uanl.mx/12375/ Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario (Comparative analysis of a metaheuristic based on a genetic algorithm versus a branch & cut method for a pickup and delivery problem with time windows constraints) López, Fabián HA Estadistícas En la solución de problemas combinatorios, es importante evaluar el costo-beneficio entre la obtención de soluciones de alta calidad en detrimento de los recursos computacionales requeridos. El problema planteado es para el ruteo de un vehículo con entrega y recolección de producto y con restricciones de ventana de horario. En la práctica, dicho problema requiere ser atendido con instancias de gran escala (nodos ≥100). Existe un fuerte porcentaje de ventanas de horario activas (≥90%) y con factores de amplitud ≥75%. El problema es NP-hard y por tal motivo la aplicación de un método de solución exacta para resolverlo en la práctica, está limitado por el tiempo requerido para la actividad de ruteo. Se propone un algoritmo genético especializado, el cual ofrece soluciones de buena calidad (% de optimalidad aceptables) y en tiempos de ejecución computacional que hacen útil su aplicación en la práctica de la logística. Para comprobar la eficacia de la propuesta algorítmica se desarrolla un diseño experimental el cual hará uso de las soluciones óptimas obtenidas mediante un algoritmo de ramificación y corte sin límite de tiempo. Los resultados son favorables. In an attempt to sovle the combinatorics problems, it is important to evaluate the costbenefit ratio between obtaining solutions of high quality and the loss of the computational resources required. The problem presented is for the routing of a vehicle with pickup and delivery of products with time window constraints. This problem requires instances of great scale (nodes≥100). A strong active time window percentage exists (≥90%) with factors of amplitude ≥75%. The problem is NP-hard and hence, the application of an exact method of solution, is limited by the time frame required for routing activity. A specialized genetic algorithm is proposed, which offers solutions of high precision and in computational times that makes its practical application useful. An experimental design is developed with good results that makes use of optimum solutions obtained by means of branch and cut algorithm without time limit. UANL Facultad de Contaduría Pública y Administración 2004-07 Article PeerReviewed text es cc_by_nc_nd http://eprints.uanl.mx/12375/1/analisis%20comparativo%20de%20una%20metahuristica%20en%20base%20a%20algoritmo%20genetico%20vs%20un%20metodo%20de%20ramificacion%20y%20corte%20para%20un%20caso%20de%20entrega%20y%20recoleccion%20con%20restricciones%20de%20ventana%20de%20horario.pdf http://eprints.uanl.mx/12375/1.haspreviewThumbnailVersion/analisis%20comparativo%20de%20una%20metahuristica%20en%20base%20a%20algoritmo%20genetico%20vs%20un%20metodo%20de%20ramificacion%20y%20corte%20para%20un%20caso%20de%20entrega%20y%20recoleccion%20con%20restricciones%20de%20ventana%20de%20horario.pdf López, Fabián (2004) Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario (Comparative analysis of a metaheuristic based on a genetic algorithm versus a branch & cut method for a pickup and delivery problem with time windows constraints). Innovaciones de negocios, 1 (2). pp. 229-243. ISSN 2007-1191 http://www.web.facpya.uanl.mx/rev_in/Revistas/1.2/A4.pdf |
| spellingShingle | HA Estadistícas López, Fabián Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario (Comparative analysis of a metaheuristic based on a genetic algorithm versus a branch & cut method for a pickup and delivery problem with time windows constraints) |
| thumbnail | https://rediab.uanl.mx/themes/sandal5/images/online.png |
| title | Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario (Comparative analysis of a metaheuristic based on a genetic algorithm versus a branch & cut method for a pickup and delivery problem with time windows constraints) |
| title_full | Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario (Comparative analysis of a metaheuristic based on a genetic algorithm versus a branch & cut method for a pickup and delivery problem with time windows constraints) |
| title_fullStr | Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario (Comparative analysis of a metaheuristic based on a genetic algorithm versus a branch & cut method for a pickup and delivery problem with time windows constraints) |
| title_full_unstemmed | Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario (Comparative analysis of a metaheuristic based on a genetic algorithm versus a branch & cut method for a pickup and delivery problem with time windows constraints) |
| title_short | Análisis comparativo de una metaheurística en base a algoritmo genético vs un método de ramificación y corte para un caso de entrega y recolección con restricciones de ventana de horario (Comparative analysis of a metaheuristic based on a genetic algorithm versus a branch & cut method for a pickup and delivery problem with time windows constraints) |
| title_sort | analisis comparativo de una metaheuristica en base a algoritmo genetico vs un metodo de ramificacion y corte para un caso de entrega y recoleccion con restricciones de ventana de horario comparative analysis of a metaheuristic based on a genetic algorithm versus a branch cut method for a pickup and delivery problem with time windows constraints |
| topic | HA Estadistícas |
| url | http://eprints.uanl.mx/12375/1/analisis%20comparativo%20de%20una%20metahuristica%20en%20base%20a%20algoritmo%20genetico%20vs%20un%20metodo%20de%20ramificacion%20y%20corte%20para%20un%20caso%20de%20entrega%20y%20recoleccion%20con%20restricciones%20de%20ventana%20de%20horario.pdf |
| work_keys_str_mv | AT lopezfabian analisiscomparativodeunametaheuristicaenbaseaalgoritmogeneticovsunmetododeramificacionycorteparauncasodeentregayrecoleccionconrestriccionesdeventanadehorariocomparativeanalysisofametaheuristicbasedonageneticalgorithmversusabranchcutmethodforapickupanddeli |