Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-2025 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/MSRouterDefs.h>
33 :
34 : #ifdef HAVE_FOX
35 : #include <utils/foxtools/MFXWorkerThread.h>
36 : #endif
37 :
38 :
39 : // ===========================================================================
40 : // class declarations
41 : // ===========================================================================
42 : class MSTransportable;
43 : class SUMOSAXAttributes;
44 :
45 : // ===========================================================================
46 : // class definitions
47 : // ===========================================================================
48 : /**
49 : * @class MSRoutingEngine
50 : * @brief A device that performs vehicle rerouting based on current edge speeds
51 : *
52 : * The routing-device system consists of in-vehicle devices that perform a routing
53 : * and a simulation-wide (static) methods for colecting edge weights.
54 : *
55 : * The edge weights container "myEdgeSpeeds" is pre-initialised as soon as one
56 : * device is built and is kept updated via an event that adapts it to the current
57 : * mean speed on the simulated network's edges.
58 : *
59 : * A device is assigned to a vehicle using the common explicit/probability - procedure.
60 : *
61 : * A device computes a new route for a vehicle as soon as the vehicle is inserted
62 : * (within "enterLaneAtInsertion") - and, if the given period is larger than 0 - each
63 : * x time steps where x is the period. This is triggered by an event that executes
64 : * "wrappedRerouteCommandExecute".
65 : */
66 : class MSRoutingEngine {
67 : public:
68 : typedef std::map<const MSEdge*, double> Prohibitions;
69 :
70 : /// @brief intialize period edge weight update
71 : static void initWeightUpdate();
72 :
73 : /// @brief initialize the edge weights if not done before
74 : static void initEdgeWeights(SUMOVehicleClass svc, SUMOTime lastAdaption = -1, int index = -1);
75 :
76 : /// @brief returns whether any edge weight updates will take place
77 : static bool hasEdgeUpdates() {
78 1566513 : return myEdgeWeightSettingCommand != nullptr;
79 : }
80 :
81 : /// @brief Information when the last edge weight adaptation occurred
82 : static SUMOTime getLastAdaptation() {
83 2319134 : return myLastAdaptation;
84 : }
85 :
86 : /// @brief return the cached route or nullptr on miss
87 : static ConstMSRoutePtr getCachedRoute(const std::pair<const MSEdge*, const MSEdge*>& key);
88 :
89 : static void initRouter(SUMOVehicle* vehicle = nullptr);
90 :
91 : /// @brief initiate the rerouting, create router / thread pool on first use
92 : static void reroute(SUMOVehicle& vehicle, const SUMOTime currentTime, const std::string& info,
93 : const bool onInit = false, const bool silent = false, const Prohibitions& prohibited = {});
94 :
95 : /// @brief initiate the person rerouting, create router / thread pool on first use
96 : static void reroute(MSTransportable& t, const SUMOTime currentTime, const std::string& info,
97 : const bool onInit = false, const bool silent = false, const Prohibitions& prohibited = {});
98 :
99 : /// @brief adapt the known travel time for an edge
100 : static void setEdgeTravelTime(const MSEdge* const edge, const double travelTime);
101 :
102 : /// @brief deletes the router instance
103 : static void cleanup();
104 :
105 : /// @brief returns whether any routing actions take place
106 : static bool isEnabled() {
107 127251948 : return !myWithTaz && myAdaptationInterval >= 0;
108 : }
109 :
110 : /// @brief return the vehicle router instance
111 : static MSVehicleRouter& getRouterTT(const int rngIndex,
112 : SUMOVehicleClass svc,
113 : const Prohibitions& prohibited = {});
114 :
115 : /// @brief return the person router instance
116 : static MSTransportableRouter& getIntermodalRouterTT(const int rngIndex,
117 : const Prohibitions& prohibited = {});
118 :
119 : /** @brief Returns the effort to pass an edge
120 : *
121 : * This method is given to the used router in order to obtain the efforts
122 : * to pass an edge from the internal edge weights container.
123 : *
124 : * The time is not used, here, as the current simulation state is
125 : * used in an aggregated way.
126 : *
127 : * @param[in] e The edge for which the effort to be passed shall be returned
128 : * @param[in] v The vehicle that is rerouted
129 : * @param[in] t The time for which the effort shall be returned
130 : * @return The effort (time to pass in this case) for an edge
131 : * @see DijkstraRouter_ByProxi
132 : */
133 : static double getEffort(const MSEdge* const e, const SUMOVehicle* const v, double t);
134 : static double getEffortBike(const MSEdge* const e, const SUMOVehicle* const v, double t);
135 : static double getEffortExtra(const MSEdge* const e, const SUMOVehicle* const v, double t);
136 : static SUMOAbstractRouter<MSEdge, SUMOVehicle>::Operation myEffortFunc;
137 :
138 : /// @brief return current travel speed assumption
139 : static double getAssumedSpeed(const MSEdge* edge, const SUMOVehicle* veh);
140 :
141 : /// @brief whether taz-routing is enabled
142 : static bool withTaz() {
143 441495 : return myWithTaz;
144 : }
145 :
146 : /// @brief record actual travel time for an edge
147 : static void addEdgeTravelTime(const MSEdge& edge, const SUMOTime travelTime);
148 :
149 : /// @brief initialize RNG for the gui thread
150 : static void initGUIThreadRNG();
151 :
152 : /** @brief Saves the state (i.e. recorded speeds)
153 : *
154 : * @param[in] out The OutputDevice to write the information into
155 : */
156 : static void saveState(OutputDevice& out);
157 :
158 : /** @brief Loads the state
159 : *
160 : * @param[in] attrs XML attributes describing the current state
161 : */
162 : static void loadState(const SUMOSAXAttributes& attrs);
163 :
164 : #ifdef HAVE_FOX
165 : static void waitForAll();
166 : #endif
167 :
168 :
169 : private:
170 : #ifdef HAVE_FOX
171 : /**
172 : * @class RoutingTask
173 : * @brief the routing task which mainly calls reroute of the vehicle
174 : */
175 : class RoutingTask : public MFXWorkerThread::Task {
176 : public:
177 186932 : RoutingTask(SUMOVehicle& v, const SUMOTime time, const std::string& info,
178 : const bool onInit, const bool silent, const Prohibitions& prohibited)
179 186932 : : myVehicle(v), myTime(time), myInfo(info), myOnInit(onInit), mySilent(silent), myProhibited(prohibited) {}
180 : void run(MFXWorkerThread* context);
181 : private:
182 : SUMOVehicle& myVehicle;
183 : const SUMOTime myTime;
184 : const std::string myInfo;
185 : const bool myOnInit;
186 : const bool mySilent;
187 : const Prohibitions myProhibited;
188 : private:
189 : /// @brief Invalidated assignment operator.
190 : RoutingTask& operator=(const RoutingTask&) = delete;
191 : };
192 :
193 : /**
194 : * @class InitTask
195 : * @brief setup RNGs for each thread (with proper locking so we don't need
196 : * locking later */
197 : class InitTask : public MFXWorkerThread::Task {
198 : public:
199 3416 : InitTask() {}
200 : void run(MFXWorkerThread* context);
201 : private:
202 : /// @brief Invalidated assignment operator.
203 : RoutingTask& operator=(const RoutingTask&) = delete;
204 : };
205 : #endif
206 :
207 : /// @name Network state adaptation
208 : /// @{
209 :
210 : /** @brief Adapt edge efforts by the current edge states
211 : *
212 : * This method is called by the event handler at the end of a simulation
213 : * step. The current edge weights are combined with the previously stored.
214 : *
215 : * @param[in] currentTime The current simulation time
216 : * @return The offset to the next call (always 1 in this case - edge weights are updated each time step)
217 : * @todo Describe how the weights are adapted
218 : * @see MSEventHandler
219 : * @see StaticCommand
220 : */
221 : static SUMOTime adaptEdgeEfforts(SUMOTime currentTime);
222 :
223 : static double patchSpeedForTurns(const MSEdge* edge, double currSpeed);
224 : /// @}
225 :
226 : /// @brief initialized edge speed storage into the given containers
227 : static void _initEdgeWeights(std::vector<double>& edgeSpeeds, std::vector<std::vector<double> >& pastEdgeSpeeds);
228 :
229 : /// @brief returns RNG associated with the current thread
230 : static SumoRNG* getThreadRNG();
231 :
232 : private:
233 : /// @brief The weights adaptation/overwriting command
234 : static Command* myEdgeWeightSettingCommand;
235 :
236 : /// @brief Information which weight prior edge efforts have
237 : static double myAdaptationWeight;
238 :
239 : /// @brief At which time interval the edge weights get updated
240 : static SUMOTime myAdaptationInterval;
241 :
242 : /// @brief Information when the last edge weight adaptation occurred
243 : static SUMOTime myLastAdaptation;
244 :
245 : /// @brief The number of steps for averaging edge speeds (ring-buffer)
246 : static int myAdaptationSteps;
247 :
248 : /// @brief The current index in the pastEdgeSpeed ring-buffer
249 : static int myAdaptationStepsIndex;
250 :
251 : typedef std::pair<SUMOTime, int> TimeAndCount;
252 :
253 : /// @brief The container of edge speeds
254 : static std::vector<double> myEdgeSpeeds;
255 : static std::vector<double> myEdgeBikeSpeeds;
256 :
257 : /// @brief Sum of travel times experienced by equipped vehicles for each edge
258 : static std::vector<TimeAndCount> myEdgeTravelTimes;
259 :
260 : /// @brief The container of past edge speeds (when using a simple moving average)
261 : static std::vector<std::vector<double> > myPastEdgeSpeeds;
262 : static std::vector<std::vector<double> > myPastEdgeBikeSpeeds;
263 :
264 : /// @brief whether taz shall be used at initial rerouting
265 : static bool myWithTaz;
266 :
267 : /// @brief whether separate speeds for bicycles shall be tracked
268 : static bool myBikeSpeeds;
269 :
270 : /// @brief The router to use
271 : static MSRouterProvider* myRouterProvider;
272 :
273 : static std::map<std::thread::id, SumoRNG*> myThreadRNGs;
274 : static bool myHaveRoutingThreads;
275 :
276 : /// @brief The container of pre-calculated routes
277 : static std::map<std::pair<const MSEdge*, const MSEdge*>, ConstMSRoutePtr> myCachedRoutes;
278 :
279 : /// @brief Coefficient for factoring edge priority into routing weight
280 : static double myPriorityFactor;
281 :
282 : /// @brief Minimum priority for all edges
283 : static double myMinEdgePriority;
284 : /// @brief the difference between maximum and minimum priority for all edges
285 : static double myEdgePriorityRange;
286 :
287 : #ifdef HAVE_FOX
288 : /// @brief Mutex for accessing the route cache
289 : static FXMutex myRouteCacheMutex;
290 : #endif
291 :
292 : private:
293 : /// @brief Invalidated copy constructor.
294 : MSRoutingEngine(const MSRoutingEngine&);
295 :
296 : /// @brief Invalidated assignment operator.
297 : MSRoutingEngine& operator=(const MSRoutingEngine&);
298 :
299 :
300 : };
|
