Advanced search
Start date

Integer linear programming and the vehicle routing problem

Grant number: 20/06105-2
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): August 01, 2020
Effective date (End): July 31, 2021
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Mário César San Felice
Grantee:Guilherme Gomes Arcencio
Home Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil


The Vehicle Routing Problem involves finding a set of routes, which minimizes the overall costs, for a fleet of vehicles to traverse in order to serve a given set of customers. The problem is very important to industry, since it is useful for modeling logistical problems such as product distribution and people transportation. This project aims to study and develop exact algorithms for this problem, employing Integer Linear Programming.Another problem this project intends to tackle using Integer Linear Programming is the one-dimensional Bin Packing Problem. It is also related to industry, modeling problems such as storage and cutting stock. Because the Bin Packing Problem has a simpler formulation, it will be used as an intermediary problem for the study of Integer Linear Programming.We also seek to study algorithms to solve linear programs, like the Simplex, and integer linear programs, like the Branch-and-Bound.As a scientific initiation, this projects seeks to introduce the candidate to scientific research and to complement his educational background in Computer Engineering, as well as to produce an article compiling the achieved results.