WSEAS Transactions on Computer Research
Print ISSN: 1991-8755, E-ISSN: 2415-1521
Volume 7, 2019
Approach based on Reduction the State Space to Solve the Vehicle Routing Problem
Authors: ,
Abstract: We are interested in problems from combinatorial optimization, more precisely, the vehicle routing problem with resource constraints. Given the large size of the problems encountered in practice, these models are solved by an approach based on column generation that can handle implicitly all feasible solutions and a master problem determining the best solution. We propose in this paper an approach to improve the acceleration of the method of column generation for solving the problem of construction vehicle routing, it is projected in each arc, the resources a vector of size smaller by using a Lagrangean relaxation algorithm to determine the coefficients of the projection arc combined with an algorithm for re-optimization, then generates a sub-set of complementary solutions to the master problem. The preliminary experiments of our technique gave good results on instances of random vehicle routing.
Search Articles
Keywords: Vehicle routing problem, path problems in graphs, decomposition methods, column generation
Pages: 41-45
WSEAS Transactions on Computer Research, ISSN / E-ISSN: 1991-8755 / 2415-1521, Volume 7, 2019, Art. #6