This study is carried out in a commercial company with a chain of convenience stores. The initial phase of the diagnosis aims to introduce the problem, show the analysis made on the process, and finally to identify the root causes of the problem. The key solution was to create a two-phase model which includes an allocation of stores by demand and vehicle capacity and a time optimization model of the routes. Vehicle routing problems are usually optimized in function of the length of the resulting routes. These functions are expressed in terms of distance, time, fuel consumption, cost, emissions, etc. In this case, the cost of the route is given by the most expensive customer covered in such a route. In addition, the models proposed consider time windows constraints and heterogeneous fleet.

All the necessary documentation under the company's scheme to implement the two-phase model and reduce travel expenses was developed This includes the restructuring of the daily route calculation and planning process with new contract terms and conditions that ensure greater benefits for the company. The results after the pilot test and simulations were a 16% reduction in final travel expenses and vehicle occupancy increased from 63% to 85%.