A comparison of probabilistic-based optimization approaches for vehicle routing problems
Authors:
- 1 June 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 7, 2606-2613
Abstract
Estimation of distribution algorithms (EDAs) are evolutionary algorithms that use probabilistic modeling to lead a more efficient search for optimal solutions. While EDAs have been applied to several types of optimization problems, they exhibit some limitations to deal with constrained optimization problems. More study and understanding of how can EDAs deal with these problems is required. In this paper we investigate the application of EDAs to a version of the vehicle routing problem in which solutions should satisfy a number of constraints involving the customers, the fleet vehicle, and the items to be delivered. For this problem, we compare two different representations of the solutions, and apply EDAs that use three probabilistic models with different characteristics. Our results show that the combination of an integer representation with tree-based probabilistic model produces the best results and is able to solve vehicle routing problems that contain over thousands of promising paths.Keywords
This publication has 21 references indexed in Scilit:
- Network measures for information extraction in evolutionary algorithmsInternational Journal of Computational Intelligence Systems, 2013
- A review on probabilistic graphical models in evolutionary computationJournal of Heuristics, 2012
- A review on estimation of distribution algorithms in permutation-based combinatorial optimization problemsProgress in Artificial Intelligence, 2012
- Univariate marginal distribution algorithm dynamics for a class of parametric functions with unitation constraintsInformation Sciences, 2011
- Incorporating a priori Knowledge in Probabilistic-Model Based Optimization2006
- Evolutionary Algorithms for the Vehicle Routing Problem with Time WindowsJournal of Heuristics, 2004
- A simple and effective evolutionary algorithm for the vehicle routing problemComputers & Operations Research, 2004
- Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the artComputer Methods in Applied Mechanics and Engineering, 2002
- Evolutionary Algorithms and Constraint Satisfaction: Definitions, Survey, Methodology, and Research Directions2001
- Routing and scheduling of vehicles and crewsComputers & Operations Research, 1983