Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-2026 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file MSRoutingEngine.h
15 : /// @author Michael Behrisch
16 : /// @author Daniel Krajzewicz
17 : /// @author Jakob Erdmann
18 : /// @date Tue, 04 Dec 2007
19 : ///
20 : // A device that performs vehicle rerouting based on current edge speeds
21 : /****************************************************************************/
22 : #pragma once
23 : #include <config.h>
24 :
25 : #include <set>
26 : #include <vector>
27 : #include <map>
28 : #include <thread>
29 : #include <utils/common/SUMOTime.h>
30 : #include <utils/common/WrappingCommand.h>
31 : #include <utils/router/AStarRouter.h>
32 : #include <microsim/MSEdge.h>
33 : #include <microsim/MSRouterDefs.h>
34 : #include <memory>
35 : #include <atomic>
36 : #include <map>
37 : #include <mutex>
38 : namespace RoutingKit {
39 : struct CustomizableContractionHierarchyMetric;
40 : struct CustomizableContractionHierarchyPartialCustomization;
41 : }
42 :
43 : #ifdef HAVE_FOX
44 : #include <utils/foxtools/MFXWorkerThread.h>
45 : #endif
46 :
47 :
48 : // ===========================================================================
49 : // class declarations
50 : // ===========================================================================
51 : class MSTransportable;
52 : class MSVehicleType;
53 : class SUMOSAXAttributes;
54 :
55 : // ===========================================================================
56 : // class definitions
57 : // ===========================================================================
58 : /**
59 : * @class MSRoutingEngine
60 : * @brief A device that performs vehicle rerouting based on current edge speeds
61 : *
62 : * The routing-device system consists of in-vehicle devices that perform a routing
63 : * and a simulation-wide (static) methods for colecting edge weights.
64 : *
65 : * The edge weights container "myEdgeSpeeds" is pre-initialised as soon as one
66 : * device is built and is kept updated via an event that adapts it to the current
67 : * mean speed on the simulated network's edges.
68 : *
69 : * A device is assigned to a vehicle using the common explicit/probability - procedure.
70 : *
71 : * A device computes a new route for a vehicle as soon as the vehicle is inserted
72 : * (within "enterLaneAtInsertion") - and, if the given period is larger than 0 - each
73 : * x time steps where x is the period. This is triggered by an event that executes
74 : * "wrappedRerouteCommandExecute".
75 : */
76 : class MSRoutingEngine {
77 : public:
78 : typedef SUMOAbstractRouter<MSEdge, SUMOVehicle>::Prohibitions Prohibitions;
79 :
80 : /// @brief initialize constants for using myPriorityFactor
81 : static void initWeightConstants(const OptionsCont& oc);
82 :
83 : /// @brief intialize period edge weight update
84 : static void initWeightUpdate(SUMOTime lastAdaption = - 1);
85 :
86 : /// @brief initialize the edge weights if not done before
87 : static void initEdgeWeights(SUMOVehicleClass svc, SUMOTime lastAdaption = -1, int index = -1);
88 :
89 : /// @brief returns whether any edge weight updates will take place
90 : static bool hasEdgeUpdates() {
91 1412094 : return myEdgeWeightSettingCommand != nullptr;
92 : }
93 :
94 : /// @brief Information when the last edge weight adaptation occurred
95 : static SUMOTime getLastAdaptation() {
96 2276962 : return myLastAdaptation;
97 : }
98 :
99 : static bool haveExtras() {
100 7026881 : return myHaveExtras;
101 : }
102 :
103 : /// @brief apply cost modifications from randomness, priorityFactor and preferences
104 259985 : static inline void applyExtras(const MSEdge* const e, const SUMOVehicle* const v, SUMOTime step, double& effort) {
105 259985 : if (gWeightsRandomFactor != 1.) {
106 234071 : long long int key = v->getRandomSeed() ^ e->getNumericalID();
107 234071 : if (myDynamicRandomness) {
108 12259 : key ^= step;
109 : }
110 234071 : effort *= (1 + RandHelper::randHash(key) * (gWeightsRandomFactor - 1));
111 : }
112 259985 : if (myPriorityFactor != 0) {
113 : // lower priority should result in higher effort (and the edge with
114 : // minimum priority receives a factor of 1 + myPriorityFactor
115 5278 : const double relativeInversePrio = 1 - ((e->getPriority() - myMinEdgePriority) / myEdgePriorityRange);
116 5278 : effort *= 1 + relativeInversePrio * myPriorityFactor;
117 : }
118 259985 : if (gRoutingPreferences) {
119 22488 : effort /= MSNet::getInstance()->getPreference(e->getRoutingType(), v->getVTypeParameter());
120 : }
121 259985 : }
122 :
123 : /// @brief return the cached route or nullptr on miss
124 : static ConstMSRoutePtr getCachedRoute(const std::pair<const MSEdge*, const MSEdge*>& key);
125 :
126 : /// @brief the currently published (customized) CCH metric FOR A GIVEN
127 : /// vehicle class, or nullptr if that class has no CCH metric (then the
128 : /// caller falls back to A*). Lock-free: a plain atomic pointer read. The
129 : /// metric objects live for the whole run, so the raw pointer is always
130 : /// valid; the double buffer guarantees the pointer we hand out is not the
131 : /// one being customized. Called on the routing hot path -- allocation- and
132 : /// lock-free.
133 : static const RoutingKit::CustomizableContractionHierarchyMetric* getPublishedCCHMetric(SUMOVehicleClass vClass, SUMOTime time, const SUMOVehicle* veh);
134 :
135 : /// @brief the free-flow CCH metric for MSNet's routers (TraCI / triggers /
136 : /// GUI), keyed by vehicle type and filled through MSNet::getTravelTime
137 : /// with a reference vehicle of the type. Free-flow efforts are static, so
138 : /// each metric customizes once; a runtime permission change re-customizes
139 : /// in place. Returns nullptr (-> exact A* fallback) whenever the query
140 : /// cannot be served by a shared metric: individual or global TraCI edge
141 : /// weights, a routing mode other than DEFAULT, or a vehicle-specific
142 : /// type. MAIN-THREAD ONLY -- MSNet's routers never run on the worker
143 : /// threads, which is what allows the synchronous lazy build and repair.
144 : static const RoutingKit::CustomizableContractionHierarchyMetric* getFreeflowCCHMetric(SUMOVehicleClass vClass, SUMOTime time, const SUMOVehicle* veh);
145 :
146 : /// @brief the shared CCH topology, built on first demand (used by
147 : /// MSNet::getRouterTT to construct its CCH router; the device path builds
148 : /// it through initCCH)
149 : static MSCCHGraph* ensureCCHGraph();
150 :
151 : static void initRouter(SUMOVehicle* vehicle = nullptr);
152 :
153 : /// @brief initiate the rerouting, create router / thread pool on first use
154 : static void reroute(SUMOVehicle& vehicle, const SUMOTime currentTime, const std::string& info,
155 : const bool onInit = false, const bool silent = false, const Prohibitions& prohibited = {});
156 :
157 : /// @brief initiate the person rerouting, create router / thread pool on first use
158 : static void reroute(MSTransportable& t, const SUMOTime currentTime, const std::string& info,
159 : const bool onInit = false, const bool silent = false, const Prohibitions& prohibited = {});
160 :
161 : /// @brief adapt the known travel time for an edge
162 : static void setEdgeTravelTime(const MSEdge* const edge, const double travelTime);
163 :
164 : /// @brief deletes the router instance
165 : static void cleanup();
166 :
167 : /// @brief tears down the CCH state (myCCHLive/myCCHFreeflow/myCCHGraph)
168 : /// only -- the ref vehicles owned by the CCH metric families hold a raw
169 : /// MSVehicleType* that MSVehicleControl frees, so this MUST run before
170 : /// MSNet deletes its MSVehicleControl (cleanup() itself runs far later,
171 : /// from MSNet::clearAll(), so this is called separately and first; it is
172 : /// also idempotent/safe to call again from cleanup() afterwards since it
173 : /// nulls out the pointers it deletes)
174 : static void cleanupCCH();
175 :
176 : /// @brief returns whether any routing actions take place
177 : static bool isEnabled() {
178 280206758 : return !myWithTaz && myAdaptationInterval >= 0;
179 : }
180 :
181 : /// @brief return the vehicle router instance
182 : static MSVehicleRouter& getRouterTT(const int rngIndex,
183 : SUMOVehicleClass svc,
184 : const Prohibitions& prohibited = {});
185 :
186 : /// @brief return the person router instance
187 : static MSTransportableRouter& getIntermodalRouterTT(const int rngIndex,
188 : const Prohibitions& prohibited = {});
189 :
190 : /// @brief whether the router collects bicycle speeds
191 : static bool hasBikeSpeeds() {
192 678 : return myBikeSpeeds;
193 : }
194 :
195 : /** @brief Returns the effort to pass an edge
196 : *
197 : * This method is given to the used router in order to obtain the efforts
198 : * to pass an edge from the internal edge weights container.
199 : *
200 : * The time is not used, here, as the current simulation state is
201 : * used in an aggregated way.
202 : *
203 : * @param[in] e The edge for which the effort to be passed shall be returned
204 : * @param[in] v The vehicle that is rerouted
205 : * @param[in] t The time for which the effort shall be returned
206 : * @return The effort (time to pass in this case) for an edge
207 : * @see DijkstraRouter_ByProxi
208 : */
209 : static double getEffort(const MSEdge* const e, const SUMOVehicle* const v, double t);
210 : static double getEffortBike(const MSEdge* const e, const SUMOVehicle* const v, double t);
211 : static double getEffortExtra(const MSEdge* const e, const SUMOVehicle* const v, double t);
212 : static SUMOAbstractRouter<MSEdge, SUMOVehicle>::Operation myEffortFunc;
213 :
214 : /// @brief return current travel speed assumption
215 : static double getAssumedSpeed(const MSEdge* edge, const SUMOVehicle* veh);
216 :
217 : /// @brief whether taz-routing is enabled
218 : static bool withTaz() {
219 577549 : return myWithTaz;
220 : }
221 :
222 : /// @brief record actual travel time for an edge
223 : static void addEdgeTravelTime(const MSEdge& edge, const SUMOTime travelTime);
224 :
225 : /** @brief Saves the state (i.e. recorded speeds)
226 : *
227 : * @param[in] out The OutputDevice to write the information into
228 : */
229 : static void saveState(OutputDevice& out);
230 :
231 : /** @brief Loads the state
232 : *
233 : * @param[in] attrs XML attributes describing the current state
234 : */
235 : static void loadState(const SUMOSAXAttributes& attrs);
236 :
237 : #ifdef HAVE_FOX
238 : static void waitForAll();
239 : #endif
240 :
241 :
242 : private:
243 : #ifdef HAVE_FOX
244 : /**
245 : * @class RoutingTask
246 : * @brief the routing task which mainly calls reroute of the vehicle
247 : */
248 : class RoutingTask : public MFXWorkerThread::Task {
249 : public:
250 171961 : RoutingTask(SUMOVehicle& v, const SUMOTime time, const std::string& info,
251 : const bool onInit, const bool silent, const Prohibitions& prohibited)
252 171961 : : myVehicle(v), myTime(time), myInfo(info), myOnInit(onInit), mySilent(silent), myProhibited(prohibited) {}
253 : void run(MFXWorkerThread* context);
254 : private:
255 : SUMOVehicle& myVehicle;
256 : const SUMOTime myTime;
257 : const std::string myInfo;
258 : const bool myOnInit;
259 : const bool mySilent;
260 : const Prohibitions myProhibited;
261 : private:
262 : /// @brief Invalidated assignment operator.
263 : RoutingTask& operator=(const RoutingTask&) = delete;
264 : };
265 :
266 : #endif
267 :
268 : /// @name Network state adaptation
269 : /// @{
270 :
271 : /** @brief Adapt edge efforts by the current edge states
272 : *
273 : * This method is called by the event handler at the end of a simulation
274 : * step. The current edge weights are combined with the previously stored.
275 : *
276 : * @param[in] currentTime The current simulation time
277 : * @return The offset to the next call (always 1 in this case - edge weights are updated each time step)
278 : * @todo Describe how the weights are adapted
279 : * @see MSEventHandler
280 : * @see StaticCommand
281 : */
282 : static SUMOTime adaptEdgeEfforts(SUMOTime currentTime);
283 :
284 : static double patchSpeedForTurns(const MSEdge* edge, double currSpeed);
285 : /// @}
286 :
287 : /// @brief initialized edge speed storage into the given containers
288 : static void _initEdgeWeights(std::vector<double>& edgeSpeeds, std::vector<std::vector<double> >& pastEdgeSpeeds);
289 :
290 : /// @brief returns RNG associated with the current thread
291 : static SumoRNG* getThreadRNG();
292 :
293 : private:
294 : /// @brief The weights adaptation/overwriting command
295 : static Command* myEdgeWeightSettingCommand;
296 :
297 : /// @brief Information which weight prior edge efforts have
298 : static double myAdaptationWeight;
299 :
300 : /// @brief At which time interval the edge weights get updated
301 : static SUMOTime myAdaptationInterval;
302 :
303 : /// @brief Information when the last edge weight adaptation occurred
304 : static SUMOTime myLastAdaptation;
305 :
306 : /// @brief The number of steps for averaging edge speeds (ring-buffer)
307 : static int myAdaptationSteps;
308 :
309 : /// @brief The current index in the pastEdgeSpeed ring-buffer
310 : static int myAdaptationStepsIndex;
311 :
312 : typedef std::pair<SUMOTime, int> TimeAndCount;
313 :
314 : /// @brief The container of edge speeds
315 : static std::vector<double> myEdgeSpeeds;
316 : static std::vector<double> myEdgeBikeSpeeds;
317 :
318 : /// @brief Sum of travel times experienced by equipped vehicles for each edge
319 : static std::vector<TimeAndCount> myEdgeTravelTimes;
320 :
321 : /// @brief The container of past edge speeds (when using a simple moving average)
322 : static std::vector<std::vector<double> > myPastEdgeSpeeds;
323 : static std::vector<std::vector<double> > myPastEdgeBikeSpeeds;
324 :
325 : /// @brief whether taz shall be used at initial rerouting
326 : static bool myWithTaz;
327 :
328 : /// @brief whether separate speeds for bicycles shall be tracked
329 : static bool myBikeSpeeds;
330 :
331 : /// @brief The router to use
332 : static MSRouterProvider* myRouterProvider;
333 :
334 : /// @brief The container of pre-calculated routes
335 : static std::map<std::pair<const MSEdge*, const MSEdge*>, ConstMSRoutePtr> myCachedRoutes;
336 :
337 : /// @brief Coefficient for factoring edge priority into routing weight
338 : static double myPriorityFactor;
339 :
340 : /// @brief Minimum priority for all edges
341 : static double myMinEdgePriority;
342 : /// @brief the difference between maximum and minimum priority for all edges
343 : static double myEdgePriorityRange;
344 :
345 : /// @brief whether randomness varies over time
346 : static bool myDynamicRandomness;
347 :
348 : /// @brief whether extra routing cost modifications are configured
349 : static bool myHaveExtras;
350 :
351 : #ifdef HAVE_FOX
352 : /// @brief Mutex for accessing the route cache
353 : static FXMutex myRouteCacheMutex;
354 : #endif
355 :
356 : /// @brief the immutable shared CCH topology (built once), or nullptr if inactive
357 : static MSCCHGraph* myCCHGraph;
358 : /// @brief the rerouting device's LIVE metric family over the adaptive
359 : /// speed tables (see utils/router/CCHMetricFamily.h): metrics are keyed
360 : /// by vehicle TYPE -- mirroring duarouter's keying -- and filled with an
361 : /// OWNED reference vehicle of the type, so the type's maximum speed,
362 : /// vClass speed limits, routing preferences, the bicycle speed table and
363 : /// one frozen weights.random-factor realization are exact per metric.
364 : /// nullptr until initCCH.
365 : static MSCCHMetricFamily* myCCHLive;
366 : /// @brief the STATIC free-flow metric family behind MSNet's routers
367 : /// (TraCI / triggers / GUI, all main-thread); built on first query
368 : static MSCCHMetricFamily* myCCHFreeflow;
369 : /// @brief construct the unregistered effort-reference vehicle for a
370 : /// type: never counted, inserted or given devices, with the type's mean
371 : /// speed factor and a deterministic random seed (the family's
372 : /// RefVehicleFactory; the slot picks the frozen random-factor
373 : /// realization, see device.rerouting.cch-ensemble)
374 : static SUMOVehicle* buildCCHRefVehicle(const MSVehicleType* type, int slot);
375 : /// @brief build the shared CCH + the live family with one metric per
376 : /// loaded type, publish initial metrics
377 : static void initCCH();
378 :
379 : public:
380 : /// @brief a runtime permission change (closure / re-opening) hit this
381 : /// edge: invalidate the graph's primed connection masks and both
382 : /// families' metrics (queries divert to the exact fallback until the
383 : /// families re-customize)
384 : static void invalidateCCHEdge(const MSEdge* e);
385 : private:
386 :
387 : private:
388 : /// @brief Invalidated copy constructor.
389 : MSRoutingEngine(const MSRoutingEngine&);
390 :
391 : /// @brief Invalidated assignment operator.
392 : MSRoutingEngine& operator=(const MSRoutingEngine&);
393 :
394 :
395 : };
|
