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

Authors

  • Pedro Ballesteros Silva Universidad Tecnológica de Pereira
  • Antonio Escobar Zuluaga Universidad Tecnológica de Pereira
  • Diana Ballesteros Riveros Universidad Tecnológica de Pereira

Keywords:

genetic algorithm's Chu-Beasley, branch-and-cut, capacity, pick-up and delivery, heuristics, optimization, vehicles routing, exact techniques.

Abstract

 

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.

Downloads

Download data is not yet available.

Downloads

Issue

Section

Artículos Científicos

How to Cite

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. (2018). Revista De La Escuela De Perfeccionamiento En Investigación Operativa, 26(44), 21-40. https://revistas.psi.unc.edu.ar/index.php/epio/article/view/22216