Optimization algorithms for the vehicle routing problem

• Grant number: 16/08481-6
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: July 01, 2016
• End date: March 19, 2017
• Field of knowledge: Physical Sciences and Mathematics - Computer Science
• Principal Investigator: Luis Augusto Angelotti Meira
• Grantee: Rodrigo Rosatti Galvão
• Host Institution: Faculdade de Tecnologia (FT). Universidade Estadual de Campinas (UNICAMP). Limeira , SP, Brazil

Abstract

This project aims to develop efficient algorithms for vehicle routing problem in a road network. When a vehicle receives a set of delivery points, it must use an optimized route, minimizing the distance traveled or total time. This is the classic Traveling Salesman Problem (TSP). However, when there is more than one vehicle, the problem has two phases: (I) to partition the delivery points and (II) for each set, to resolve a TSP. The goal is to find a global minimum for the two phases. This TSP generalization may receive additional requirements such as vehicle capacity and delivery time windows. The resulting problem is the Vehicle Routing Problem (VRP). This scientific research will be devoted to the design algorithm for the VRP optimization. The student will use a variety of optimization techniques in order to find good solutions in appropriate computational time. At the end of scientific research, it is expected that student has formed solid knowledge in the areas of mathematical programming, optimization and vehicle routing problems. (AU)