Optimization of a multi-depot routing for bottle banks rounds based on variable logistic constraints

Abstract

The management and collect of bottle banks is an essential task for the cleanliness of cities. Indeed, if poorly managed, the sites can quickly become dirty and attract pest which is problematic for the neighborhood. In addition to that, inefficient routing and thus inefficient collect lead to supplementary costs in terms of extra fuels and extra work hours. This thesis addresses this problem by focusing on the daily management of 70 bottle banks located in the province of Namur. The collection of those bottle banks are handled by a fleet of vehicles divided in several depots. Moreover, an additional constraint is imposed on the number of vehicles available in each depot. This thesis presents 3 multi-depots vehicle routing problem formulations to model the daily collect of bottle banks. Then, the Gurobi solver for integer programming is used to solve the different formulations. This solver computes the solution with a branch and bound(B&B) algorithm that uses heuristics and cutting planes. This particular method has the advantage to provide lower bounds to the optimal solution of the problem. In addition to that, feasible solutions can be found during the computation which can allow an early stopping if the solution is good enough. The 3 formulations are compared in terms of qualities and processing times with the best solution showing good results. Indeed, on the worst case of the problem i.e. when the round is organized on all bottle banks, the best formulation found a feasible solution that has a difference of 3-5% with the lower bound of the optimal solution. In addition to that, the feasible solution was found after less than 3 minutes of processing. The best formulation was also challenged on the basis of its different parameters in order to measure the influence of those parameters. Finally, a daily selection of the bottle banks based on their filling and a basic tool to clean up the input data have been developed. In addition to that, a visualization of the solution found by the model has been provided