Abstract

Logistic Service Providers (LSPs) offering hinterland transportation face the trade-off between efficiently using the capacity of long-haul vehicles and minimizing the first and last-mile costs. To achieve the optimal trade-off, freights have to be consolidated considering the variation in the arrival of freight and their characteristics, the applicable transportation restrictions, and the interdependence of decisions over time. We propose the use of a Markov model and an Approximate Dynamic Programming (ADP) algorithm to consolidate the right freights in such transportation settings. Our model incorporates probabilistic knowledge of the arrival of freights and their characteristics, as well as generic definitions of transportation restrictions and costs. Using small test instances, we show that our ADP solution provides accurate approximations to the optimal solution of the Markov model. Using larger problem instances, we show that our modeling approach has significant benefits when compared to common-practice heuristic approaches. Document type: Part of book or chapter of book

Abstract

In this paper we explore tramp ship routing and scheduling. Tramp ships operate much like taxies following the available demand. Tramp operators can determine some of their demand in advance by entering into long-term contracts and then try to maximise profits from optional voyages found in the spot market. Routing and scheduling a tramp fleet to best utilise fleet capacity according to current demand is therefore an ongoing and complicated problem. Here we add further complexity to the routing and scheduling problem by incorporating voyage separation requirements that enforce a minimum time spread between some voyages. The incorporation of these separation requirements helps balance the conflicting objectives of maximising profit for the tramp operator and minimising inventory costs for the charterer, since these"br/"costs increase if similar voyages are not performed with some separation in time. We have developed a new and exact branch-and-price procedure for this problem. We use a dynamic programming algorithm to generate columns and describe a time window branching scheme used to enforce the voyage separation requirements which we relax in the master problem. Computational results show that our algorithm in general finds optimal solutions very quickly and performs much faster compared to an earlier a priori path generation method. Finally, we compare our method to an earlier adaptive large neighbourhood search heuristic and find that on similar-sized instances our approach generally uses less time to find the optimal solution than the adaptive large neighbourhood search method uses to find a heuristic solution. Document type: Book

Abstract

LNCS, Vol. 8596; International audience; In this paper we present state space reduction techniques for a dynamic programming algorithm applied to the Aircraft Sequencing Problem (ASP) with Constrained Position Shifting (CPS). We consider the classical version of the ASP, which calls for determining the order in which a given set of aircraft should be assigned to a runway at an airport, subject to minimum separations in time between consecutive aircraft, in order to minimize the sum of the weighted deviations from the scheduled arrival/departure times of the aircraft. The focus of the paper is on a number of ways of improving the computation times of the dynamic programming algorithm proposed. This is achieved by using heuristic upper bounds and a completion lower bound in order to reduce the state space in the dynamic programming algorithm. We compare our algorithm to an approach based on mixed integer linear programming, which was adapted from the literature for the case of CPS. We show using real-world air traffic instances from the Milan Linate Airport that the dynamic programming algorithm significantly outperforms the MILP. Furthermore, we show that the proposed algorithm is capable of solving very large instances in short computation times, and that it is suitable for use in a real-time setting.

Abstract

International audience; Simultaneous development of photovoltaic generation and electric vehicles strengthens the solicitations on the electric power system. This paper investigates the possible synergy between these players to jointly improve the production predictability while ensuring a low carbon mobility. It stands for a step towards a quantification of its economic and environmental fallout. First a context is described for a PV-EV collaboration. Then this is gathered into an optimization problem. Grid commitment constraints, battery aging and mobility needs are here considered from the environmental point of view of equivalent primary energy. Finally, a resolution method is presented which achieve an time-efficient optimization of the power flow for each vehicle, based on upstream computed charging policies. It relies on a stochastic modeling of both vehicles availability and forecast error of the PV production. The resolution framework is the stochastic dynamic programming, coupled with on-line minimization so as to avoid the curse of dimensionality. The proposed resolution enables to compute optimal power flow for each vehicle, even among large fleets. The emphasis is here set on a versatile resolution method which could take over many detailed objective functions.

Abstract

This paper presents a study of the combined influence of battery models and sizing strategy for hybrid and battery-based electric vehicles. In particular, the aim is to find the number of battery (and supercapacitor) cells to propel a light vehicle to run two different standard driving cycles. Three equivalent circuit models are considered to simulate the battery electrical performance: linear static, non-linear static and non-linear with first-order dynamics. When dimensioning a battery-based vehicle, less complex models may lead to a solution with more battery cells and higher costs. Despite the same tendency, when a hybrid vehicle is taken into account, the influence of the battery models is dependent on the sizing strategy. In this work, two sizing strategies are evaluated: dynamic programming and filter-based. For the latter, the complexity of the battery model has a clear influence on the result of the sizing problem. On the other hand, a modest influence is observed when a dynamic programming strategy is followed.

Abstract

