Faculté des Sciences appliquées

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

##### Details
 Title : Optimization of a multi-depot routing for bottle banks rounds based on variable logistic constraints Translated title : [fr] Optimisation de tournées de bulles à verres depuis plusieurs dépôts sur la base de contraintes logistiques variables Author : Chiodo, Adrien Date of defense  : 24-Jun-2021/25-Jun-2021 Advisor(s) : Louppe, Gilles  Lejoly, Loïc Committee's member(s) : Louveaux, Quentin  Boigelot, Bernard Language : English Number of pages : 70 pages. Keywords : [en] Optimization[en] MDVRP[en] Routing Problem[en] VRP Discipline(s) : Engineering, computing & technology > Computer science Institution(s) : Université de Liège, Liège, Belgique Degree: Master en ingénieur civil en informatique, à finalité spécialisée en "intelligent systems" Faculty: Master thesis of the Faculté des Sciences appliquées

##### Abstract

[en] 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

Description: -
Size: 2.57 MB
Description:
Size: 2.63 MB
Description:
Size: 404.79 kB

### Author

• Chiodo, Adrien Université de Liège > Master ingé. civ. info., à fin.

### Committee's member(s)

• Louveaux, Quentin Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation : Optimisation discrète
View his publications on ORBi
• Boigelot, Bernard Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique
View his publications on ORBi
• Total number of views 13