Spelling suggestions: "subject:"contraintes dde capacité"" "subject:"contraintes dee capacité""
1 |
Modelling congestion in passenger transit networks / Modélisation des contraintes de capacité en transports collectifs de voyageursChandakas, 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 analysisGuillen 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