/
0/5

0 avis

Selective vehicle routing problem

cluster and synchronization constraints

Type de document : Thèse
Langue : anglais

Responsabilité(s) :


Responsabilité(s) secondaire (s) :
Université de soutenance : Université de Technologie de Compiègne

Numéro national de thèse : 2018COMP2449

Année de publication : 2018


Discipline : Technologies de l'Information et des Systèmes : Unité de recherche Heudyasic (UMR-7253)

Sujets :


Mots clés :

Résumé(s) :

  • Le problème de tournées de véhicules (Vehicle Routing Problem - VRP) est un problème d'optimisation combinatoire utilisé généralement pour modéliser et résoudre des différents problèmes rencontrés dans les systèmes logistiques et de transport. Dans cette thèse, nous nous sommes intéressés à l'étude et la résolution d'une classe de problèmes du VRP appelée les problèmes de courses d'orientation (Team Orienteering Problem - TOP). Dans cette catégorie de problèmes, il est a priori impossible de visiter tous les clients en raison de ressources limitées. On associe plutôt un profit à chaque client qui représente sa valeur. Ce profit est collecté lorsque le client est visité par l'un des véhicules disponibles. L'objectif est donc de sélectionner un sous ensemble de clients à servir tout en maximisant le profit total collecté. Dans un premier temps, nous avons introduit une nouvelle généralisation pour le TOP que nous avons appelé le Clustered TOP ou CluTOP. Dans cette variante, les clients sont regroupés en sous-ensembles appelés clusters auxquels nous associons des profits. Pour résoudre cette variante, nous avons proposé un schéma exact basé sur l'approche des plans sécants avec des inégalités valides supplémentaires et des pré-traitements. Nous avons également conçu une méthode heuristique basée sur l'approche order first-cluster second. Cette heuristique hybride combine une heuristique de type Adaptive Large Neighborhood Search qui explore l'espace des solutions et une procédure de découpage qui explore l'espace de recherche des tours géants. De plus, la procédure de découpage est renforcée par une recherche locale afin de mieux explorer l'espace de recherche. Le deuxième problème traité dans ce travail s'appelle le Synchronized Team Orienteering Problem with Time Windows (STOPTW). Cette variante avait été initialement proposée afin de modéliser des scénarios liés à la protection des infrastructures stratégiques menacées par l'avancée des feux de forêts. En plus des contraintes de fenêtres de temps et des visites synchronisées, cette variante considère le cas d'une flotte de véhicules hétérogène. Pour résoudre ce problème, nous avons proposé une méthode heuristique basée sur l'approche GRASP.ILS qui est parvenue à dominer la seule approche existante dans la littérature. La dernière variante du TOP abordée dans cette thèse s'appelle le Set Orienteering Problem (SOP). Les clients dans cette variante sont regroupés en sous-ensembles appelés clusters. Un profit est associé à chaque groupe qui n'est obtenu que si au moins un client est desservi par le véhicule disponible. Nous avons proposé une méthode de coupes avec deux procédures de séparation pour séparer les contraintes d'élimination des sous-tours. Nous avons également proposé un algorithme Mémétique avec une procédure de découpage optimale calculée à l'aide de la programmation dynamique.
  • The Vehicle Routing Problem (VRP) is a family of Combinatorial Optimization Problems generally used to solve different issues related to transportation systems and logistics. In this thesis, we focused our attention on a variant of the VRP called the Team Orienteering Problem (TOP). In this family of problems, it is a priory impossible to visit all the customers due to travel time limitation on vehicles. Instead, a profit is associated with each customer to represent its value and it is collected once the customer is visited by one of the available vehicles. The objective function is then to maximize the total collected profit with respect to the maximum travel time. Firstly, we introduced a new generalization for the TOP that we called the Clustered TOP (CluTOP). In this variant, the customers are grouped into subsets called clusters to which we associate profits. To solve this variant, we proposed an exact scheme based on the cutting plane approach with additional valid inequalities and pre-processing techniques. We also designed a heuristic method based on the order first-cluster second approach for the CluTOP. This Hybrid Heuristic combines between an ANLS heuristic that explores the solutions space and a splitting procedure that explores the giant tours search space. In addition, the splitting procedure is enhanced by local search procedure in order to enhance its coverage of search space. The second problem treated in this work is called the Synchronized Team Orienteering Problem with Time Windows (STOPTW). This variant was initially proposed in order to model scenarios related to asset protection during escaped wildfires. It considers the case of a heterogeneous fleet of vehicles along with time windows and synchronized visits. To solve this problem, we proposed a heuristic method based on the GRASP.ILS approach that led to a very outstanding results compared to the literature. The last variant of the TOP tackled in this thesis called the Set Orienteering Problem (SOP). Customers in this variant are grouped into subsets called clusters. Each cluster is associated with a profit which is gained if at least one customer is served by the single available vehicle. We proposed a Branch-and-Cut with two separation procedures to separate subtours elimination constraints. We also proposed a Memetic Algorithm with an optimal splitting procedure based on dynamic programming.

