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