European Master's Program in Computational Logic

Search:
05 December 2016

Master Thesis defence by Mr Rafael Mejia Santana

Mr Rafael Mejia Santana defended his master thesis on 'Heuristic Algorithms and Variants of the Vehicle Routing Problem for a Distribution Company: A Case Study'


Mr Rafael Mejia Santana defended his master thesis on 'Heuristic Algorithms and Variants of the Vehicle Routing Problem for a Distribution Company: A Case Study' at NOVA on 12 October 2016.

Abstract:This thesis addresses a problem with extreme importance to companies around the world in the domains of transportation, distribution and logistics: the Vehicle Routing Problem (VRP). The main idea consists in determine a set of vehicle trips, called routes, with the minimum total cost, in which the depot is the point of departure and point of arrival of each vehicle and a set of cities or customers are visited at least once. The VRP is considered a combinatorial optimization problem for optimal delivery.
Since the problem we are tackling represents a real-world application, it is necessary to take into account different attributes of vehicle routing problems, that is to say, additional characteristics and constraints that aim to give a more accurate picture of the situation. Among the additional constraints we considered those arising from legislation and transit laws in Portugal, break time for drivers, time windows and capacity characteristics. In this work, we have implemented some methods for combinatorial optimization problems combining Clustering techniques, Constraint Programming and Local Search heuristics to obtain weekly plans for the distribution fleet of the company and design a "winning strategy" for MAVRPs.