Faculté des Sciences appliquées
Faculté des Sciences appliquées

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

Chiodo, Adrien ULiège
Promotor(s) : Louppe, Gilles ULiège ; Lejoly, Loïc
Date of defense : 24-Jun-2021/25-Jun-2021 • Permalink :
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 ULiège
Date of defense  : 24-Jun-2021/25-Jun-2021
Advisor(s) : Louppe, Gilles ULiège
Lejoly, Loïc 
Committee's member(s) : Louveaux, Quentin ULiège
Boigelot, Bernard ULiège
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


[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



Access Erratum_Master_Thesis_CHIODO_Adrien.pdf
Description: -
Size: 2.57 MB
Format: Adobe PDF
Access Master_Thesis_CHIODO_Adrien.pdf
Size: 2.63 MB
Format: Adobe PDF
Access Abstract_CHIODO_Adrien.pdf
Size: 404.79 kB
Format: Adobe PDF


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


Committee's member(s)

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

All documents available on MatheO are protected by copyright and subject to the usual rules for fair use.
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.