• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 2
  • Tagged with
  • 2
  • 2
  • 2
  • 2
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Modelling congestion in passenger transit networks / Modélisation des contraintes de capacité en transports collectifs de voyageurs

Chandakas, Ektoras 01 April 2014 (has links)
Un modèle structurel est fourni afin d'appréhender les phénomènes de capacité dans un modèle d'affectation de flux de voyageurs sur un réseau de transport collectifs. Cela a été fondé sur une représentation du réseau de transports collectifs en deux couches : sur la couche inférieure, le modèle traite séparément chaque sous système du réseau (ligne, station et rabattement) en fonction des effets de capacité spécifiques ; sur la couche supérieure, le choix d'itinéraire d'un voyageur individuel est adressée par une représentation du réseau en leg (ou segment de ligne) en utilisant le coût et les caractéristiques opérationnelles des sous-systèmes respectifs. On établit une cadre novateur pour modéliser les effets de capacité et on développe le modèle CapTA (pour Capacitated Transit Assignment). Il s'agit d'un modèle d'affectation de flux systémique et modulaire. Il adresse les phénomènes de capacité ci dessous : La qualité du service en véhicule est liée au confort de voyageurs à bord. L'occupation d'états de confort hétérogènes (places assises, strapontins et debout à de densités de voyageurs variables) influence la pénibilité perçu du voyage ; La capacité du véhicule à la montée impacte le temps d'attente de voyageurs et leur distribution aux missions disponibles ; La capacité de l'infrastructure de la ligne établit une relation entre le temps de stationnement des véhicules (and par extension les flux de voyageurs en montée et en descente) et la performance des missions et leur fréquence de service. Ces phénomènes sont traités par ligne d'exploitation sur la base d'un ensemble des modèles locaux qui rendent de flux et de coût spécifiques. Par conséquent, ils modifient les conditions locales d'un trajet en transports collectifs pour chaque voyageur individuel. Cependant, ils doivent être adressés dans le cadre d'un réseau de transports collectifs afin de recueillir leur effet sur les choix d'itinéraire sur le réseau ; essentiellement sur les arbitrages économiques qui impactent le choix entre itinéraires alternatifs. Leur traitement sur la couche réseau garantir la cohérence du choix d'itinéraire. Le modèle de station traite de contraintes de capacité spécifiques et évalue les conditions locales de marche, qui est sensible aux interactions des voyageurs à l'intérieur de la station : le goulot instantané à l'entrée d'un élément de circulation retard l'évacuation de la plateforme ; la densité de voyageurs et l'hétérogénéité des leur flux ralenti les voyageurs qui circulent dans une station ; la présence de l'information en temps réel influence le processus de décision des voyageurs. Ces effets n'ont pas seulement un impact sur le choix d'itinéraire à l'intérieure de la station, mais notamment ils modifient les choix de service sur le niveau du réseau. La Région Ile-de-France fournit un champ d'application idéal pour un modèle d'affectation de flux de voyageurs en transport collectifs sous contraintes de congestion. Plus précisément, il est utilisé dans le cadre du modèle CapTA pour illustrer les capacités de simulation et la finesse de l'approche de modélisation adoptée. Le réseau de transports collectifs contient 1 500 missions de cars et autocars, tout comme 260 missions ferroviaires et inclut 14 lignes de métro et 4 lignes de tramway. L'affectation de trafic à l'heure de pointe du matin est caractérisée d'une charge importante en voyageurs sur les sections centrales de lignes ferroviaires qui traversent la ville. Un temps de stationnement élevé, en raison de flux de montée et descente, et la réduction de la fréquence de service impactent la capacité des missions et des lignes. Le temps généralisé d'un trajet est impacté notamment de sa composante de confort à bord. De résultats détaillés sont présentés sur le RER A, la ligne la plus chargée du réseau ferroviaire régional / A structural model is provided to capture capacity phenomena in passenger traffic assignment to a transit network. That has been founded on a bi-layer representation of the transit network : on the lower layer the model addresses each network sub-system (line, station and access-egress) separately, on the basis of specific capacity effects ; on the upper layer a leg-based representation is used with respect to the sub-systems' costs and operating characteristics to address the trip maker's path choices. We establish a novel framework for modelling capacity effects and develop the CapTA network model (for Capacitated Transit Assignment). It is systemic and modular and addresses in particular the following capacity phenomena, the in-vehicle quality of service is linked to the comfort of the passengers on-board. The occupation of heterogeneous comfort states (seats, folding seats and standing at different passenger densities) influences the perceived arduousness of the travel ; the vehicle capacity at boarding influences the waiting time of the passengers and their distribution to the transit services ; the track infrastructure capacity relates the dwelling time of the vehicles (and by extent the alighting and boarding flows) with the performance of the transit services and their service frequency. These phenomena are dealt with by line of operations on the basis of a set of local models yielding specific flows and costs. Accordingly, they modify the local conditions of a transit trip for each individual passenger. However, these should be addressed within the transit network in order to capture their effect on the network path choices; essentially the economic trade-offs that influence the choice between different network itineraries. Their treatment in a network level assures the coherence of the path choice. Equivalently, a station sub-model addresses specific capacity constraints and yields the local walking conditions, sensible to the interaction of the passengers in the interior of a station : the instant bottleneck created at the entry of the circulation elements delays the evacuation of the station platforms; the passenger density and presence of heterogeneous passenger flows slows down the passengers who circulate in the station; and the presence of real-time information influences the decision making process of the transit users exposed to. These effects do not only impact locally the in-station path choice, but most notably they modify the choices of transit routes and itineraries on a network level. The Paris Metropolitan Region provides an ideal application field of the capacity constrained transit assignment model. It is mainly used as a showcase of the simulation capabilities and of the finesse of the modelling approach. The transit network involves 1 500 bus routes together with 260 trains routes that include 14 metro lines and 4 light rail lines. Traffic assignment at the morning peak hour is characterized by heavy passenger loads along the central parts of the railway lines. Increased train dwelling, due to boarding and alighting flows, and reduction in the service frequency impact the route and the line capacity. The generalized time of a transit trip is impacted mainly though its in-vehicle comfort component. Detailed results have been provided for the RER A, the busiest commuter rail line in the transit network
2

