Integer linear programming and the vehicle routing problem

• Grant number: 20/06105-2
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2020
• End date: 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
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil

Abstract

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.