Autre(s) titre(s):

  • Titre traduit : Problèmes de tournées de véhicules sélectives : contraintes de cluster et de synchronisation


  • Accéder au document
  • Consulter en ligne

    Suggestions

    Du même auteur

    Hybrid heuristic for the clustered orienteering problem | Yahiaoui, Ala-Eddine

    Hybrid heuristic for the clustered orienteering problem / Yahiaoui, Ala-Eddine - Moukrim, Aziz - Serairi, Mehdi - Springer, 2017

    This paper addresses the Clustered Orienteering Problem, a recent variant of the Orienteering Problem. In this variant, customers are grouped into subsets called clusters. A profit is assigned to each cluster and is collected only...

    Source : Ressources électroniques

    EXTR|EXTR

    The clustered team orienteering problem | Moukrim, Aziz

    The clustered team orienteering problem / Moukrim, Aziz - Serairi, Mehdi - Yahiaoui, Ala-Eddine - Springer Verlag, 2019

    In this paper, we present a new variant of the Clustered Orienteering Problem (COP) that we refer to as the Clustered Team Orienteering Problem (CluTOP). In this problem, customers are grouped into subsets called clusters. A profi...

    Source : Ressources électroniques

    EXTR|EXTR

    Flow-shop with time delays, linear modeling and exact solution approaches | Mkadem, Mohamed Amine (19..-....). Auteur

    Flow-shop with time delays, linear modeling and exact solution approaches / Mkadem, Mohamed Amine (19..-....). Auteur, 2017

    Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à l...

    Source : Ressources électroniques

    THES|THES

    Du même sujet

    Selective vehicle routing problems in collaborative urban transport networks | Ben Said, Asma (19..-....). Auteur

    Selective vehicle routing problems in collaborative urban transport networks / Ben Said, Asma (19..-....). Auteur, 2019

    Le but de ce travail de thèse réside dans la planification de la distribution urbaine des marchandises dans un système de transport collaboratif. Cette collaboration consiste à échanger les demandes de transport entre transporteur...

    Source : Ressources électroniques

    THES|THES

    Vehicle routing problems with resources synchronization | Lafifi, Sohaib. Auteur

    Vehicle routing problems with resources synchronization / Lafifi, Sohaib. Auteur, 2014

    Cette thèse porte sur la résolution de problèmes de transport qui intègrent des contraintes temporelles considérant les fenêtres de temps, la synchronisation des visites et l équilibrage des services. Ces problèmes trouvent plusie...

    Source : Ressources électroniques

    THES|THES

    Flow-shop with time delays, linear modeling and exact solution approaches | Mkadem, Mohamed Amine (19..-....). Auteur

    Flow-shop with time delays, linear modeling and exact solution approaches / Mkadem, Mohamed Amine (19..-....). Auteur, 2017

    Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à l...

    Source : Ressources électroniques

    THES|THES

    Chargement des enrichissements...

    Avis des lecteurs