Abstract

Improving transportation efficiency without increasing urban traffic congestion, requires to carry out new services such as ridesharing which contributes to reduce operating cost and to save road resources. In this paper, we provide users of a ridesharing system greater flexibility: given a set of drivers’ offers already in the system, and a new rider’s request, we determine a best driver, a best pick-up and drop-off locations, and a sharing cost rate between rider and driver for their common path. The main idea of our approaches consists in labelling interesting nodes of a geographical map with information about drivers, in so-called buckets. Based on the information contained in these buckets, when a rider enters the system we determine a best driver, as well as a best pick-up and drop-off locations that minimize the total travel cost of rider and driver. Exact and heuristic approaches to identify a best driver, as well as a best pick-up and drop-off locations are proposed. Finally, we perform a comparative evaluation using real road network of the Lorraine region (FR) and real data provided by a local company. Experimental analysis shows a running time of a few seconds while improving participants’ cost-savings and matching rate compared to the recurring ridesharing.

Abstract

Traditional network location theory is concerned with the optimal location of facilities which can be considered as single points (emergency medical service stations, switching centers in communication networks, bus stops, mail boxes, etc.) However, in many real problems the facility to be located is too large to be modeled as a point. Examples of such problems include the location of pipelines and high speed train lines, the design of emergency routes, newspaper delivery routes, subway lines, etc. We will refer to this kind of facilities as extensive facilities or structures, and they may have the shape of a path, a tree, a cycle or a more general subgraph.

Abstract

International audience; Car-sharing systems are increasingly employing environmentally-friendly electric vehicles. The design and management of Ecar-sharing systems poses several additional challenges with respect to those based on traditional combustion vehicles, mainly related with the limited autonomy allowed by current battery technology. We review the main optimization problems arising in Ecar-sharing systems at strategic, tactical and operational levels, and discuss the existing approaches often developed for similar problems, for example in car-sharing systems with traditional vehicles. We also outline open problems and fruitful research directions.

Abstract

This study presents a real-data approach that aims at optimizing the location of urban loading-unloading (L/U) spaces. The originality of this paper is twofold: first, it proposes a data collection methodology in order to integrate real and up-to-date information regarding cartography, L/U parking demand and existing L/U spaces. Second, an optimization model is developed in order to determine the location of new L/U spaces by taking into account real distances, influence radius and physical constraints. Such optimization model can be used to evaluate the relevance of the existing L/U spaces and/or to determine the optimal location of new ones. For this we propose to combine the use of OpenStreetMap, Google Maps APIs, and Open Data portals. This paper provides a framework composed by 3 models, namely: data collection, demand generation and location optimization. The proposed approach is applied to the city of Paris in order to illustrate different case studies and to assess the effectiveness of the framework.

Abstract

Abstract This work aims at proposing a new organization of urban merchandize distribution based on mutualized and optimized resources. In this context, our contribution is twofold. On one hand, we develop a set of models to manage merchandize distribution. We develop a new reservation system that enables customers to request a merchandize transportation service (delivery and collect) or to book a vehicle for self-service purposes. Requests are processed by two main decision modules (1) an online module that immediately searches for a feasible solution for a request, and decides to accept or reject it, and (2) an offline module that looks for optimized solutions starting from the feasible schedule defined by the online module. On the other hand, we develop a new discrete event simulator, called MODUMS which integrates the proposed models, implements such a logistic system and evaluates its economic and environmental impact. MODUMS takes as inputs realistic information about the transportation means, geographic data and demand information requests that are generated according to some probability distributions. It gives as outputs indicators on the impact of mutualization on the quality of urban logistics in terms of, for example, number of delayed or rejected requests, filling rate of vehicles, total distance and quantity of CO2.

Abstract

