Retour au site du LAAS-CNRS

Abstract

Based on a practical study in a local authority, this paper deals with new criteria for collecting waste in a dynamic context: when routes need to be updated, for instance when new housings appear or the amount of waste increases or decreases, they wish to maintain some level of stability from the current routes. We modelled our problem as a Vehicle Routing Problem with Time Windows (VRPTW), and defined two types of criteria: those concerning costs, and those concerning stability. Then, we exhibit results on VRPTW instances to take into account the dynamic increase in terms of number of nodes to collect and quantities in nodes to collect.

Abstract

This paper presents an improved discrepancy-based method, called CDDS, after being adapted to solve the flexible job shop problem in a precedent work. We propose applying discrepancy on some pertinent variables chosen by using two types of heuristics. The method is tested on different problem instances from literature.

Mots-Clés / Keywords

Résumé

L'organisation de la collecte des déchets ménagers est un problème central pour les collectivités locales qui en ont la charge. Il fait partie de la famille des problèmes de transport et plus précisément des problèmes de tournées de véhicules qu'il convient d'adapter à un ensemble d'exigences particulières qui sont difficiles à concilier : qualité de service, réduction des coûts, impact environnemental, équilibrage des collectes, etc. Notre travail s'intéresse à l'organisation des tournées de collecte et plus précisément à leur évolution dynamique lors de l'intégration de nouveaux lieux de collecte. A partir d'une étude menée au sein d'une collectivité locale, nous nous sommes centrés sur deux types de critères d'évaluation des tournées de collecte : ceux liés aux coûts et ceux concernant la stabilité des différentes tournées face aux évolutions des secteurs à collecter. Nous présentons dans cet article le problème de collecte que nous avons étudié et sa modélisation mathématique. Puis nous exposons les méthodes que nous avons utilisées pour le traitement de l'aspect dynamique des tournées de collecte et nous donnons les premiers résultats que nous avons obtenus.

Mots-Clés / Keywords

Mots-Clés / Keywords

Résumé

Notre travail s'intéresse à l'organisation de la collecte des déchets ménagers au sein d'une collectivité locale afin d'optimiser les tournées existantes. Les problèmes de transport comme la collecte des déchets sont soumis à de nombreuses exigences difficiles à concilier : qualité de service, réduction des coûts, impact environnemental, équilibrage des collectes etc. A partir d'une étude menée au sein de la collectivité locale, nous nous sommes centrés sur deux catégories de critères : ceux liés aux coûts et ceux concernant la stabilité des différentes tournées qui vont être construites. Dans cet article, nous présentons la modélisation que nous avons retenue pour notre problème et nous donnons des pistes sur les méthodes de résolution envisagées.

Mots-Clés / Keywords

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) is a generalization of the classical Job Shop Problem in which each operation must be processed on a given machine chosen among a finite sub-set of candidate machines. The aim is to find an allocation for each operation and to define the se-quence of operations on each machine so that the resulting schedule has a minimal completion time. We propose a variant of the climbing discrepancy search approach for solving this problem. Experiments have been performed on well-known benchmarks for flexible job shop scheduling.

Mots-Clés / Keywords