Integer linear programming and the vehicle routing problem

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.