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

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.