Actualités du LIPN

[LIPN] [CNRS] [Université Paris 13]

To content | To menu | To search

Keyword - tournée de véhicules

Entries feed - Click here to abridge

Past posts

Tuesday 2 November 2010

Modeling and solving some pickup-and-delivery routing problems

fr 

Tuesday 2 November 2010 at 12.30 PM — Seminars

Le séminaire AOC recevra le 2 novembre Juan José Salazar González (Universidad de La Laguna, Tenerife).

There are many variants of vehicle routing problems were a set of commodities must be moved between different locations. In our talk we model and solve some variants. The simplest (but still complex) version is the so-called "one-commodity pickup-and-delivery Travelling Salesman Problem" (1-PDTSP).

In this version we assume to have a single capacitated vehicle that must move one product (e.g. bicycles) between different points (customers) of a region. Each customer has a demand of the product that may be positive (delivery point) or negative (pickup point). One customer is considered to be the main office (depot) with a demand to equilibrate pickups and deliveries.

Then the 1PDTSP is the problem of finding the shortest route for the vehicle that visits each customer exactly once and satisfies the demand of all of them. We present and discuss a mathematical model, a branch-and-cut method and a metaheuristic approch for the 1-PDTSP.

Then we will discuss the multi-commodity extension of this problem, analysing first the particular cases where each commodity has only one source and one destination (called the "one-to-one m-PDTSP"). We relate this problem to others in the literature and dicuss some exact and heuristics approaches to solve it. Most of these results have been obtained while Hipólito Hernández Pérez was doing his PhD at University of La Laguna, Tenerife.

Tuesday 20 April 2010

Résolution de problèmes de transport à la personne par génération de colonnes

fr 

Tuesday 20 April 2010 at 12.30 PM — Seminars

Le séminaire OCAD recevra le 20 avril Thierry Garaix (chercheur, Politecnico di Torino).

Cette présentation met en avant trois problèmes de tournées de véhicules originaux issus de la considération de réseau routiers réels et de critères de qualité de service pour le transport de personnes. Les méthodes proposées sont basées sur des approches de génération de colonnes.

Au cours des dernières décennies, en partant du problème de Voyageur de Commerce, les problèmes de tournées de véhicules académiques ont été enrichis par des contraintes ou des extensions de natures différentes : flotte de véhicules, capacités, fenêtres de temps et ramassage et livraison pour les plus étudiées. Nous disposons ainsi aujourd’hui de méthodes heuristiques ou exactes efficaces sur ces problèmes. Deux enjeux majeurs actuels en terme d’optimisation, sont le passage à des problèmes de grande taille et/ou la prise en compte de nouvelles contraintes (possiblement multicritères). Le transport de personnes et en particulier les transports à la demande s’apparentent directement à ces enjeux en intégrant notamment des contraintes fortes liées à la qualité de service.

Un réseau de transport propose généralement des chemins alternatifs privilégiant tel ou tel critère (coût, temps, sécurité;...). Considérer ces alternatives, génère une forte augmentation de la taille des données définissant l’espace des solutions. Il est donc nécessaire de valider des approches pertinentes sur des réseaux ainsi définis. Un critère usuel d’évaluation de la performance générale d’un système de transport, est le taux moyen de remplissage des véhicules. Cependant, ce critère fractionnaire est rarement (jamais) utilisé comme objectif dans les outils de calcul des tournées. Dans le un cas de transport à la demande, il se révèle peu coûteux en temps de calcul d’y adapter une méthode de génération de colonnes standard.

Dans le cadre de transport de personnes handicapées, la régularité des horaires de ramassage d’un jour sur l’autre, est un critère de qualité de service primordial. C’est aussi une valeur ajoutée à des tournées de livraison pour des clients réguliers. La modélisation de cette contrainte donne un problème original pour lequel est proposé une heuristique basée sur la résolution exacte d’un problème de tournées à fenêtres de temps dures (sans temps d’attentes) et multiples.

Tuesday 24 November 2009

Le problème de ramassage et livraison préemptif

fr 

Tuesday 24 November 2009 at 12.30 PM — Seminars

Le séminaire OCAD accueille Mathieu Lacroix (ATER, LAMSADE, université Paris-Dauphine).

