A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows. (April 2019) - Pérez-Rodríguez, Ricardo; Hernández-Aguirre, Arturo
Highlights: A new way of estimating an probability distribution for routing problems. The Mallows distribution solves vehicle routing problems efficiently. A Pareto-front approach helps to find better solutions for routing problems. An effective estimate of the vertices at the positions in the routing sequence. A new option for routing problems, called route-first cluster-second. Abstract: The Vehicle Routing Problem (VRP) seeks to find minimum-travel routes for a set of vehicles. The routes contain a set of customers with known demands. Each vehicle departs and arrives at the same depot. In the vehicle routing problem with time windows (VRPTW), each vehicle has to arrive in a specific time window with each customer and also each vehicle has to return to the depot before a due time. In this research, the use of an estimation of distribution algorithm to solve the problem is proposed. The algorithm uses the generalized Mallows distribution as a probability model to describe the distribution of the solution space. Homberger-Gehring's instances are used as input and test parameters in order to show that the modification of the generalized Mallows distribution mentioned is able to produce competitive sequences for the VRPTW against some other estimation of distribution algorithms used in permutation-based optimization problems.