Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2002-2024 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 RORouteDef.cpp
15 : /// @author Daniel Krajzewicz
16 : /// @author Michael Behrisch
17 : /// @author Jakob Erdmann
18 : /// @date Sept 2002
19 : ///
20 : // Base class for a vehicle's route definition
21 : /****************************************************************************/
22 : #include <config.h>
23 :
24 : #include <string>
25 : #include <iterator>
26 : #include <algorithm>
27 : #include <utils/common/StringUtils.h>
28 : #include <utils/common/ToString.h>
29 : #include <utils/common/Named.h>
30 : #include <utils/common/StringUtils.h>
31 : #include <utils/common/MsgHandler.h>
32 : #include <utils/common/RandHelper.h>
33 : #include <utils/iodevices/OutputDevice.h>
34 : #include <utils/options/OptionsCont.h>
35 : #include "ROEdge.h"
36 : #include "RORoute.h"
37 : #include <utils/router/SUMOAbstractRouter.h>
38 : #include <utils/router/RouteCostCalculator.h>
39 : #include "RORouteDef.h"
40 : #include "ROVehicle.h"
41 :
42 : // ===========================================================================
43 : // static members
44 : // ===========================================================================
45 : bool RORouteDef::myUsingJTRR(false);
46 :
47 : // ===========================================================================
48 : // method definitions
49 : // ===========================================================================
50 163621 : RORouteDef::RORouteDef(const std::string& id, const int lastUsed,
51 163621 : const bool tryRepair, const bool mayBeDisconnected) :
52 163621 : Named(StringUtils::convertUmlaute(id)),
53 163621 : myPrecomputed(nullptr), myLastUsed(lastUsed), myTryRepair(tryRepair),
54 163621 : myMayBeDisconnected(mayBeDisconnected),
55 163621 : myDiscardSilent(false) {
56 163621 : }
57 :
58 :
59 326746 : RORouteDef::~RORouteDef() {
60 483141 : for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
61 : if (myRouteRefs.count(*i) == 0) {
62 319764 : delete *i;
63 : }
64 : }
65 326746 : }
66 :
67 :
68 : void
69 305496 : RORouteDef::addLoadedAlternative(RORoute* alt) {
70 305496 : myAlternatives.push_back(alt);
71 305496 : }
72 :
73 :
74 : void
75 4 : RORouteDef::addAlternativeDef(const RORouteDef* alt) {
76 : std::copy(alt->myAlternatives.begin(), alt->myAlternatives.end(),
77 4 : back_inserter(myAlternatives));
78 : std::copy(alt->myAlternatives.begin(), alt->myAlternatives.end(),
79 4 : std::inserter(myRouteRefs, myRouteRefs.end()));
80 4 : }
81 :
82 :
83 : RORoute*
84 151618 : RORouteDef::buildCurrentRoute(SUMOAbstractRouter<ROEdge, ROVehicle>& router,
85 : SUMOTime begin, const ROVehicle& veh) const {
86 151618 : if (myPrecomputed == nullptr) {
87 151618 : preComputeCurrentRoute(router, begin, veh);
88 : }
89 151618 : return myPrecomputed;
90 : }
91 :
92 :
93 : void
94 151618 : RORouteDef::preComputeCurrentRoute(SUMOAbstractRouter<ROEdge, ROVehicle>& router,
95 : SUMOTime begin, const ROVehicle& veh) const {
96 151618 : myNewRoute = false;
97 151618 : const OptionsCont& oc = OptionsCont::getOptions();
98 151618 : const bool ignoreErrors = oc.getBool("ignore-errors");
99 : assert(myAlternatives[0]->getEdgeVector().size() > 0);
100 151618 : MsgHandler* mh = ignoreErrors ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance();
101 303272 : if (myAlternatives[0]->getFirst()->prohibits(&veh) && (!oc.getBool("repair.from")
102 : // do not try to reassign starting edge for trip input
103 9 : || myMayBeDisconnected || myAlternatives[0]->getEdgeVector().size() < 2)) {
104 24 : mh->inform("Vehicle '" + veh.getID() + "' is not allowed to depart on edge '" +
105 12 : myAlternatives[0]->getFirst()->getID() + "'.");
106 12 : return;
107 303242 : } else if (myAlternatives[0]->getLast()->prohibits(&veh) && (!oc.getBool("repair.to")
108 : // do not try to reassign destination edge for trip input
109 9 : || myMayBeDisconnected || myAlternatives[0]->getEdgeVector().size() < 2)) {
110 : // this check is not strictly necessary unless myTryRepair is set.
111 : // However, the error message is more helpful than "no connection found"
112 18 : mh->inform("Vehicle '" + veh.getID() + "' is not allowed to arrive on edge '" +
113 9 : myAlternatives[0]->getLast()->getID() + "'.");
114 9 : return;
115 : }
116 460687 : const bool skipTripRouting = (oc.exists("write-trips") && oc.getBool("write-trips")
117 162934 : && RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().skipRouteCalculation());
118 151597 : if ((myTryRepair && !skipTripRouting) || myUsingJTRR) {
119 : ConstROEdgeVector newEdges;
120 54707 : if (repairCurrentRoute(router, begin, veh, myAlternatives[0]->getEdgeVector(), newEdges)) {
121 54065 : if (myAlternatives[0]->getEdgeVector() != newEdges) {
122 51218 : if (!myMayBeDisconnected) {
123 102 : WRITE_WARNINGF(TL("Repaired route of vehicle '%'."), veh.getID());
124 : }
125 51218 : myNewRoute = true;
126 51218 : RGBColor* col = myAlternatives[0]->getColor() != nullptr ? new RGBColor(*myAlternatives[0]->getColor()) : nullptr;
127 51218 : myPrecomputed = new RORoute(myID, 0, myAlternatives[0]->getProbability(), newEdges, col, myAlternatives[0]->getStops());
128 : } else {
129 2847 : myPrecomputed = myAlternatives[0];
130 : }
131 : }
132 : return;
133 54707 : }
134 96890 : if ((RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().skipRouteCalculation()
135 192932 : || OptionsCont::getOptions().getBool("remove-loops"))
136 96946 : && (skipTripRouting || myAlternatives[myLastUsed]->isValid(veh, ignoreErrors))) {
137 956 : myPrecomputed = myAlternatives[myLastUsed];
138 : } else {
139 : // build a new route to test whether it is better
140 : ConstROEdgeVector oldEdges;
141 95934 : oldEdges.push_back(myAlternatives[0]->getFirst());
142 95934 : oldEdges.push_back(myAlternatives[0]->getLast());
143 : ConstROEdgeVector edges;
144 95934 : repairCurrentRoute(router, begin, veh, oldEdges, edges);
145 : // check whether the same route was already used
146 : int cheapest = -1;
147 136709 : for (int i = 0; i < (int)myAlternatives.size(); i++) {
148 122137 : if (edges == myAlternatives[i]->getEdgeVector()) {
149 : cheapest = i;
150 : break;
151 : }
152 : }
153 95934 : if (cheapest >= 0) {
154 81362 : myPrecomputed = myAlternatives[cheapest];
155 : } else {
156 14572 : RGBColor* col = myAlternatives[0]->getColor() != nullptr ? new RGBColor(*myAlternatives[0]->getColor()) : nullptr;
157 14572 : myPrecomputed = new RORoute(myID, 0, 1, edges, col, myAlternatives[0]->getStops());
158 14572 : myNewRoute = true;
159 : }
160 95934 : }
161 : }
162 :
163 :
164 : bool
165 150641 : RORouteDef::repairCurrentRoute(SUMOAbstractRouter<ROEdge, ROVehicle>& router,
166 : SUMOTime begin, const ROVehicle& veh,
167 : ConstROEdgeVector oldEdges, ConstROEdgeVector& newEdges) const {
168 301282 : MsgHandler* mh = (OptionsCont::getOptions().getBool("ignore-errors") ?
169 150641 : MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance());
170 150641 : const int initialSize = (int)oldEdges.size();
171 150641 : if (initialSize == 1) {
172 5439 : if (myUsingJTRR) {
173 : /// only ROJTRRouter is supposed to handle this type of input
174 5384 : bool ok = router.compute(oldEdges.front(), nullptr, &veh, begin, newEdges);
175 9468 : myDiscardSilent = ok && newEdges.size() == 0;
176 : } else {
177 55 : newEdges = oldEdges;
178 : }
179 : } else {
180 290404 : if (oldEdges.front()->prohibits(&veh)) {
181 : // option repair.from is in effect
182 : const std::string& frontID = oldEdges.front()->getID();
183 18 : for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
184 30 : if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
185 : i = oldEdges.erase(i);
186 : } else {
187 6 : WRITE_MESSAGE("Changing invalid starting edge '" + frontID
188 : + "' to '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
189 3 : break;
190 : }
191 : }
192 : }
193 145202 : if (oldEdges.size() == 0) {
194 6 : mh->inform("Could not find new starting edge for vehicle '" + veh.getID() + "'.");
195 642 : return false;
196 : }
197 290398 : if (oldEdges.back()->prohibits(&veh)) {
198 : // option repair.to is in effect
199 : const std::string& backID = oldEdges.back()->getID();
200 : // oldEdges cannot get empty here, otherwise we would have left the stage when checking "from"
201 6 : while (oldEdges.back()->prohibits(&veh) || oldEdges.back()->isInternal()) {
202 : oldEdges.pop_back();
203 : }
204 9 : WRITE_MESSAGE("Changing invalid destination edge '" + backID
205 : + "' to edge '" + oldEdges.back()->getID() + "' for vehicle '" + veh.getID() + "'.");
206 : }
207 145199 : ConstROEdgeVector mandatory = veh.getMandatoryEdges(oldEdges.front(), oldEdges.back());
208 : std::set<ConstROEdgeVector::const_iterator> jumpStarts;
209 145199 : veh.collectJumps(mandatory, jumpStarts);
210 : assert(mandatory.size() >= 2);
211 : // removed prohibited
212 453732 : for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
213 617066 : if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
214 : // no need to check the mandatories here, this was done before
215 : i = oldEdges.erase(i);
216 : } else {
217 : ++i;
218 : }
219 : }
220 : // reconnect remaining edges
221 145199 : if (mandatory.size() > oldEdges.size() && initialSize > 2) {
222 0 : WRITE_MESSAGEF(TL("There are stop edges which were not part of the original route for vehicle '%'."), veh.getID());
223 : }
224 145199 : const ConstROEdgeVector& targets = mandatory.size() > oldEdges.size() ? mandatory : oldEdges;
225 145199 : newEdges.push_back(targets.front());
226 : ConstROEdgeVector::iterator nextMandatory = mandatory.begin() + 1;
227 : int lastMandatory = 0;
228 145199 : for (ConstROEdgeVector::const_iterator i = targets.begin() + 1;
229 308358 : i != targets.end() && nextMandatory != mandatory.end(); ++i) {
230 163798 : const ROEdge* prev = *(i - 1);
231 163798 : const ROEdge* cur = *i;
232 176527 : if (prev->isConnectedTo(*cur, veh.getVClass()) && (!isRailway(veh.getVClass()) || prev->getBidiEdge() != cur)) {
233 12725 : newEdges.push_back(cur);
234 : } else {
235 151073 : if (initialSize > 2) {
236 : // only inform if the input is (probably) not a trip
237 88035 : WRITE_MESSAGEF(TL("Edge '%' not connected to edge '%' for vehicle '%'."), (*(i - 1))->getID(), (*i)->getID(), veh.getID());
238 : }
239 151073 : const ROEdge* last = newEdges.back();
240 : newEdges.pop_back();
241 151073 : if (last->isTazConnector() && newEdges.size() > 1) {
242 : // assume this was a viaTaz
243 28 : last = newEdges.back();
244 : newEdges.pop_back();
245 : }
246 151073 : if (veh.hasJumps() && jumpStarts.count(nextMandatory - 1) != 0) {
247 24 : while (*i != *nextMandatory) {
248 : ++i;
249 : }
250 24 : newEdges.push_back(last);
251 24 : newEdges.push_back(*i);
252 : //std::cout << " skipJump mIndex=" << (nextMandatory - 1 - mandatory.begin()) << " last=" << last->getID() << " next=" << (*i)->getID() << " newEdges=" << toString(newEdges) << "\n";
253 : } else {
254 :
255 : // router.setHint(targets.begin(), i, &veh, begin);
256 151049 : if (!router.compute(last, *i, &veh, begin, newEdges)) {
257 : // backtrack: try to route from last mandatory edge to next mandatory edge
258 : // XXX add option for backtracking in smaller increments
259 : // (i.e. previous edge to edge after *i)
260 : // we would then need to decide whether we have found a good
261 : // tradeoff between faithfulness to the input data and detour-length
262 : ConstROEdgeVector edges;
263 642 : if (lastMandatory >= (int)newEdges.size() || last == newEdges[lastMandatory] || !router.compute(newEdges[lastMandatory], *nextMandatory, &veh, begin, edges)) {
264 1278 : mh->inform("Mandatory edge '" + (*i)->getID() + "' not reachable by vehicle '" + veh.getID() + "'.");
265 : return false;
266 : }
267 6 : while (*i != *nextMandatory) {
268 : ++i;
269 : }
270 : newEdges.erase(newEdges.begin() + lastMandatory + 1, newEdges.end());
271 : std::copy(edges.begin() + 1, edges.end(), back_inserter(newEdges));
272 642 : }
273 :
274 : }
275 : }
276 163159 : if (*i == *nextMandatory) {
277 : nextMandatory++;
278 160365 : lastMandatory = (int)newEdges.size() - 1;
279 : }
280 : }
281 145199 : }
282 : return true;
283 : }
284 :
285 :
286 : void
287 149655 : RORouteDef::addAlternative(SUMOAbstractRouter<ROEdge, ROVehicle>& router,
288 : const ROVehicle* const veh, RORoute* current, SUMOTime begin) {
289 149655 : if (myTryRepair || myUsingJTRR) {
290 52773 : if (myNewRoute) {
291 49918 : delete myAlternatives[0];
292 49918 : myAlternatives[0] = current;
293 : }
294 105546 : if (!router.isValid(current->getEdgeVector(), veh)) {
295 0 : throw ProcessError("Route '" + getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
296 : }
297 52773 : double costs = router.recomputeCosts(current->getEdgeVector(), veh, begin);
298 52773 : if (veh->hasJumps()) {
299 : // @todo: jumpTime should be applied in recomputeCost to ensure the
300 : // correctness of time-dependent traveltimes
301 20 : costs += STEPS2TIME(veh->getJumpTime());
302 : }
303 52773 : current->setCosts(costs);
304 52773 : return;
305 : }
306 : // add the route when it's new
307 96882 : if (myNewRoute) {
308 14572 : myAlternatives.push_back(current);
309 : }
310 : // recompute the costs and (when a new route was added) scale the probabilities
311 96882 : const double scale = double(myAlternatives.size() - 1) / double(myAlternatives.size());
312 350534 : for (RORoute* const alt : myAlternatives) {
313 253668 : if (!router.isValid(alt->getEdgeVector(), veh)) {
314 32 : throw ProcessError("Route '" + current->getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
315 : }
316 : // recompute the costs for all routes
317 253652 : const double newCosts = router.recomputeCosts(alt->getEdgeVector(), veh, begin);
318 : assert(myAlternatives.size() != 0);
319 253652 : if (myNewRoute) {
320 34800 : if (alt == current) {
321 : // set initial probability and costs
322 14556 : alt->setProbability(1. / (double) myAlternatives.size());
323 14556 : alt->setCosts(newCosts);
324 : } else {
325 : // rescale probs for all others
326 20244 : alt->setProbability(alt->getProbability() * scale);
327 : }
328 : }
329 253652 : RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().setCosts(alt, newCosts, alt == myAlternatives[myLastUsed]);
330 : }
331 : assert(myAlternatives.size() != 0);
332 96866 : RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().calculateProbabilities(myAlternatives, veh, veh->getDepartureTime());
333 96866 : const bool keepRoute = RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().keepRoute();
334 96866 : if (!RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().keepAllRoutes() && !keepRoute) {
335 : // remove with probability of 0 (not mentioned in Gawron)
336 335555 : for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end();) {
337 242873 : if ((*i)->getProbability() == 0) {
338 0 : delete *i;
339 : i = myAlternatives.erase(i);
340 : } else {
341 : i++;
342 : }
343 : }
344 : }
345 96866 : int maxNumber = RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber();
346 96866 : if ((int)myAlternatives.size() > maxNumber) {
347 56 : const RORoute* last = myAlternatives[myLastUsed];
348 : // only keep the routes with highest probability
349 56 : sort(myAlternatives.begin(), myAlternatives.end(), [](const RORoute * const a, const RORoute * const b) {
350 : return a->getProbability() > b->getProbability();
351 : });
352 56 : if (keepRoute) {
353 18 : for (int i = 0; i < (int)myAlternatives.size(); i++) {
354 18 : if (myAlternatives[i] == last) {
355 12 : myLastUsed = i;
356 12 : break;
357 : }
358 : }
359 12 : if (myLastUsed >= maxNumber) {
360 6 : std::swap(myAlternatives[maxNumber - 1], myAlternatives[myLastUsed]);
361 6 : myLastUsed = maxNumber - 1;
362 : }
363 : }
364 112 : for (std::vector<RORoute*>::iterator i = myAlternatives.begin() + maxNumber; i != myAlternatives.end(); i++) {
365 56 : delete *i;
366 : }
367 : myAlternatives.erase(myAlternatives.begin() + maxNumber, myAlternatives.end());
368 : }
369 : // rescale probabilities
370 : double newSum = 0.;
371 350462 : for (const RORoute* const alt : myAlternatives) {
372 253596 : newSum += alt->getProbability();
373 : }
374 : assert(newSum > 0);
375 : // @note newSum may be larger than 1 for numerical reasons
376 350462 : for (RORoute* const alt : myAlternatives) {
377 253596 : alt->setProbability(alt->getProbability() / newSum);
378 : }
379 :
380 : // find the route to use
381 96866 : if (!keepRoute) {
382 92682 : double chosen = RandHelper::rand();
383 92682 : myLastUsed = 0;
384 158342 : for (const RORoute* const alt : myAlternatives) {
385 158342 : chosen -= alt->getProbability();
386 158342 : if (chosen <= 0) {
387 : return;
388 : }
389 65660 : myLastUsed++;
390 : }
391 : }
392 : }
393 :
394 :
395 : const ROEdge*
396 0 : RORouteDef::getDestination() const {
397 0 : return myAlternatives[0]->getLast();
398 : }
399 :
400 :
401 : OutputDevice&
402 254445 : RORouteDef::writeXMLDefinition(OutputDevice& dev, const ROVehicle* const veh,
403 : bool asAlternatives, bool withExitTimes, bool withCost, bool withLength) const {
404 254445 : if (asAlternatives) {
405 115978 : dev.openTag(SUMO_TAG_ROUTE_DISTRIBUTION).writeAttr(SUMO_ATTR_LAST, myLastUsed);
406 388689 : for (int i = 0; i != (int)myAlternatives.size(); i++) {
407 545422 : myAlternatives[i]->writeXMLDefinition(dev, veh, true, true, withExitTimes, withLength);
408 : }
409 115978 : dev.closeTag();
410 115978 : return dev;
411 : } else {
412 276934 : return myAlternatives[myLastUsed]->writeXMLDefinition(dev, veh, withCost, false, withExitTimes, withLength);
413 : }
414 : }
415 :
416 :
417 : RORouteDef*
418 24608 : RORouteDef::copy(const std::string& id, const SUMOTime stopOffset) const {
419 24608 : RORouteDef* result = new RORouteDef(id, 0, myTryRepair, myMayBeDisconnected);
420 50096 : for (const RORoute* const route : myAlternatives) {
421 25488 : RGBColor* col = route->getColor() != nullptr ? new RGBColor(*route->getColor()) : nullptr;
422 25488 : RORoute* newRoute = new RORoute(id, route->getCosts(), route->getProbability(), route->getEdgeVector(), col, route->getStops());
423 : newRoute->addStopOffset(stopOffset);
424 25488 : result->addLoadedAlternative(newRoute);
425 : }
426 24608 : return result;
427 : }
428 :
429 :
430 : double
431 90849 : RORouteDef::getOverallProb() const {
432 : double sum = 0.;
433 323063 : for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
434 232214 : sum += (*i)->getProbability();
435 : }
436 90849 : return sum;
437 : }
438 :
439 :
440 : /****************************************************************************/
|