International audience; To sustain the rapidly increasing air traffic demand, the future air traffic management system will rely on a concept, called Trajectory-Based Operations (TBO), that will require aircraft to follow an assigned 4D trajectory (time-constrained trajectory) with high precision. TBO involves separating aircraft via strategic (long-term) trajectory deconfliction rather than the currently-practicing tactical (short-term) conflict resolution. In this context, this chapter presents a strategic trajectory planning approach aiming at minimizing the number of conflicts between aircraft trajectories for a given day. The proposed methodology allocates an alternative departure time, a horizontal flight path, and a flight level to each aircraft at a nation-wide scale.In real-life situations, aircraft may arrive at a given position with some uncertainties on its curvilinear abscissa due to external events. To ensure robustness of the strategic trajectory plan, the aircraft arrival time to any given position will be represented here by a probabilistic distribution over its nominal assigned arrival time.The proposed approach optimizes the 4D trajectory of each aircraft so as to minimize the probability of potential conflicts between trajectories. A hybrid-metaheuristic optimization algorithm has been developed to solve this large-scale mixed-variable optimization problem. The algorithm is implemented and tested with real air traffic data taking into account uncertainty over the French airspace for which a conflict-free and robust 4D trajectory plan is produced.

Abstract

SDO; "p"Electric vehicle routing problems (eVRPs) extend classical routing problems to consider the limited driving range of electric vehicles. In general, this limitation is overcome by introducing planned detours to battery charging stations. Most existing eVRP models rely on one (or both) of the following assumptions: (i) the vehicles fully charge their batteries every time they reach a charging station, and (ii) the battery charge level is a linear function of the charging time. In practical situations, however, the amount of charge is a decision variable, and the battery charge level is a concave function of the charging time.In this paper we extend current eVRP models to consider partial charging and nonlinear charging functions. We present a computational study comparing our assumptions with those commonly made in the literature. Our results suggest that neglecting partial and nonlinear charging may lead to infeasible or overly expensive solutions.

Abstract

Study of interactions between two consecutive layers of ATM under increased traffic.Results highlight an exponential growth in delay costs if constant network capacity.Results highlight an unmanageable controller workload if network capacity is high.We find a compromise by controlling delay costs growth with a sector capacity growth.We quantify research objectives for future work on air traffic control optimization. Air traffic in Europe is predicted to increase considerably over the next decades. In this context, we present a study of the interactions between the costs due to ground-holding regulations and the costs due to en-route air traffic control. We dulator that considers the regulation delays, aircraft trajectories, and air conflict resolution. Through intensive simulations based on traffic forecasts extrapolated from French traffic data for 2012, we compute the regulation delays and avoidance maneuvers according to two scenarios: the current regulations and no regulations. The resulting cost analysis highlights the exponential growth in regulation costs that can be expected if the procedures and the airspace capacity do not change. Compared to the delay costs, the costs of the air traffic control are negligible with or without regulation. The analysis reveals the heavy controller workloads when there are no regulations, suggesting the need for regulations that are appropriate for large traffic volumes and an improved ATC system. These observations motivate the design of a third scenario that computes the sector capacities to find a compromise between the increase in the delay costs due to ground-holding regulations and the increase in the controller workload. The results reveal the sensitivity of the delay costs to the sector capacity; this information will be useful for further research into ATM sector capacity and ATC automated tool design. Finally, because of the growing interest in the free flight paradigm, we also perform a traffic and cost analysis for aircraft following direct routes. The results obtained highlight the fuel and time savings and the spatial restrictions that companies use to avoid congested areas. Document type: Article

Abstract

