methodology to solve the problem of vehicle routing with simultaneous deliveries and collections - VRPSPD using the genetic algorithm of Chu - Beasley combined with exact techniques

 This article presents a methodology to solve the homogeneous vehicles routing problem with simultaneous pickups and deliveries (VRPSPD) using matheuristics formed by the specialized genetic algorithm's Chu-Beasley and exact techniques of mixed integer linear programming, based on the Branch-an...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Ballesteros Silva, Pedro, Escobar Zuluaga, Antonio, Ballesteros Riveros, Diana
Formato: Artículo revista
Lenguaje:Español
Publicado: Escuela de Perfeccionamiento en Investigación Operativa 2018
Materias:
algoritmo genético de Chu Beasley
branch-and-cut
capacidad
entregas y recogidas
heurísticas
optimización
ruteo de vehículos
técnicas exactas
genetic algorithm's Chu-Beasley
capacity
pick-up and delivery
heuristics
optimization
vehicles routing
exact techniques.
Acceso en línea:https://revistas.unc.edu.ar/index.php/epio/article/view/22216
Aporte de:
Revista de la Escuela de Perfeccionamiento en Investigación Operativa de Universidad Nacional de Córdoba
id I10-R359-article-22216
record_format ojs
spelling I10-R359-article-222162018-12-03T15:49:27Z methodology to solve the problem of vehicle routing with simultaneous deliveries and collections - VRPSPD using the genetic algorithm of Chu - Beasley combined with exact techniques Metodología para resolver el problema de ruteo de vehículos con entregas y recogidas simultáneas - VRPSPD utilizando el algoritmo genético de Chu – Beasley combinado con técnicas exactas Ballesteros Silva, Pedro Escobar Zuluaga, Antonio Ballesteros Riveros, Diana algoritmo genético de Chu Beasley branch-and-cut capacidad entregas y recogidas heurísticas optimización ruteo de vehículos técnicas exactas genetic algorithm's Chu-Beasley branch-and-cut capacity pick-up and delivery heuristics optimization vehicles routing exact techniques.  This article presents a methodology to solve the homogeneous vehicles routing problem with simultaneous pickups and deliveries (VRPSPD) using matheuristics formed by the specialized genetic algorithm's Chu-Beasley and exact techniques of mixed integer linear programming, based on the Branch-and-Bound procedure, applied to the best configuration obtained from the genetic algorithm with the support of constructive heuristic methods in the determination of the sub problems, which make part of the generation of the initial population, necessary in the stage of local improvement.The problem considers a set of customers, whose demands of pick-up and delivery of products or people are known, and whose objective is to get the set of routes of minimal cost, which permit to satisfy the demand of the customers, considering the respective constraints of the system and the vehicles necessary for the completion of the same.The methodology developed is implemented in C++, GAMS (algebraic modeling language) and Java. Solver CPLEX (optimization software package that helps solve the problem encoded in GAMS). The efficiency of the implementation of the algorithm is verified with the use of test instances available in the specialized literature, getting good results in relatively short computing times. En este artículo se presenta una metodología para resolver el problema de ruteo de vehículos homogéneos con entregas y recogidas simultáneas (VRPSPD) utilizando una matheurística, conformada por el algoritmo genético especializado de Chu-Beasley  y técnicas exactas de programación lineal entera mixta, basadas en el procedimiento de Branch-and-Cut,  aplicadas a la mejor configuración obtenida del algoritmo genético,  con el apoyo de métodos heurísticos constructivos en la determinación de los subproblemas, que hacen parte de la generación de la población inicial y son necesarios en la etapa de mejoría local.              El problema considera un conjunto de clientes, cuyas demandas de recogida y entrega de productos o personas son conocidas y su objetivo es obtener el conjunto de rutas de costo mínimo, que permita satisfacer la demanda de los clientes, considerando las respectivas restricciones del sistema y los vehículos necesarios para la realización de las mismas.La metodología desarrollada se implementa en C++, GAMS (lenguaje de modelado algebraico) y Java. Para encontrar la solución se dispone del software solver CPLEX (paquete de software de optimización que ayuda a resolver el problema codificado en GAMS). La eficiencia de la implementación del algoritmo se verifica con la utilización de instancias de prueba disponibles en la literatura especializada, obteniendo buenos resultados en tiempos de cómputo relativamente cortos. Escuela de Perfeccionamiento en Investigación Operativa 2018-11-30 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion application/pdf https://revistas.unc.edu.ar/index.php/epio/article/view/22216 Revista de la Escuela de Perfeccionamiento en Investigación Operativa; Vol. 26 Núm. 44 (2018): Noviembre; 21-40 1853-9777 0329-7322 spa https://revistas.unc.edu.ar/index.php/epio/article/view/22216/21817
institution Universidad Nacional de Córdoba
institution_str I-10
repository_str R-359
container_title_str Revista de la Escuela de Perfeccionamiento en Investigación Operativa
language Español
format Artículo revista
topic algoritmo genético de Chu Beasley
branch-and-cut
capacidad
entregas y recogidas
heurísticas
optimización
ruteo de vehículos
técnicas exactas
genetic algorithm's Chu-Beasley
branch-and-cut
capacity
pick-up and delivery
heuristics
optimization
vehicles routing
exact techniques.
spellingShingle algoritmo genético de Chu Beasley
branch-and-cut
capacidad
entregas y recogidas
heurísticas
optimización
ruteo de vehículos
técnicas exactas
genetic algorithm's Chu-Beasley
branch-and-cut
capacity
pick-up and delivery
heuristics
optimization
vehicles routing
exact techniques.
Ballesteros Silva, Pedro
Escobar Zuluaga, Antonio
Ballesteros Riveros, Diana
methodology to solve the problem of vehicle routing with simultaneous deliveries and collections - VRPSPD using the genetic algorithm of Chu - Beasley combined with exact techniques
topic_facet algoritmo genético de Chu Beasley
branch-and-cut
capacidad
entregas y recogidas
heurísticas
optimización
ruteo de vehículos
técnicas exactas
genetic algorithm's Chu-Beasley
branch-and-cut
capacity
pick-up and delivery
heuristics
optimization
vehicles routing
exact techniques.
author Ballesteros Silva, Pedro
Escobar Zuluaga, Antonio
Ballesteros Riveros, Diana
author_facet Ballesteros Silva, Pedro
Escobar Zuluaga, Antonio
Ballesteros Riveros, Diana
author_sort Ballesteros Silva, Pedro
title methodology to solve the problem of vehicle routing with simultaneous deliveries and collections - VRPSPD using the genetic algorithm of Chu - Beasley combined with exact techniques
title_short methodology to solve the problem of vehicle routing with simultaneous deliveries and collections - VRPSPD using the genetic algorithm of Chu - Beasley combined with exact techniques
title_full methodology to solve the problem of vehicle routing with simultaneous deliveries and collections - VRPSPD using the genetic algorithm of Chu - Beasley combined with exact techniques
title_fullStr methodology to solve the problem of vehicle routing with simultaneous deliveries and collections - VRPSPD using the genetic algorithm of Chu - Beasley combined with exact techniques
title_full_unstemmed methodology to solve the problem of vehicle routing with simultaneous deliveries and collections - VRPSPD using the genetic algorithm of Chu - Beasley combined with exact techniques
title_sort methodology to solve the problem of vehicle routing with simultaneous deliveries and collections - vrpspd using the genetic algorithm of chu - beasley combined with exact techniques
description  This article presents a methodology to solve the homogeneous vehicles routing problem with simultaneous pickups and deliveries (VRPSPD) using matheuristics formed by the specialized genetic algorithm's Chu-Beasley and exact techniques of mixed integer linear programming, based on the Branch-and-Bound procedure, applied to the best configuration obtained from the genetic algorithm with the support of constructive heuristic methods in the determination of the sub problems, which make part of the generation of the initial population, necessary in the stage of local improvement.The problem considers a set of customers, whose demands of pick-up and delivery of products or people are known, and whose objective is to get the set of routes of minimal cost, which permit to satisfy the demand of the customers, considering the respective constraints of the system and the vehicles necessary for the completion of the same.The methodology developed is implemented in C++, GAMS (algebraic modeling language) and Java. Solver CPLEX (optimization software package that helps solve the problem encoded in GAMS). The efficiency of the implementation of the algorithm is verified with the use of test instances available in the specialized literature, getting good results in relatively short computing times.
publisher Escuela de Perfeccionamiento en Investigación Operativa
publishDate 2018
url https://revistas.unc.edu.ar/index.php/epio/article/view/22216
work_keys_str_mv AT ballesterossilvapedro methodologytosolvetheproblemofvehicleroutingwithsimultaneousdeliveriesandcollectionsvrpspdusingthegeneticalgorithmofchubeasleycombinedwithexacttechniques
AT escobarzuluagaantonio methodologytosolvetheproblemofvehicleroutingwithsimultaneousdeliveriesandcollectionsvrpspdusingthegeneticalgorithmofchubeasleycombinedwithexacttechniques
AT ballesterosriverosdiana methodologytosolvetheproblemofvehicleroutingwithsimultaneousdeliveriesandcollectionsvrpspdusingthegeneticalgorithmofchubeasleycombinedwithexacttechniques
AT ballesterossilvapedro metodologiapararesolverelproblemaderuteodevehiculosconentregasyrecogidassimultaneasvrpspdutilizandoelalgoritmogeneticodechubeasleycombinadocontecnicasexactas
AT escobarzuluagaantonio metodologiapararesolverelproblemaderuteodevehiculosconentregasyrecogidassimultaneasvrpspdutilizandoelalgoritmogeneticodechubeasleycombinadocontecnicasexactas
AT ballesterosriverosdiana metodologiapararesolverelproblemaderuteodevehiculosconentregasyrecogidassimultaneasvrpspdutilizandoelalgoritmogeneticodechubeasleycombinadocontecnicasexactas
first_indexed 2024-09-03T22:23:24Z
last_indexed 2024-09-03T22:23:24Z
_version_ 1809215342223818752

Ejemplares similares