Dans un premier temps, nous considérons le problème lorsque la flotte est composée de plusieurs véhicules, les transbordements sont possibles et le fractionnement des demandes est autorisé. Nous donnons deux formulations à l’aide de programmes linéaires mixtes basés sur un graphe spatio-temporel. Nous présentons des contraintes valides et fournissons, pour chacune des deux formulations, un algorithme de coupes et branchements pour résoudre le problème. Nous comparons finalement les résultats expérimentaux obtenus avec les deux algorithmes.

Nous considérons par la suite le problème lorsque la flotte est composée d’un unique véhicule et le fractionnement des demandes n’est pas autorisé. Nous considérons également la version unitaire de ce problème, c’est-à-dire, lorsque le véhicule ne transporte qu’une seule demande à la fois. Pour ces deux versions, nous donnons une formulation sous forme d’un programme linéaire en nombres entiers. Nous étudions ensuite le polytope des solutions de la version unitaire et développons un algorithme de coupes et branchements. Nous étudions également ce polytope dans la classe des cactus. Nous considérons finalement un cas particulier de la version unitaire du problème lorsque le graphe est complet, chaque sommet est incident à au plus une demande et les coûts vérifient les inégalités triangulaires. Nous montrons que, sous ces hypothèses, le problème se ramène à la recherche d’un cactus de coût minimum vérifiant certaines propriétés. En se basant sur cette transformation, nous proposons une métaheuristique pour résoudre le problème.

Friday 6 November 2009

Heuristique à grand voisinage pour confection de tournée avec cueillettes, livraisons et contraintes

fr 

Friday 6 November 2009 at 02.00 PM — Seminars

Le séminaire OCAD accueille Michel Gendreau (CIRRELT et MAGI, École polytechnique de Montréal).

De façon exceptionnelle, ce séminaire a lieu en B311 à 14h un vendredi, et non un mardi à 12h30 comme habituellement.

Le titre complet est : « Une heuristique à grand voisinage pour un problème de confection de tournée d’un seul véhicule avec cueillettes, livraisons et contraintes de chargement ».

Nous présentons un nouveau problème de confection de tournée dans lequel un véhicule unique effectue des cueillettes et des livraisons, tout en respectant des contraintes de chargement. La caisse du véhicule est divisée en plusieurs « files » de même largeur dans lesquelles des colis de même largeur, mais possiblement de longueur différente sont placés les uns derrière les autres durant le transport. La longueur totale des colis placés dans chaque file à tout instant ne peut dépasser la longueur de la caisse du véhicule. De plus, aucun déplacement des colis n’est permis, ce qui veut dire que seul le dernier colis non encore livré de chaque file est accessible pour livraison. Cette variante est motivée par la parution récente d’articles portant sur des problèmes semblables qu’elle généralise.

Nous proposons une heuristique à grand voisinage, basée sur les travaux récents de Pisinger et Ropke, comme méthode de résolution. Nous rapportons les résultats d’expérimentations numériques pour plusieurs instances existantes de cas particuliers, ainsi que pour un jeu de nouvelles instances.

(Travail réalisé en collaboration avec Jean-François Côté et Jean-Yves Potvin)

Wednesday 3 December 2008

Soutenance de thèse de Nora Touati

fr 

Wednesday 3 December 2008 at 03.00 PM — PhD & Habilitations defends

Nora Touati soutient sa thèse intitulée « Amélioration des performances du schéma de la génération de colonnes: Application aux problèmes de tournées de véhicules ».

La soutenance aura lieu le mercredi 3 décembre 2008 à 15h, salle B311 du LIPN.

Le jury sera composé de :

  • Anass Nagih: Directeur de thèse PR-Université de Metz.
  • Lucas Létocart: Co-encadrant, MCF-Université Paris 13.
  • Claude Lemaréchal: Rapporteur, DR-INRIA Rhone-Alpes.
  • Ali-Ridha Mahjoub:Rapporteur, PR-Université Paris Dauphine.
  • Aristide Mingozzi: Examinateur, PR-Université de Bologne.
  • Gérard Plateau: Président du jury, PR-Université Paris 13.
  • Roberto Wolfler-Calvo: Examinateur, PR-Université Paris 13.

Continue reading...

Tuesday 14 October 2008

Tournées de véhicules m-péripatétiques

fr 

Tuesday 14 October 2008 at 12.30 PM — Seminars

Le séminaire OCAD accueille Sandra U. Ngueveu (Université de doctorante, Technologie de Troyes).

Elle nous présentera ses travaux sur les bornes inférieures et supérieures sur le problème de tournées de véhicules m-péripatétiques (résumé plus complet à venir).