This thesis focuses on the optimal design of one-way station-based carsharing systems. We consider the system design through two structural aspects: the optimal system dimensioning (number of parking places, vehicles, battery capacities, etc.) and the identification of appropriate stations’ locations. Although the addressed problems do not directly concern the system management, some relevant aspects (like vehicle relocation operations) are nonetheless part of the models. The modelling approach uses graph theory to represent the system dynamics over time and various optimization models (ILPs and MILPs) are proposed. The objective is to deduce an optimal shape of the whole system (number of vehicles, parking places, jockeys, stations’ locations, etc.) allowing to capture the maximum number of estimated time-dependent requests. Electric vehicles and power supply are also included in an enhanced model version and context related constraints ensure the integrity of the whole model. The optimization allows to study the impact of different power supply technologies and settle the minimal autonomy a shared vehicle necessitate in this environment. Models are applied to realistic case studies, using both random generated data and real estimated outputs of simulation tools. Strategies including vehicle relocation operations managed by jockeys (employees of the carsharing operator) are considered. We propose some graph simplifications reducing the problem size and leading to greatly improve solver capabilities as well as computation times. A greedy heuristic helping to quickly find feasible solutions and initialize the solver is also proposed and illustrated.; Cette thèse s'intéresse à la conception optimale d'un système d'autopartage de type one-way avec stations. Les problèmes abordés traitent de deux aspects structurels importants : le dimensionnement optimal du système (nombre de places de parking, de véhicules, de relocalisation de véhicules, etc.) et la localisation adéquate des stations. Bien que le management ou pilotage en temps réel du service ne soit pas l'objet de cette étude, certains aspects pertinents (relocalisation de véhicules, nombre de jockeys) ont toutefois été intégrés aux modèles. L'approche mathématique utilise des objets de la théorie des graphes pour représenter les systèmes dans le temps et les problèmes sont résolus grâce à la programmation linéaire en nombre entiers. L'objectif est d'identifier la structure du service permettant de capturer le plus de demandes possibles. L'introduction de véhicules électriques et de la puissance de charge en station sont étudiés dans un modèle dédié. Les expérimentations s'appuient sur des données réalistes, générées aléatoirement. Nous nous intéressons particulièrement aux pistes d'amélioration des temps de calculs et de réduction des graphes. Une heuristique gloutonne permettant d'identifier rapidement une solution réalisable est en particulier proposée. Enfin, une étude de dimensionnement des batteries confirme que des capacités deux fois inférieures à celles actuellement sur le marché sont viable dans le contexte urbain actuel.

Abstract

Traffic Engineering (TE) uses methods and models from a variety of mathematical fields, such as statistics and optimization, to improve the performance of telecommunication networks. In this thesis, we study TE problems dealing with networks that impose single-path routing. As the name infers, in this type of routing, the traffic flow of each "commodity" cannot be split in its path between its origin and destination. Given its cheap cost, single-path routing is widely used in today's data centers, where thousands of stored servers perform computations or host Internet services. One common case of single-path routing is the one enforced by the Spanning Tree Protocol (STP) in switched Ethernet networks. The STP requires the network to keep its activated links loop-free, while maintaining the other redundant links ready for back-up, in case of link failure. The Multiple Spanning Tree Protocol (MSTP) extends the STP by installing multiple virtual networks compliant with the STP, over a single physical topology. Therefore, the MSTP is greatly beneficial for network service providers, as it allows for a more efficient use of the existing resources.Network design problems dealing with the MSTP are generally highly combinatorial and very hard to solve. As such, TE literature mainly suggests heuristic methods, which can quickly produce reasonable designs. Notwithstanding, due to a scarce existence of lower bounds to the optimum values of such problems, there is little knowledge about the quality of the solutions provided by these heuristics.In this sense, we propose mathematical programming models and methods that can provide optimal designs for these networks, or at the very least, obtain valid lower bounds. Taking into mind the goal of avoiding congestion in the network, we focus on two problems that deal with the following load-balancing objectives: the minimization of the worst-case link utilization, and the minimization of flow costs given by piecewise linear functions that penalize heavily-loaded links. The study of both these problems yielded relevant by-products: the first is the study of a MSTP network design problem, where we minimize the total load, and the second is the study of a fundamental unsplittable multicommodity flow problem with piecewise linear costs.For all the considered problems, we provide studies of complexity, extensive polyhedral studies to compare the proposed formulations, and a wide array of computational experiments to evaluate the performance of the proposed models and methods. Doctorat en Sciences info:eu-repo/semantics/nonPublished