Metaheuristics for vehicle routing problems : new methods and performance analysis

Guillen Reyes, Fernando Obed 02 1900 (has links)
Cette thèse s’intéresse au problème classique de tournées de véhicules avec contraintes de capacité (CVRP pour Capacitated Vehicle Routing Problem) ainsi qu’une variante beaucoup plus complexe, soit le problème de tournées de véhicules dépendant du temps avec fenêtres de temps et points de transfert défini sur un réseau routier (TDVRPTWTP-RN pour Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network). Dans le premier article, le TDVRPTWTP-RN est résolu en adaptant une métaheuristique qui représente l’état de l’art pour le CVRP, appelé Slack Induction for String Removals (SISR). Cette métaheuristique fait appel au principe “détruire et reconstruire” en retirant des séquences de clients consécutifs dans les routes de la solution courante et en réinsérant ensuite ces clients de façon à créer une nouvelle solution. Le problème est défini sur un réseau routier où différents chemins alternatifs peuvent être utilisés pour se déplacer d’un client à l’autre. De plus, le temps de parcours sur chacun des arcs du réseau n’est pas fixe, mais dépend du moment où le véhicule quitte le sommet origine. S’inspirant de problèmes rencontrés en logistique urbaine, nous considérons également deux types de véhicules, de petite et grande capacité, où les grands véhicules sont interdits de passage au centre-ville. Ainsi, les clients du centre-ville ne peuvent être servis que suite au transfert de leur demande d’un grand à un petit véhicule à un point de transfert. Comme un point de transfert n’a pas de capacité, une problématique de synchronisation apparaît quand un grand véhicule doit y rencontrer un ou plusieurs petits véhicules pour leur transférer une partie de son contenu. Contrairement aux problèmes stricts de tournées de véhicules à deux échelons, les grands véhicules peuvent aussi servir des clients localisés à l’extérieur du centre-ville. Comme le problème abordé est beaucoup plus complexe que le CVRP, des modifications importantes ont dû être apportées à la métaheuristique SISR originale. Pour évaluer la performance de notre algorithme, un ensemble d’instances tests a été généré à partir d’instances existantes pour le TDVRPTW-RN. Les réseaux omt été divisés en trois régions : centre-ville, frontière et extérieur. Le centre-ville et l’extérieur sont respectivemnt les royaumes des petits et grands véhicules, tandis que la frontière (où l’on retrouve les points de transfert) peut être visité par les deux types de véhicules. Les résultats numériques montrent que la métaheuristique proposée exploite les opportunités d’optimiser une solution en déplaçant autant que possible les clients neutres, soit ceux qui peuvent être servis indifféremment par un petit ou un grand véhicule, des routes des petits véhicules vers les routes des grands véhicules, réduisant ainsi les coûteuses visites aux points de transfert. Les deuxième et troisième article s’intéressent à des concepts plus fondamentaux et font appel au problème plus simple du CVRP pour les évaluer. Dans le second article, un étude expérimentale est conçue afin d’examiner l’impact de données (distances) imprécises sur la performance de différents types d’heuristiques, ainsi qu’une méthode exacte, pour le CVRP. À cette fin, différents niveaux d’imprécision ont été introduits dans des instances tests classiques pour le CVRP avec 100 à 1 000 clients. Nous avons observé que les meilleures métaheuristiques demeurent les meilleures, même en présence de hauts niveaux d’imprécision, et qu’elles ne sont pas affectées autant par les imprécisions qu’une heuristique simple. Des expériences avec des instances réelles ont mené aux mêmes conclusions. Le troisième article s’intéresse à l’intégration de l’apprentissage automatique dans la métaheuristique SISR qui représente l’état de l’art pour le CVRP. Dans ce travail, le principe “détruire et reconstruire” au coeur de SISR est hybridé avec une méthode d’apprentissage par renforcement qui s’inspire des systèmes de colonies de fourmis. L’ap- prentissage automatique a pour but d’identifier les arêtes les plus intéressantes, soit celles qui se retrouvent le plus fréquemment dans les solutions de grande qualité précédemment rencontrées au cours de la recherche. L’inclusion de telles arêtes est alors favorisé lors de la réinsertion des clients ayant été retirés de la solution par le mécanisme de destruction. Les instances utilisées pour tester notre approche hybride sont les mêmes que celles du second article. Nous avons observé que notre algorithme ne peut produire que des solutions lé- gèrement meilleures que la métaheuristique SISR originale, celle-ci étant déjà quasi-optimale. / This thesis is concerned both with the classical Capacitated Vehicle Routing Problem (CVRP) and a much more complex variant called the Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network (TDVRPTWTP-RN ). In the first paper, the TDVRPTWTP RN is solved by adapting a state-of-the-art metaheuris- tic for the CVRP, called Slack Induction for String Removals (SISR). This metaheuristic is based on the ruin and recreate principle and removes strings of consecutive customers in the routes of the current solution and then reinserts the removed customers to create a new solution. The problem is formulated in a full road network where different alternative paths can be used to go from one customer to the next. Also, the travel time on each arc of the road network is not fixed, but depends on the departure time from the origin node. Motivated from city logistics applications, we also consider two types of vehicles, large and small, with large vehicles being forbidden from the downtown area. Thus, downtown customers can only be served through a transfer of their goods from large to small vehicles at designated transfer points. Since transfer points have no capacity, synchronization issues arise when a large vehicle must meet one or more small vehicles to transfer goods. As opposed to strict two-echelon VRPs, large vehicles can also directly serve customers that are outside of the downtown area. Given that the TDVRPTWTP-RN is much more complex than the CVRP, important modifications to the original SISR metaheuristic were required. To evaluate the performance of our algorithm, we generated a set of test instances by extending existing instances of the TDVRPTW-RN . The road networks are divided into three regions: downtown, boundary and outside. The downtown and outside areas are the realm of small and large vehicles, respectively, while the boundary area that contains the transfer points can be visited by both small and large vehicles. The results show that the proposed metaheuristic exploits optimization opportunities by moving as much as possible neutral customers (which can be served by either small or large vehicles) from the routes of small vehicles to those of large vehicles, thus avoiding costly visits to transfer points. The second and third papers examine more fundamental issues, using the classical CVRP as a testbed. In the second paper, an experimental study is designed to examine the impact of inaccurate data (distances) on the performance of different types of heuristics, as well as one exact method, for the CVRP. For this purpose, different levels of distance inaccuracies were introduced into well-known benchmark instances for the CVRP with 100 to 1,000 customers. We observed that the best state-of-the-art metaheuristics remain the best, even in the presence of high inaccuracy levels, and that they are not as much affected by inaccuracies when compared to a simple heuristic. Some experiments performed on real-world instances led to the same conclusions. The third paper focuses on the integration of learning into the state-of-the-art SISR for the CVRP. In this work, the ruin and recreate mechanism at the core of SISR is enhanced by a reinforcement learning technique inspired from ant colony systems. The learning component is aimed at identifying promising edges, namely those that are often found in previously encountered high-quality solutions. The inclusion of these promising edges is then favored during the reinsertion of removed customers. The benchmark instances of the second paper were also used here to test the new hybrid algorithm. We observed that the latter can produce only slightly better solutions than the original SISR, due to the quasi-optimality of the original solutions.

Page generated in 0.1076 seconds