Production and stock optimization in supply chains is a complex problem because it determines the optimum quantity production in time. Due to their multileveld nature, those problems are mostly solved by different methods and models of dynamic programming. The problem discussed in this paper refers to the determination of optimum quantity of production and stocks within the supply chain in a certain period of time, as well as in each sub-interval of a period, but with the condition that the production and stock expenditure remains minimal and that the predetermined demand in every sub-interval and throughout the entire observation period remains satisfied. Optimalizacija proizvodnje i zaliha u opskrbnim lancima predstavlja iznimno složen problem, jer se radi o određivanju optimalne količine proizvodnje u vremenu. Takvi problemi se zbog svoje više-etapnosti najčešće rješavaju primjenom raznih metoda i modela dinamičkog programiranja. Problem koji se obraduje o ovoj znanstvenoj raspravi, odnosi se na određivanje optimalne količine proizvodnje i zaliha unutar opskrbnog lanca u određenom razdoblju, kao i u svakom pod-intervalu toga razdoblja, pod uvjetom da troškovi proizvodnje i zaliha, budu minimalni i da se zadovolji unaprijed zadana potražnja u svakom pod-intervalu, a tako i u cijelom promatranom razdoblju.

Abstract

network-wide coordination system for heavy-duty vehicle platooning with the purpose of reducing fuel consumption is developed. Road freight is by far the dominating mode for overland transport with over 60 % modal share in the OECD countries and is thus critically important for the economy. Overcoming its strong dependency on fossil fuels and manual labor as well as handling rising congestion levels are therefore important societal challenges. Heavy-duty vehicle platooning is a promising near-term automated-driving technology. It combines vehicle-to-vehicle communication and on-board automation to slipstream in a safe manner, which can reduce fuel consumption by more than 10 %. However, in order to realize these benefits in practice, a strategy is needed to form platoons in an operational context. We propose a platoon coordination system that supports the process of automatically forming platoons over large geographic areas. We develop an architecture in which fleet management systems send start locations, destinations, and arrival deadlines to a platoon coordinator. By computing desirable speed profiles and by letting the vehicles' on-board systems track them, vehicles can meet en route and form platoons. Matching vehicles into platoons and deriving suitable speed profiles is treated as an optimization problem with the objective of maximizing the overall fuel savings under the constraint that vehicles arrive in time at their destinations. By updating the speed profiles and the platoon configurations based on real-time measurements of vehicle position and platoon state, the system can accommodate new vehicles joining on the fly. Using real-time measurements also makes the system resilient to disturbances and changing operating conditions. This thesis seeks to develop the theoretical foundations of such a system and evaluate its potential to improve transport efficiency.   We first explore the coordination of vehicle pairs. Fuel-optimal speed profiles are derived. The uncertainty arising from traffic is taken into account by modeling travel time distributions and considering the probability of two vehicles successfully merging. Building on this coordination algorithm for vehicle pairs, we derive algorithms for larger platoons and vehicle fleets. This results in an NP-hard combinatorial optimization problem. The problem is formulated as an integer program and results on the solution structure are derived. In order to handle realistic fleet sizes with thousands of vehicles and continental sized geographical areas under real-time operation, heuristic algorithms are developed. The speed profiles resulting from the combinatorial optimization are further improved using convex optimization. Moreover, we derive efficient algorithms to identify all pairs of vehicles that can platoon. Simulations demonstrate that the proposed algorithm is able to compute plans for thousands of vehicles. Coordinating approximately a tenth of Germany's heavy-duty vehicle traffic, platooning rates over 65 % can be achieved and fuel consumption can be reduced by over 5 %. The proposed system was implemented in a demonstrator system. This demonstrator system has been used in experiments on public roads that show the technical feasibility of en route platoon coordination. Ett nätverksomfattande system för att koordinera körning i lastbilskolonner i syfte att minska bränsleförbrukningen utvecklas i denna avhandling.Vägtransport är med marginal det mest dominerande sättet för landtransport med en andel över 60 % i OECD-länderna och är således avgörande för samhällsekonomin. Dess starka beroende av fossila bränslen och arbetskraft samt ökande trängsel är därför viktiga utmaningar för samhället. Vägtransport är på väg att genomgå grundläggande förändringar genom elektrifiering, kommunikation och automation. Lastbilskolonnkörning är en teknologi för att automatisera fordon, som är redo att lanseras inom en snar framtid. Kolonnkörning kan ge bränslebesparingar på över 10 % tack vare att automatisering och kommunikation mellan fordon möjliggör så kallad slipstreaming på ett säkert sätt. Det behövs dock en strategi för att sätta ihop lastbilskolonner för att kunna dra nytta av denna teknologi. Vi föreslår därför ett automatiserat koordineringssystem som stödjer processen att sätta ihop lastbilskolonner inom stora geografiska områden. Vi utvecklar en arkitektur där fleet management system skickar start- och målpunkter samt senaste ankomsttid till koordineringssystemet. Genom att beräkna passande hastighetsprofiler och genom att låta lastbilarnas färddatorer följa dem kan lastbilar mötas på vägen och bygga ihop kolonner. Problemet att matcha fordon till kolonner och att komma fram till passande hastighetsprofiler hanteras som ett optimeringsproblem med målet att maximera den totala bränslebesparingen. Genom att uppdatera lösningen baserade på realtidsmätningar av fordonspositioner och kolonntillstånd kan systemet hantera tillkommande lastbilar och kan vara robust gentemot störningar och förändrade operativa förutsättningar. Denna avhandling strävar efter att utveckla teoretiska förutsättningar för ett sådant system och att utvärdera dess potential att öka transportsystemets effektivitet. Vi börjar med att undersöka koordinering av fordonspar och härleder bränsleoptimala hastighetsprofiler. Den osäkerhet som beror på trafiken tas hänsyn till genom att modellera hastighetsfördelningar och genom att betrakta sannolikheten att två fordon träffas och kan påbörja kolonnkörning. Vi bygger på denna algoritm för fordonspar för att härleda algoritmer som kan hantera större kolonner och större antal lastbilar. Det resulterar i ett NP-svårt kombinatoriskt optimeringsproblem. Problemet formuleras som ett heltalsoptimieringsproblem och vi kommer fram till resultat som visar strukturen av lösningen. Resulterande hastighetsprofiler förbättras ytterligare med hjälp av konvex optimering. Förutom detta utvecklas effektiva algoritmer för att identifiera alla fordonspar som kan köra i kolonn. Simuleringar demonstrerar att den föreslagna algoritmen klarar att beräkna planer för tusentals lastbilar. Vi visar att en samording av c:a 10 % av Tysklands lastbilstrafik kan tillåta att mer än 65 % av den totala körsträckan körs i kolonn och att bränsleåtgången kan minskas med mer än 5 %. Det presenterade systemet implementerades i ett demonstratorsystem. Experiment med demonstratorn på allmän väg har visat att koordinering av kolonnkörning på vägen är tekniskt genomförbart. "p"QC 20180403

