This was the second project Asteroide worked on during his summer internship at Opex Analytics in 2018.
There was a warehouse that served hundreds of stores. Everyday, the warehouse had to fulfill demand from about 50 stores. Trucks were outsourced from six companies. Each company had different prices and restrictions. For example, some companies would not deliver to certain states or would not accept certain type of routes. The goal was to assign orders to trucks, and trucks to routes, as to meet all the demand and minimize total cost. This problem can be seen as a variant of the standard travelling salesman problem (TSP), one of the most challenging problem in mixed integer linear programming (MILP).
Aster implemented a set covering algorithm and a few specialized heuristics. His proposed heuristics would run way faster than the deterministic counterpart and consider routes with any number of stops. Most importantly, he demonstrated trough experiments that the proposed heuristics yield near-optimal solutions for the instances of interest. At the end of that summer, he had a robust program to solve this type of vehicle routing problems, which was intend to be used in other projects.