1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2007-2019 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
10 /// @file MSRoutingEngine.cpp
11 /// @author Michael Behrisch
12 /// @author Daniel Krajzewicz
13 /// @author Laura Bieker
14 /// @author Christoph Sommer
15 /// @author Jakob Erdmann
16 /// @date Tue, 04 Dec 2007
17 /// @version $Id$
18 ///
19 // A device that performs vehicle rerouting based on current edge speeds
20 /****************************************************************************/
21
22 // ===========================================================================
23 // included modules
24 // ===========================================================================
25 #include <config.h>
26
27 #include "MSRoutingEngine.h"
28 #include <microsim/MSNet.h>
29 #include <microsim/MSLane.h>
30 #include <microsim/MSEdge.h>
31 #include <microsim/MSEdgeControl.h>
32 #include <microsim/MSEventControl.h>
33 #include <microsim/MSGlobals.h>
34 #include <microsim/MSVehicleControl.h>
35 #include <utils/options/OptionsCont.h>
36 #include <utils/common/WrappingCommand.h>
37 #include <utils/common/StaticCommand.h>
38 #include <utils/common/StringUtils.h>
39 #include <utils/xml/SUMOSAXAttributes.h>
40 #include <utils/router/DijkstraRouter.h>
41 #include <utils/router/AStarRouter.h>
42 #include <utils/router/CHRouter.h>
43 #include <utils/router/CHRouterWrapper.h>
44
45
46 // ===========================================================================
47 // static member variables
48 // ===========================================================================
49 std::vector<double> MSRoutingEngine::myEdgeSpeeds;
50 std::vector<std::vector<double> > MSRoutingEngine::myPastEdgeSpeeds;
51 Command* MSRoutingEngine::myEdgeWeightSettingCommand = nullptr;
52 double MSRoutingEngine::myAdaptationWeight;
53 int MSRoutingEngine::myAdaptationSteps;
54 int MSRoutingEngine::myAdaptationStepsIndex = 0;
55 SUMOTime MSRoutingEngine::myAdaptationInterval = -1;
56 SUMOTime MSRoutingEngine::myLastAdaptation = -1;
57 bool MSRoutingEngine::myWithTaz;
58 SUMOAbstractRouter<MSEdge, SUMOVehicle>* MSRoutingEngine::myRouter = nullptr;
59 AStarRouter<MSEdge, SUMOVehicle, SUMOAbstractRouterPermissions<MSEdge, SUMOVehicle> >* MSRoutingEngine::myRouterWithProhibited = nullptr;
60 std::map<std::pair<const MSEdge*, const MSEdge*>, const MSRoute*> MSRoutingEngine::myCachedRoutes;
61 #ifdef HAVE_FOX
62 FXWorkerThread::Pool MSRoutingEngine::myThreadPool;
63 #endif
64
65
66 // ===========================================================================
67 // method definitions
68 // ===========================================================================
69 // ---------------------------------------------------------------------------
70 // static initialisation methods
71 // ---------------------------------------------------------------------------
72 void
initWeightUpdate()73 MSRoutingEngine::initWeightUpdate() {
74 if (myAdaptationInterval == -1) {
75 myEdgeWeightSettingCommand = nullptr;
76 myEdgeSpeeds.clear();
77 myAdaptationInterval = -1;
78 myAdaptationSteps = -1;
79 myLastAdaptation = -1;
80 const OptionsCont& oc = OptionsCont::getOptions();
81 myWithTaz = oc.getBool("device.rerouting.with-taz");
82 myAdaptationInterval = string2time(oc.getString("device.rerouting.adaptation-interval"));
83 myAdaptationWeight = oc.getFloat("device.rerouting.adaptation-weight");
84 const SUMOTime period = string2time(oc.getString("device.rerouting.period"));
85 if (myAdaptationWeight < 1. && myAdaptationInterval > 0) {
86 myEdgeWeightSettingCommand = new StaticCommand<MSRoutingEngine>(&MSRoutingEngine::adaptEdgeEfforts);
87 MSNet::getInstance()->getEndOfTimestepEvents()->addEvent(myEdgeWeightSettingCommand);
88 } else if (period > 0) {
89 WRITE_WARNING("Rerouting is useless if the edge weights do not get updated!");
90 }
91 OutputDevice::createDeviceByOption("device.rerouting.output", "weights", "meandata_file.xsd");
92 }
93 }
94
95 // ---------------------------------------------------------------------------
96 // MSRoutingEngine-methods
97 // ---------------------------------------------------------------------------
98 void
initEdgeWeights()99 MSRoutingEngine::initEdgeWeights() {
100 if (myEdgeSpeeds.empty()) {
101 const OptionsCont& oc = OptionsCont::getOptions();
102 if (myAdaptationWeight == 0 || !oc.isDefault("device.rerouting.adaptation-steps")) {
103 myAdaptationSteps = oc.getInt("device.rerouting.adaptation-steps");
104 }
105 const bool useLoaded = oc.getBool("device.rerouting.init-with-loaded-weights");
106 const double currentSecond = SIMTIME;
107 for (const MSEdge* const edge : MSNet::getInstance()->getEdgeControl().getEdges()) {
108 while (edge->getNumericalID() >= (int)myEdgeSpeeds.size()) {
109 myEdgeSpeeds.push_back(0);
110 if (myAdaptationSteps > 0) {
111 myPastEdgeSpeeds.push_back(std::vector<double>());
112 }
113 }
114 if (useLoaded) {
115 myEdgeSpeeds[edge->getNumericalID()] = edge->getLength() / MSNet::getTravelTime(edge, nullptr, currentSecond);
116 } else {
117 myEdgeSpeeds[edge->getNumericalID()] = edge->getMeanSpeed();
118 }
119 if (myAdaptationSteps > 0) {
120 myPastEdgeSpeeds[edge->getNumericalID()] = std::vector<double>(myAdaptationSteps, myEdgeSpeeds[edge->getNumericalID()]);
121 }
122 }
123 myLastAdaptation = MSNet::getInstance()->getCurrentTimeStep();
124 }
125 }
126
127
128 double
getEffort(const MSEdge * const e,const SUMOVehicle * const v,double)129 MSRoutingEngine::getEffort(const MSEdge* const e, const SUMOVehicle* const v, double) {
130 const int id = e->getNumericalID();
131 if (id < (int)myEdgeSpeeds.size()) {
132 double effort = MAX2(e->getLength() / MAX2(myEdgeSpeeds[id], NUMERICAL_EPS), e->getMinimumTravelTime(v));
133 if (gWeightsRandomFactor != 1.) {
134 effort *= RandHelper::rand(1., gWeightsRandomFactor);
135 }
136 return effort;
137 }
138 return 0.;
139 }
140
141
142 double
getAssumedSpeed(const MSEdge * edge)143 MSRoutingEngine::getAssumedSpeed(const MSEdge* edge) {
144 return edge->getLength() / getEffort(edge, nullptr, 0);
145 }
146
147
148 SUMOTime
adaptEdgeEfforts(SUMOTime currentTime)149 MSRoutingEngine::adaptEdgeEfforts(SUMOTime currentTime) {
150 initEdgeWeights();
151 if (MSNet::getInstance()->getVehicleControl().getDepartedVehicleNo() == 0) {
152 return myAdaptationInterval;
153 }
154 std::map<std::pair<const MSEdge*, const MSEdge*>, const MSRoute*>::iterator it = myCachedRoutes.begin();
155 for (; it != myCachedRoutes.end(); ++it) {
156 it->second->release();
157 }
158 myCachedRoutes.clear();
159 const MSEdgeVector& edges = MSNet::getInstance()->getEdgeControl().getEdges();
160 if (myAdaptationSteps > 0) {
161 // moving average
162 for (MSEdgeVector::const_iterator i = edges.begin(); i != edges.end(); ++i) {
163 if ((*i)->isDelayed()) {
164 const int id = (*i)->getNumericalID();
165 const double currSpeed = (*i)->getMeanSpeed();
166 myEdgeSpeeds[id] += (currSpeed - myPastEdgeSpeeds[id][myAdaptationStepsIndex]) / myAdaptationSteps;
167 myPastEdgeSpeeds[id][myAdaptationStepsIndex] = currSpeed;
168 }
169 }
170 myAdaptationStepsIndex = (myAdaptationStepsIndex + 1) % myAdaptationSteps;
171 } else {
172 // exponential moving average
173 const double newWeightFactor = (double)(1. - myAdaptationWeight);
174 for (MSEdgeVector::const_iterator i = edges.begin(); i != edges.end(); ++i) {
175 if ((*i)->isDelayed()) {
176 const int id = (*i)->getNumericalID();
177 const double currSpeed = (*i)->getMeanSpeed();
178 if (currSpeed != myEdgeSpeeds[id]) {
179 myEdgeSpeeds[id] = myEdgeSpeeds[id] * myAdaptationWeight + currSpeed * newWeightFactor;
180 }
181 }
182 }
183 }
184 myLastAdaptation = currentTime + DELTA_T; // because we run at the end of the time step
185 if (OptionsCont::getOptions().isSet("device.rerouting.output")) {
186 OutputDevice& dev = OutputDevice::getDeviceByOption("device.rerouting.output");
187 dev.openTag(SUMO_TAG_INTERVAL);
188 dev.writeAttr(SUMO_ATTR_ID, "device.rerouting");
189 dev.writeAttr(SUMO_ATTR_BEGIN, STEPS2TIME(currentTime));
190 dev.writeAttr(SUMO_ATTR_END, STEPS2TIME(currentTime + myAdaptationInterval));
191 for (const MSEdge* e : edges) {
192 dev.openTag(SUMO_TAG_EDGE);
193 dev.writeAttr(SUMO_ATTR_ID, e->getID());
194 dev.writeAttr("traveltime", getEffort(e, nullptr, STEPS2TIME(currentTime)));
195 dev.closeTag();
196 }
197 dev.closeTag();
198 }
199 return myAdaptationInterval;
200 }
201
202
203 const MSRoute*
getCachedRoute(const std::pair<const MSEdge *,const MSEdge * > & key)204 MSRoutingEngine::getCachedRoute(const std::pair<const MSEdge*, const MSEdge*>& key) {
205 auto routeIt = myCachedRoutes.find(key);
206 if (routeIt != myCachedRoutes.end()) {
207 return routeIt->second;
208 }
209 return nullptr;
210 }
211
212
213 void
reroute(SUMOVehicle & vehicle,const SUMOTime currentTime,const bool onInit)214 MSRoutingEngine::reroute(SUMOVehicle& vehicle, const SUMOTime currentTime, const bool onInit) {
215 #ifdef HAVE_FOX
216 const bool needThread = (myRouter == nullptr && myThreadPool.isFull());
217 #else
218 const bool needThread = true;
219 #endif
220 if (needThread && myRouter == nullptr) {
221 OptionsCont& oc = OptionsCont::getOptions();
222 const std::string routingAlgorithm = oc.getString("routing-algorithm");
223 const bool mayHaveRestrictions = MSNet::getInstance()->hasPermissions() || oc.getInt("remote-port") != 0;
224 if (routingAlgorithm == "dijkstra") {
225 if (mayHaveRestrictions) {
226 myRouter = new DijkstraRouter<MSEdge, SUMOVehicle, SUMOAbstractRouterPermissions<MSEdge, SUMOVehicle> >(
227 MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort);
228 } else {
229 myRouter = new DijkstraRouter<MSEdge, SUMOVehicle, SUMOAbstractRouter<MSEdge, SUMOVehicle> >(
230 MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort);
231 }
232 } else if (routingAlgorithm == "astar") {
233 if (mayHaveRestrictions) {
234 typedef AStarRouter<MSEdge, SUMOVehicle, SUMOAbstractRouterPermissions<MSEdge, SUMOVehicle> > AStar;
235 std::shared_ptr<const AStar::LookupTable> lookup;
236 if (oc.isSet("astar.all-distances")) {
237 lookup = std::make_shared<const AStar::FLT>(oc.getString("astar.all-distances"), (int)MSEdge::getAllEdges().size());
238 } else if (oc.isSet("astar.landmark-distances")) {
239 const double speedFactor = vehicle.getChosenSpeedFactor();
240 // we need an exemplary vehicle with speedFactor 1
241 vehicle.setChosenSpeedFactor(1);
242 CHRouterWrapper<MSEdge, SUMOVehicle, SUMOAbstractRouterPermissions<MSEdge, SUMOVehicle> > router(
243 MSEdge::getAllEdges(), true, &MSNet::getTravelTime,
244 string2time(oc.getString("begin")), string2time(oc.getString("end")), std::numeric_limits<int>::max(), 1);
245 lookup = std::make_shared<const AStar::LMLT>(oc.getString("astar.landmark-distances"), MSEdge::getAllEdges(), &router, &vehicle, "", oc.getInt("device.rerouting.threads"));
246 vehicle.setChosenSpeedFactor(speedFactor);
247 }
248 myRouter = new AStar(MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort, lookup);
249 } else {
250 typedef AStarRouter<MSEdge, SUMOVehicle, SUMOAbstractRouter<MSEdge, SUMOVehicle> > AStar;
251 std::shared_ptr<const AStar::LookupTable> lookup;
252 if (oc.isSet("astar.all-distances")) {
253 lookup = std::shared_ptr<const AStar::LookupTable> (new AStar::FLT(oc.getString("astar.all-distances"), (int)MSEdge::getAllEdges().size()));
254 } else if (oc.isSet("astar.landmark-distances")) {
255 const double speedFactor = vehicle.getChosenSpeedFactor();
256 // we need an exemplary vehicle with speedFactor 1
257 vehicle.setChosenSpeedFactor(1);
258 CHRouterWrapper<MSEdge, SUMOVehicle, SUMOAbstractRouter<MSEdge, SUMOVehicle> > router(
259 MSEdge::getAllEdges(), true, &MSNet::getTravelTime,
260 string2time(oc.getString("begin")), string2time(oc.getString("end")), std::numeric_limits<int>::max(), 1);
261 lookup = std::make_shared<const AStar::LMLT>(oc.getString("astar.landmark-distances"), MSEdge::getAllEdges(), &router, &vehicle, "", oc.getInt("device.rerouting.threads"));
262 vehicle.setChosenSpeedFactor(speedFactor);
263 }
264 myRouter = new AStar(MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort, lookup);
265 }
266 } else if (routingAlgorithm == "CH") {
267 const SUMOTime weightPeriod = myAdaptationInterval > 0 ? myAdaptationInterval : std::numeric_limits<int>::max();
268 if (mayHaveRestrictions) {
269 myRouter = new CHRouter<MSEdge, SUMOVehicle, SUMOAbstractRouterPermissions<MSEdge, SUMOVehicle> >(
270 MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort, vehicle.getVClass(), weightPeriod, true);
271 } else {
272 myRouter = new CHRouter<MSEdge, SUMOVehicle, SUMOAbstractRouter<MSEdge, SUMOVehicle> >(
273 MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort, vehicle.getVClass(), weightPeriod, false);
274 }
275 } else if (routingAlgorithm == "CHWrapper") {
276 const SUMOTime weightPeriod = myAdaptationInterval > 0 ? myAdaptationInterval : std::numeric_limits<int>::max();
277 myRouter = new CHRouterWrapper<MSEdge, SUMOVehicle, SUMOAbstractRouterPermissions<MSEdge, SUMOVehicle> >(
278 MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort,
279 string2time(oc.getString("begin")), string2time(oc.getString("end")), weightPeriod, oc.getInt("device.rerouting.threads"));
280 } else {
281 throw ProcessError("Unknown routing algorithm '" + routingAlgorithm + "'!");
282 }
283 }
284 #ifdef HAVE_FOX
285 if (needThread) {
286 const int numThreads = OptionsCont::getOptions().getInt("device.rerouting.threads");
287 if (myThreadPool.size() < numThreads) {
288 new WorkerThread(myThreadPool, myRouter);
289 }
290 if (myThreadPool.size() < numThreads) {
291 myRouter = nullptr;
292 }
293 }
294 if (myThreadPool.size() > 0) {
295 myThreadPool.add(new RoutingTask(vehicle, currentTime, onInit));
296 return;
297 }
298 #endif
299 vehicle.reroute(currentTime, "device.rerouting", *myRouter, onInit, myWithTaz);
300 }
301
302
303 void
setEdgeTravelTime(const MSEdge * const edge,const double travelTime)304 MSRoutingEngine::setEdgeTravelTime(const MSEdge* const edge, const double travelTime) {
305 myEdgeSpeeds[edge->getNumericalID()] = edge->getLength() / travelTime;
306 }
307
308
309 SUMOAbstractRouter<MSEdge, SUMOVehicle>&
getRouterTT(const MSEdgeVector & prohibited)310 MSRoutingEngine::getRouterTT(const MSEdgeVector& prohibited) {
311 if (myRouterWithProhibited == nullptr) {
312 initWeightUpdate();
313 initEdgeWeights();
314 myRouterWithProhibited = new AStarRouter<MSEdge, SUMOVehicle, SUMOAbstractRouterPermissions<MSEdge, SUMOVehicle> >(
315 MSEdge::getAllEdges(), true, &MSRoutingEngine::getEffort);
316 }
317 myRouterWithProhibited->prohibit(prohibited);
318 return *myRouterWithProhibited;
319 }
320
321
322 void
cleanup()323 MSRoutingEngine::cleanup() {
324 delete myRouterWithProhibited;
325 myRouterWithProhibited = nullptr;
326 myAdaptationInterval = -1; // responsible for triggering initEdgeWeights
327 myPastEdgeSpeeds.clear();
328 myEdgeSpeeds.clear();
329 // @todo recheck. calling release crashes in parallel routing
330 //for (auto& item : myCachedRoutes) {
331 // item.second->release();
332 //}
333 myCachedRoutes.clear();
334 myAdaptationStepsIndex = 0;
335 #ifdef HAVE_FOX
336 if (myThreadPool.size() > 0) {
337 // we cannot wait for the static destructor to do the cleanup
338 // because the output devices are gone by then
339 myThreadPool.clear();
340 // router deletion is done in thread destructor
341 myRouter = nullptr;
342 return;
343 }
344 #endif
345 delete myRouter;
346 myRouter = nullptr;
347 }
348
349
350 #ifdef HAVE_FOX
351 void
waitForAll()352 MSRoutingEngine::waitForAll() {
353 if (myThreadPool.size() > 0) {
354 myThreadPool.waitAll();
355 }
356 }
357
358
359 // ---------------------------------------------------------------------------
360 // MSRoutingEngine::RoutingTask-methods
361 // ---------------------------------------------------------------------------
362 void
run(FXWorkerThread * context)363 MSRoutingEngine::RoutingTask::run(FXWorkerThread* context) {
364 myVehicle.reroute(myTime, "device.rerouting", static_cast<WorkerThread*>(context)->getRouter(), myOnInit, myWithTaz);
365 const MSEdge* source = *myVehicle.getRoute().begin();
366 const MSEdge* dest = myVehicle.getRoute().getLastEdge();
367 if (source->isTazConnector() && dest->isTazConnector()) {
368 const std::pair<const MSEdge*, const MSEdge*> key = std::make_pair(source, dest);
369 lock();
370 if (MSRoutingEngine::myCachedRoutes.find(key) == MSRoutingEngine::myCachedRoutes.end()) {
371 MSRoutingEngine::myCachedRoutes[key] = &myVehicle.getRoute();
372 myVehicle.getRoute().addReference();
373 }
374 unlock();
375 }
376 }
377 #endif
378
379
380 /****************************************************************************/
381
382