Abstract

The operation of heavy-duty vehicles at small inter-vehicular distances, known as platoons, lowers the aerodynamic drag and, therefore, reduces fuel consumption and greenhouse gas emissions. Tests conducted on flat roads have shown the potential of platooning to reduce the fuel consumption of about 10%. However, platoons are expected to operate on public highways with varying topography alongside other vehicles. Due to the large mass and limited engine power of heavy-duty vehicles, road slopes have a significant impact on feasible and optimal speed profiles. For single vehicles, experiments have shown that optimizing the speed according to the road profile resulted in fuel saving of up to 3.5%. The use of such a look-ahead control framework is expected to lead to large benefits also for platooning. This thesis presents the design of safe and fuel-efficient control of heavy-duty vehicle platoons driving on realistic road profiles. The scenario where the platooning vehicles cooperate to optimize their overall fuel-efficiency is studied together with the scenario where the vehicles do not explicitly cooperate. First, we propose a control architecture that splits the cooperative platooning control problem into two layers. The top layer computes a reference speed profile that ensures fuel-efficient operation of the entire platoon based on dynamic programming. The bottom layer relies on model predictive control to safely track the reference speed. Simulations show the ability of the proposed controller to save up to 12% of fuel for following vehicles compared to existing platoon controllers and to safely react to emergency braking of the leading vehicle. Second, we propose a gear management layer that fits in the cooperative platooning control architecture and explicitly takes the gear selection into account. The underlying optimal control problem aims at minimizing the vehicle fuel consumption and the reference tracking deviations. Simulations indicate how this formulation outperforms existing alternatives, both in terms of fuel-efficiency and tracking error. Third, we address non-cooperative platooning by proposing a vehicle-following controller suitable for fuel-efficient control of heavy-duty vehicles. The proposed controller explores both the benefits given by the short inter-vehicular distance and those given by pulse-and-glide, i.e., alternating traction and coasting phases. A simulation study suggests fuel saving of up to 18% compared to the single vehicle case, and up to 7% compared to when a constant-distance vehicle-following controller is used. Last, we propose a vehicle-following controller aimed at exploiting long preview of the preceding vehicle trajectory by directly manipulating the inputs of low-level vehicle controllers. This is achieved through a model predictive controller that uses a short prediction horizon and includes a terminal state set that incorporates preview information about the preceding vehicle. Experiments indicate the ability of the controller to avoid unnecessary braking, while simulations show behavior similar to the optimal control behavior. "p"QC 20180416

Abstract

International audience; As mobile applications deliver increasingly complex functionalities, the demands for even more intensive computation would quickly transcend energy capability of mobile devices. On one hand and in an attempt to address such issues, fog computing paradigm is introduced to mitigate the limited energy and computation resources available within constrained mobile devices, by moving computation resources closer to their users at the edge of the access network. On another hand, most of electric vehicles (EVs), with increasing computation, storage and energy capabilities, spend more than 90% of time on parking lots. In this paper, we conceive the basic idea of using the underutilized computation resources of parked EVs as fog nodes in order to provide on-demand computation at the vicinity of the access network. The proposed Vehicular Fog Computing (VFC) architecture aggregates the abundant unused resources of parked vehicles, and uses it to serve mobile users' demands. The resource allocation problem is formulated as a Markov Decision Process (MDP) and dynamic programming is used to solve the underling decision problem. Extensive simulation results show the effectiveness of the proposed approach by improving the global reward value by 51% and scoring an energy gain of 66% compared to two other models.