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 19 June 2012

Gestion optimale de systèmes de transport en libre-service

fr 

Tuesday 19 June 2012 at 12.30 PM — Seminars

Le séminaire AOC recevra le 19 juin à 12h30 Daniel Chemla (doctorant, LIPN/EPC) en B311.

Les systèmes de vélos en libre-service ont connu ces dernières années un développement sans précédent. Bien que les premières tentatives de mise en place remontent aux années 60, l’arrivée de technologies permettant un suivi des différents véhicules mis à la disposition du grand public et de l’état des bornes de stationnement en temps réel a rendu les systèmes plus sûrs. Plus de 200 villes disposent de tels dispositifs et cette tendance se poursuit avec l’entrée en fonctionnement du système de New York prévue pour l’été 2012. La mise en place d’Autolib à Paris depuis fin 2011 laisse présager l’arrivée d’un nouvel avatar de ce type de transport.

L’objectif de cette thèse de te proposer des algorithmes d’aide à la décision pour l’optimisation de réseaux de transport en libre service. L’exploitation de ces systèmes qui fleurissent actuellement un peu partout dans le monde pose en effet de nombreux problèmes, l’un des plus cruciaux étant celui de la régulation. Cette dernière a pour objectif de maintenir dans chaque station un nombre de vélos ni trop faible, ni trop élevé, afin de satisfaire au mieux la demande. Cette régulation se fait souvent par le biais de camions qui effectuent des tournées sur le réseau.

Les travaux présenté lors de ce séminaire considèrent le cas statique, où les déplacements de véhicules dûs aux usagers est considéré comme négligeable. Comment rééquilibrer le système avec un unique camion ? Et avec plusieurs camions ? Dans le premier cas, une méthode mêlant méthode tabu et branch-and-cut permet d’obtenir de bons résultats pour des instances de moins de 100 stations. Pour le cas avec plusieurs camions, une méthode de génération de colonnes est proposée, permettant de résoudre des instances de taille plus modeste, mais comparable à celle des instances résolues du Split Delivery VRP.

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).