Transcription
D5.2 – Coordinated fault-tolerated real-time scheduling of platoonsCOMPANION- 610990EUROPEAN COMMISSIONSEVENTH FRAMEWORK PROGRAMMEGA No. 610990Cooperative dynamic formation of platoons for safe andenergy-optimized goods transportationD5.2. Coordinated fault-tolerated real-time scheduling ofplatoonsDeliverable No.Deliverable TitleDissemination levelWritten ByChecked byApproved byIssue dateCOMPANION D5.2Coordinated fault-tolerated real-timescheduling of platoonsPublicSebastian van de Hoef (KTH)Jonas Mårtensson (KTH) WP leaderMagnus Adolfson (Scania) 7/20161/1
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 610990PublicHistory LogNameStatusVersionDateSummary of actions madeKTHJonas MårtenssonEditor0.114/06/2016First Draft. SkeletonKTHSebastian van de HoefEditor0.212/07/2016First version with contentOffisSönke EilersReviewer0.220/07/2016Comments on 0.2VWChristian BrunsReviewer0.221/07/2016Comments on 0.2KTHSebastian van de HoefEditor0.321/07/2016Addressing comments on 0.2ScaniaMagnus AdolfsonReviewer0.327/07/2016Comments on 0.3KTHSebastian van de HoefEditor1.029/07/2016Addressing comments on 0.32 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 610990PublicExecutive SummaryThis report constitutes the Deliverable D5.2: Coordinated fault-tolerant real-time scheduling of platoons. It is the result of the work within the task T5.2, which belongs to WP5: Off-board system forplatoon coordination.The objective of WP5.2 is the development of a novel decision making engine for the fault-tolerantreal-time scheduling of platoons. The engine is provided with a set of assignment specifications, eachconsisting of a start time, a start position, a goal position and an arrival deadline. A vehicle is assignedto each assignment by a higher planning layer. The objective is to find fuel efficient routes and speedprofiles so that all vehicles arrive at theirs destinations before the deadline while minimizing its fuel consumption. Hereby, speed profiles are computed taking into account that vehicles can meet on commonparts of their routes and dynamically form platoons, which lowers their fuel consumption. In orderto account for new assignments and deviations, an updated plan is computed in real-time whenevernecessary.The potentially large scale combined with the strict timing requirements make computing such plans achallenging problem. The computation of plans is therefore divided into several stages. In the beginningroutes are computed and additional data on the routes is gathered. Based on this information, pairsof vehicles that can platoon are identified and plans involving two vehicles at a time are computed.These pairwise plans are first combined and then jointly optimized. Simulation studies demonstratethe potential of such an approach to significantly lower the fuel consumption of large vehicle fleets.Furthermore, the developed methods have been implemented and tested in a demonstrator systemusing both real and simulated vehicles.3 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 610990PublicContents1Introduction1.1 Objectives . . . . . . . . . . . . . . . . . .1.2 Scope . . . . . . . . . . . . . . . . . . . .1.3 Modeling . . . . . . . . . . . . . . . . . .1.4 Method for Platoon Coordination . . . . . .1.5 Off-Board System Component Architecture.55779122Extracting Candidate Platoon Pairs2.1 Candidate Platoon Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2 Culling Candidate Platoon Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3 Features and Classifiers for Culling Platoon Pairs . . . . . . . . . . . . . . . . . . . . .131315163Pairwise Adapted Vehicle Plans3.1 The Optimal Rendezvous Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2 Computing Adapted Vehicle Plans . . . . . . . . . . . . . . . . . . . . . . . . . . . .1920214 Computing Fuel-Efficient Vehicle Plans4.1 Combining Pairwise Plans to Save Fuel4.2 Exact Computation . . . . . . . . . .4.3 Heuristic Computation . . . . . . . .4.4 Joint Vehicle Plan Optimization . . . .5Implementation Aspects5.1 Incoming Assignments .5.2 Disturbances . . . . . .5.3 Deviations . . . . . . . .5.4 Handling of Time Delays.2425283334.37373838386 Driving Time and Rest Periods39740404248Evaluation in Simulation7.1 Extraction of Candidate Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.2 Integrated Simulation Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7.3 Demonstrator System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8 Summary and Conclusions504 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 610990PublicFig. 1: Two trucks with similar start-destination-pairs can meet en route and form a platoon.1.IntroductionThis report constitutes the Deliverable D5.2: Coordinated fault-tolerant real-time scheduling of platoons. It is the result of the work within the task T5.2, which belongs to WP5: Off-board system forplatoon coordination.1.1.ObjectivesIntegrating platooning into the road freight transport system leads to a challenging coordination problem. While there have been promising demonstrations of intra-platoon control systems the questionremains open where and when platoons should be formed. In some special cases, trucks have the entireor first part of their journey in common, for instance, when leaving from a distribution center. However,such special cases account only for a small fraction of road freight transport. Consider Figure 1. It showstrucks that travel between the same two regions but from different locations within the regions andat approximately the same time. These trucks can adjust their speeds slightly at the beginning of theirjourneys, form a platoon at the start of the common part of their routes and thus save fuel during mostof their journeys.This example motivates the need for a coordination scheme that helps trucks form platoons (Figure 2).Such a system should retain the advantages trucks have over other transportation systems, such as flexibility and independence, while maximizing the gains from platooning, specifically reduced fuel consumption. In particular the reduction in fuel consumption can be jeopardized if vehicles drive at increased velocities in order to catch up to their assigned platoon partners [14]. The objective of thisdeliverable is to develop a novel multi-objective decision making engine which provides as output the5 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 610990PublicFig. 2: Illustration of an integrated platoon coordination system. Trucks communicate via vehicle to infrastructure communication with the centralized platoon coordinator that coordinates the dynamic formation ofplatoons and integrates with logistic operators.most efficient arrangement of platoons, taking into consideration the prevailing information infrastructure. Efficiency is defined primarily in terms of fuel consumption, while strict requirements on arrivaltimes, computational effort as well as safety are taken into account. The derived system has to monitorthe network of available platoons, analyze their destinations and constraints in terms of slot times atterminals and the drivers’ resting times. Fuel optimized route decisions and speed recommendationsare given to the drivers. The overall framework thus has a hierarchical nature, in the sense that decisionmaking can be transferred from the back engine to the local user by means described above. Vehiclesmeet up and form platoons mainly by adjusting their speeds. Stopping at parking places or along theroad to wait for approaching vehicles will have to be avoided, but scheduled halts at resting places orservice areas could provide additional opportunities.6 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 6109901.2.PublicScopeThe results presented in this report have been published or are submitted in the following scientificpublications: S. van de Hoef, K. H. Johansson, and D. V. Dimarogonas. Fuel-optimal coordination of truck platooning based on shortest paths. In American Control Conference, pages 3740–3745, Chicago, IL,2015 S. van de Hoef, K. H. Johansson, and D. V. Dimarogonas. Coordinating truck platooning by clustering pairwise fuel-optimal plans. In 18th IEEE International Conference on Intelligent TransportationSystems, pages 408–415, 2015 S. van de Hoef, K. H. Johansson, and D. V. Dimarogonas. Computing feasible vehicle platooningopportunities for transport assignments. In 14-th IFAC Symposium on Control in TransportationSystems, 2016. To be published B. Besselink, V. Turri, S. van de Hoef, K.-Y. Liang, A. Alam, J. Mårtensson, and K. H. Johansson.Cyber-physical control of road freight transport. Proceedings of the IEEE, 104(5):1128–1141, 2016 K.-Y. Liang, S. van de Hoef, H. Terelius, V. Turri, B. Besselink, J. Mårtensson, and K. H. Johansson.Networked control challenges in collaborative road freight transport. European Journal of Control,2016. To be published S. van de Hoef, K. H. Johansson, and D. V. Dimarogonas. Fuel-efficient en route formation of truckplatoons. IEEE Transactions on Intelligent Transportation Systems, 2016. Submitted for publication S. van de Hoef. Fuel-Efficient Centralized Coordination of Truck Platooning. KTH, Royal Instituteof Technology, 2016. Licentiate ThesisThis report summarizes the important results from these publications. For additional details the readeris referred to these sources.This report focuses on the development of the optimization methods for coordinating platooning asoutlined above. In the course of this development certain practical aspects, such as different speedlimits along the route, have been simplified in order to allow for a concise mathematical representationand extensive Monte-Carlo simulations. Many of these details have been taken into account in thedemonstrator and the report indicates how the described methods can be adapted to handle them.1.3.ModelingWe have an index set Nc of finitely many transport assignments, each tied to a specific truck. A transportassignment A (P S , P D , tS , tD ) consists of a start position P S , a destination P D , a start time tS , andan arrival deadline tD . In addition a time window for start and departure can be considered. We modelthe road network as a directed graph Gr (Nr , Er ) with nodes Nr and edges Er . Nodes correspondto intersections or endpoints in the road network and edges correspond to road segments connecting7 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 610990Publicthese intersections. The function L : Er R maps each edge in Er to the length of the correspondingroad segment. A vehicle position is a pair (e, x) Er [0, L(e)] where e indicates the current roadsegment and x how far the vehicle has traveled along that segment.The goal is to compute fuel-efficient plans for the trucks that ensure arrival before each truck’s individual deadline. Each plan includes a route in the road network from start to destination and encodes apiecewise constant speed trajectory. The speed is constrained to a range of feasible speeds [vmin , vmax ],which depends on the road segment and is determined by legal restrictions, traffic, and physical limitations of the vehicle. In large parts of the report, we suppose this range to be the same for all vehicles androad segments. For the sake of this high-level planning, it is reasonable to assume that trucks changetheir speed instantaneously. The plans computed by the optimization engine are further refined onvehicle and platoon level without compromising the validity of the high-level plan.Definition 1 (Vehicle Plan). A vehicle plan P (e, v, t̂) consists of a route e, a speed sequence v, anda time sequence t̂. The route is a sequence of Ne edges in the road network e (e[1], . . . , e[Ne ]),e[i] Er . The speed sequence is a sequence of Nv speeds v (v[1], . . . , v[Nv ]), where speeds arewithin the feasible speed range 0 vmin v[i] vmax . The time sequence t̂ (t̂[1], . . . , t̂[Nv 1])defines when the speed changes. Speed v[i] is selected from t̂[i] until t̂[i 1].Note that Ne and Nv may be different for different vehicle plans.We want to compute a vehicle plan for each truck. A valid vehicle plan brings the truck from its startposition P S (eS , xS ), where it is at time tS , to its destination P D (eD , xD ) before its deadline tD .Vehicle plans are constrained by two conditions. The first condition requires the trip to start at the starttime t̂[1] tS and ends before the deadline t̂[Nv 1] tA tD . The second condition ensures thatthe truck arrives at its destination when the trip ends. The distance traveled isD : NXe 1L(e[i]) xD xS i 1NvXv[i](t̂[i 1] t̂[i]).i 1A vehicle trajectory consists of an edge trajectory and a linear position trajectory ξ. The edge trajectoryfor t [tS , tA ) is given by (t) e[j] where j depends on t and is the largest integer that satisfiesj 1XSZtL(e[i]) x i 1φ(τ )dτ,tSand where the speed trajectory φ(t) v[i] for t [t̂[i], t̂[i 1]), i {1, . . . , Nv }. The linear position,i.e., the second element of the position, at time t is given byZtφ(τ )dτ ξ(t) tSj 1XL(e[i]) xS .i 1When trucks platoon, their positions coincide in the model for high-level planning. The ordering anddistance control on platoon level is handled locally on vehicle level. Each platoon consists of a platoonleader and a number of platoon followers. We introduce the platoon trajectory πn : [tSn , tAn ) {0, 1}for truck n Nc . A platoon trajectory equals 1 when truck n is a platoon follower and 0 when it is a8 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 610990Publicplatoon leader or traveling alone. Thus, πn (t) 1 implies that there is another truck m Nc withm 6 n and ( n (t), ξn (t)) ( m (t), ξm (t)) and hence we neglect the physical dimension of the trucks.We refer to the combination of a vehicle plan and a platoon trajectory as a vehicle platoon plan.Figure 3 illustrates the relation between vehicle plans and assignments. The route connects the assignment’s start position P S and destination P D . The combination of the speed sequence v and the timesequence t̂ induces a position trajectory. When parts of these trajectories overlap, the vehicles canplatoon.We model the fuel consumption per distance traveled as a function of the speed and of whether thetruck is a platoon follower or not. A platoon leader has the same fuel consumption as a truck that travelsalone while a platoon follower has a reduced fuel consumption. We denote the fuel consumption perdistance traveled as f : [vmin , vmax ] {0, 1} R where(f0 (v) if p 0f (v, p) (1)fp (v) if p 1.The function f0 models the fuel consumption when the truck is a platoon leader or when it travels solo,and fp the fuel consumption when the truck is a platoon follower.We purposely omit that fuel consumption depends on road and vehicle parameters in order to keep thepresentation concise. In a future production system, the above simplified fuel would be automaticallycalibrated for each individual assignment using the data-driven fuel consumption model as describedin [13]. Then the simplified model is used for the efficient computation of vehicle plans. Before sendingvehicle plans to the fleet manager, the data driven fuel model can be used again to test the validity ofthe prediction by the simplified model.The problem that we want to solve is to find a vehicle plan for each vehicle, and we want to minimizethe combined fuel consumption of these plans. The total fuel consumption F (φn , πn ) associated tovehicle n’s plan is given byAZtnF (φn , πn ) f (φn (t), πn (t))φn (t)dt,(2)tSnwhere φn is the speed trajectory, πn the platoon trajectory, tSn the start time, and tAn the arrival time oftruck n as determined by the plan. The combined fuel consumption Fc is given by:XFc F (φn , πn ).(3)n NcOur primary goal is to compute vehicle plans that minimize Fc .1.4.Method for Platoon CoordinationConsider the centralized platoon coordination system in Figure 4. Assignment data is provided by thefleet operators through the back-end HMI and the fleet manager. We use the word fleet operator to referto a human working at a logistics company and who determines assignment for a number of vehicles.The optimization engine then computes fuel-efficient vehicle platoon plans for the trucks. These plans9 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION . 3: Each assignment consists of a start position and a destination in the network. Vehicle plans consistof a route, a speed sequence, and a time sequence. When the position trajectories of two vehicles partiallycoincide, these vehicles can form a platoon and save fuel. The upper plot shows an example of a road networkand start, destination, as well as the routes of four assignments. The lower plot shows the optimal trajectoriesalong the routes in three dimensions. When trajectories coincide, the vehicles platoon.10 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 610990PublicPlatoon CoordinatorAssignmentsAn (PnS , PnD , tSn , tDn)n 1n 2Vehicle PlansPn (en , vn , t̂n ).Fig. 4: Schematic of the platoon coordinator. Trucks provide their assignment data and the platoon coordinatorcomputes fuel efficient vehicle plans.are sent to the trucks through the fleet manager to be executed. This process is repeated wheneverthere is updated information, such as deviations from the plans and new assignments. The currentvehicle position is then the new start position of an assignment that is already being executed.The computation of the vehicle plans happens in six stages:1. Computation of the routes: fuel-efficient routes are computed by the route calculation engine. Italso provides speed bounds on the route links based on traffic information and legal restrictions.2. Gathering of route information: the speed bounds are further updated incorporating weatherinformation and the physical limits of the vehicle. If needed, the fuel-consumption model is alsocalibrated at the point for each assignment.3. Extraction of candidate platoon pairs: all pairs of assignments that can potentially platoon areidentified. In order for two vehicles to be able to platoon, their routes have to overlap at somepoint and the vehicles have to be able to meet on that common segment based on timing andspeed constraints.4. Computation of pairwise plans: many plans involving two vehicles are computed. The fuel savingsof these plans are recorded as the so-called coordination graph.5. Selection of pairwise plans: a consistent subset of the plans computed in the previous stage iscombined. The objective is to maximize the combined fuel-savings resulting from the selectionof pairwise plans.6. Joint vehicle platoon plan optimization: the selected pairwise plans are jointly optimized for low11 / 53
D5.2–Coordinated fault-tolerant real-time scheduling of platoonsCOMPANION 610990PublicFig. 5: Component architecture of the off-board system.fuel consumption. This stage only updates the segment traversal times while the platoon partnersremain the same as in the previous stage.Stages 1–2 can sometimes be omitted upon recalculation, depending on whether or not the remainderof the previously computed route is still valid. Furthermore, data such
D5.2–Coordinated fault-tolerant real-„me scheduling of platoons COMPANION 610990 Public Fig. 1: Two trucks with similar start-des„na„on-pairs can meet en route and form a platoon. 1.Introduc„on This report cons„tutes the Deliverable D5.2: Coordinated fa
