Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-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 RailwayRouter.h
15 : /// @author Jakob Erdmann
16 : /// @date Tue, 25 Feb 2020
17 : ///
18 : // The RailwayRouter builds a special network for railway routing to handle train reversal restrictions (delegates to a SUMOAbstractRouter)
19 : /****************************************************************************/
20 : #pragma once
21 : #include <config.h>
22 :
23 : #include <string>
24 : #include <vector>
25 : #include <algorithm>
26 : #include <assert.h>
27 : #ifdef HAVE_FOX
28 : #include <utils/foxtools/fxheader.h>
29 : #endif
30 : #include <utils/common/MsgHandler.h>
31 : #include <utils/common/SUMOTime.h>
32 : #include <utils/common/ToString.h>
33 : #include <utils/iodevices/OutputDevice.h>
34 : #include "SUMOAbstractRouter.h"
35 : #include "DijkstraRouter.h"
36 : #include "RailEdge.h"
37 :
38 :
39 : //#define RailwayRouter_DEBUG_ROUTES
40 :
41 : // ===========================================================================
42 : // class definitions
43 : // ===========================================================================
44 : /**
45 : * @class RailwayRouter
46 : * The router for rail vehicles for track networks where some sections may be used in both directions
47 : * and trains may reverse depending on location and train length
48 : *
49 : * Example (assume each track section is 100m long) running from left to right and a negative sign indicates reverse direction
50 : *
51 : * A C D
52 : * .______.______.______.
53 : * ._____/
54 : * B
55 : *
56 : * Consider a train of 200m length that enters on B and must move to A (with a reversal):
57 : * The necessary route is B C D -D -C -A were D,-D are needed for the train to fully pass the switch
58 : *
59 : * We shadow the normal edge graph with a railEdge graph to include virtual
60 : * turnarounds that look at the train length.
61 : * The graph extension takes place via RailEdge::init()
62 : * For edge C we create a virtual turnaround (as successor of C) that connectes C with -C and is then expanded to C D -D -C for trains longer than 100m.
63 : * The expension takes place via RailEdge::insertOriginalEdges()
64 : *
65 : */
66 : template<class E, class V>
67 : class RailwayRouter : public SUMOAbstractRouter<E, V> {
68 :
69 : private:
70 :
71 :
72 : typedef RailEdge<E, V> _RailEdge;
73 : typedef SUMOAbstractRouter<_RailEdge, V> _InternalRouter;
74 : typedef DijkstraRouter<_RailEdge, V> _InternalDijkstra;
75 : typedef std::map<const E*, RouterProhibition> Prohibitions;
76 :
77 : public:
78 :
79 : /// Constructor
80 617 : RailwayRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename SUMOAbstractRouter<E, V>::Operation effortOperation,
81 : typename SUMOAbstractRouter<E, V>::Operation ttOperation = nullptr, bool silent = false,
82 : bool havePermissions = false, const bool haveRestrictions = false, double maxTrainLength = 5000,
83 : double reversalPenalty = 60) :
84 : SUMOAbstractRouter<E, V>("RailwayRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
85 617 : myInternalRouter(nullptr), myOriginal(nullptr), mySilent(silent),
86 617 : myMaxTrainLength(maxTrainLength),
87 1234 : myLastFrom(nullptr) {
88 617 : myReversalPenalty = reversalPenalty;
89 617 : myStaticOperation = effortOperation;
90 242033 : for (const E* const edge : edges) {
91 241416 : myInitialEdges.push_back(edge->getRailwayRoutingEdge());
92 : }
93 617 : }
94 :
95 : /// Destructor
96 1992 : virtual ~RailwayRouter() {
97 669 : delete myInternalRouter;
98 2661 : }
99 :
100 379 : SUMOAbstractRouter<E, V>* clone() {
101 379 : return new RailwayRouter<E, V>(this);
102 : }
103 :
104 : /** @brief Builds the route between the given edges using the minimum effort at the given time
105 : The definition of the effort depends on the wished routing scheme */
106 28918 : bool compute(const E* from, const E* to, const V* const vehicle, SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
107 28918 : ensureInternalRouter();
108 28918 : if (vehicle->getLength() > myMaxTrainLength) {
109 15 : WRITE_WARNINGF("Vehicle '%' with length % exceeds configured value of --railway.max-train-length %",
110 : vehicle->getID(), toString(vehicle->getLength()), toString(myMaxTrainLength));
111 : }
112 28918 : return _compute(from, to, vehicle, msTime, into, silent, false);
113 : }
114 :
115 98 : void prohibit(const Prohibitions& toProhibit) {
116 98 : ensureInternalRouter();
117 : typename _InternalRouter::Prohibitions _toProhibit;
118 113 : for (auto item : toProhibit) {
119 15 : _toProhibit[item.first->getRailwayRoutingEdge()] = item.second;
120 : }
121 98 : myInternalRouter->prohibit(_toProhibit);
122 : this->myProhibited = toProhibit;
123 : #ifdef RailwayRouter_DEBUG_ROUTES
124 : std::cout << "RailRouter numProhibitions=" << toProhibit.size() << "\n";
125 : #endif
126 98 : }
127 :
128 :
129 78573 : double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
130 78573 : double effort = SUMOAbstractRouter<E, V>::recomputeCosts(edges, v, msTime, lengthp);
131 : const E* prev = nullptr;
132 : // reversal corrections
133 78573 : double timeCorrection = STEPS2TIME(msTime);
134 1578961 : for (const E* const e : edges) {
135 1500388 : if (prev != nullptr && e->getBidiEdge() == prev) {
136 30465 : if (e->getLength() > v->getLength()) {
137 : // vehicle doesn't need to drive to the end of the edge
138 : // @note exact timing correction for time-dependent effort is not done
139 30344 : const double savingsFactor = 1 - v->getLength() / e->getLength();
140 : double effortCorrection = 0;
141 30344 : double lengthCorrection = 0.;
142 30344 : effortCorrection += this->getEffort(prev, v, timeCorrection);
143 30344 : this->updateViaCost(prev, e, v, timeCorrection, effortCorrection, lengthCorrection);
144 30344 : effort -= savingsFactor * effortCorrection;
145 30344 : if (lengthp != nullptr) {
146 0 : *lengthp -= savingsFactor * lengthCorrection;
147 : }
148 : }
149 30465 : effort += myReversalPenalty;
150 : }
151 : prev = e;
152 : }
153 78573 : return effort;
154 : }
155 :
156 62 : inline void setBulkMode(const bool mode) {
157 62 : if (myInternalRouter != nullptr) {
158 62 : myInternalRouter->setBulkMode(mode);
159 : }
160 62 : }
161 :
162 : private:
163 379 : RailwayRouter(RailwayRouter* other) :
164 : SUMOAbstractRouter<E, V>(other),
165 379 : myInternalRouter(nullptr),
166 379 : myOriginal(other),
167 379 : mySilent(other->mySilent),
168 379 : myMaxTrainLength(other->myMaxTrainLength)
169 379 : {}
170 :
171 29016 : void ensureInternalRouter() {
172 29016 : if (myInternalRouter == nullptr) {
173 1338 : myInternalRouter = new _InternalDijkstra(getRailEdges(), this->myErrorMsgHandler == MsgHandler::getWarningInstance(), &getTravelTimeStatic,
174 669 : nullptr, mySilent, nullptr, this->myHavePermissions, this->myHaveRestrictions);
175 : }
176 29016 : }
177 :
178 28949 : bool _compute(const E* from, const E* to, const V* const vehicle, SUMOTime msTime, std::vector<const E*>& into, bool silent, bool avoidUnsafeBackTracking) {
179 : // make sure that the vehicle can turn-around when starting on a short edge (the virtual turn-around for this lies backwards along the route / track)
180 : // if reversals are forbidden (negative penalty), we don't need to check this
181 102 : std::vector<double> backLengths;
182 28949 : double backDist = myReversalPenalty >= 0 ? vehicle->getLength() - from->getLength() : 0;
183 : const E* start = from;
184 29404 : while (backDist > 0) {
185 839 : const E* prev = getStraightPredecessor(start, into, (int)backLengths.size());
186 839 : if (prev == nullptr) {
187 : #ifdef RailwayRouter_DEBUG_ROUTES
188 : std::cout << " Could not determine back edge for vehicle '" << vehicle->getID() << "' when routing from edge '" << from->getID() << "' at time=" << time2string(msTime) << "\n";
189 : #endif
190 : //WRITE_WARNING("Could not determine back edge for vehicle '" + vehicle->getID() + "' when routing from edge '" + from->getID() + "' at time=" + time2string(msTime));
191 : break;
192 : }
193 486 : backDist -= prev->getLength();
194 486 : if (avoidUnsafeBackTracking && prev->getSuccessors().size() > 1) {
195 : bool foundSwitch = false;
196 54 : for (const E* succ : prev->getSuccessors()) {
197 54 : if (succ != start && succ != prev->getBidiEdge()) {
198 : foundSwitch = true;
199 : break;
200 : }
201 : }
202 31 : if (foundSwitch) {
203 : break;
204 : }
205 : }
206 455 : backLengths.push_back(prev->getLength() + (backLengths.empty()
207 455 : ? MIN2(vehicle->getLength(), from->getLength())
208 : : backLengths.back()));
209 : start = prev;
210 : }
211 :
212 102 : std::vector<const _RailEdge*> intoTmp;
213 28949 : if (myLastFrom != start) {
214 27609 : myInternalRouter->setBulkMode(false);
215 : }
216 28949 : bool success = myInternalRouter->compute(start->getRailwayRoutingEdge(), to->getRailwayRoutingEdge(), vehicle, msTime, intoTmp, silent);
217 28949 : myLastFrom = start;
218 : #ifdef RailwayRouter_DEBUG_ROUTES
219 : std::cout << "RailRouter veh=" << vehicle->getID() << " from=" << from->getID() << " to=" << to->getID() << " t=" << time2string(msTime)
220 : << " safe=" << avoidUnsafeBackTracking << " success=" << success << " into=" << toString(into) << "\n";
221 : #endif
222 28949 : if (success) {
223 : const size_t intoSize = into.size();
224 28897 : int backIndex = (int)backLengths.size();
225 425129 : for (const _RailEdge* railEdge : intoTmp) {
226 396232 : if (railEdge->getOriginal() != nullptr) {
227 388515 : backIndex--;
228 : }
229 : // prevent premature reversal on back edge (extend train length)
230 396232 : const double length = backIndex >= 0 ? backLengths[backIndex] : vehicle->getLength();
231 396232 : railEdge->insertOriginalEdges(length, into);
232 : }
233 : #ifdef RailwayRouter_DEBUG_ROUTES
234 : std::cout << "RailRouter: internal result=" << toString(intoTmp) << "\n";
235 : std::cout << "RailRouter: expanded result=" << toString(into) << "\n";
236 : std::cout << "RailRouter: backLengths=" << toString(backLengths) << " bls=" << backLengths.size() << " intoSize=" << intoSize << " final result=" << toString(into) << "\n";
237 : #endif
238 28897 : if (backLengths.size() > 0) {
239 : // skip the virtual back-edges
240 : into.erase(into.begin() + intoSize, into.begin() + intoSize + backLengths.size());
241 349 : if (*(into.begin() + intoSize) != from) {
242 31 : if (!avoidUnsafeBackTracking) {
243 : // try again, this time with more safety (but unable to
244 : // make use of turn-arounds on short edge)
245 : into.erase(into.begin() + intoSize, into.end());
246 : // we are starting from a different edge and are thus violating the assumptions of bulk mode
247 31 : success = _compute(from, to, vehicle, msTime, into, silent, true);
248 : return success;
249 : } else {
250 0 : WRITE_WARNING("Railway routing failure due to turn-around on short edge '" + from->getID()
251 : + "' for vehicle '" + vehicle->getID() + "' time=" + time2string(msTime) + ".");
252 : }
253 : }
254 : }
255 28866 : if (this->myProhibited.size() > 0) {
256 : // make sure that turnarounds don't use prohibited edges
257 138 : for (const E* e : into) {
258 126 : if (this->myProhibited.find(e) != this->myProhibited.end()) {
259 : into.clear();
260 : success = false;
261 : break;
262 : }
263 : }
264 : }
265 : }
266 : return success;
267 :
268 28949 : }
269 :
270 779 : const std::vector<_RailEdge*>& getRailEdges() {
271 779 : if (myOriginal != nullptr) {
272 110 : return myOriginal->getRailEdges();
273 : }
274 : #ifdef HAVE_FOX
275 669 : FXMutexLock locker(myLock);
276 : #endif
277 669 : if (myRailEdges.empty()) {
278 560 : myRailEdges = myInitialEdges;
279 560 : int numericalID = myInitialEdges.back()->getNumericalID() + 1;
280 38313 : for (_RailEdge* railEdge : myInitialEdges) {
281 37753 : railEdge->init(myRailEdges, numericalID, myMaxTrainLength, myReversalPenalty >= 0);
282 : }
283 : }
284 669 : return myRailEdges;
285 : }
286 :
287 1265176 : static inline double getTravelTimeStatic(const RailEdge<E, V>* const edge, const V* const veh, double time) {
288 1265176 : if (edge->getOriginal() != nullptr) {
289 1188605 : return (*myStaticOperation)(edge->getOriginal(), veh, time);
290 : } else {
291 : // turnaround edge
292 76571 : if (edge->isVirtual()) {
293 : // add up time for replacement edges
294 60 : std::vector<const E*> repl;
295 56521 : edge->insertOriginalEdges(veh->getLength(), repl);
296 : assert(repl.size() > 0);
297 : double seenDist = 0;
298 : double result = 0;
299 : repl.pop_back(); // last edge must not be used fully
300 216468 : for (const E* e : repl) {
301 159947 : result += (*myStaticOperation)(e, veh, time + result);
302 159947 : seenDist += e->getLength();
303 : }
304 56521 : const double lengthOnLastEdge = MAX2(0.0, veh->getLength() - seenDist);
305 56521 : return result + myReversalPenalty + lengthOnLastEdge * myReversalPenaltyFactor;
306 56461 : } else {
307 : // if the edge from which this turnaround starts is longer
308 : // than the vehicle then we are overstimating the cost
309 : // (because the turnaround may happen before driving to the end)
310 : // However, unless the vehicle starts on this edge, we should be taking a
311 : // virtual turnaround at the end of the previous edge. Otherwise, the exaggerated cost doesn't
312 20050 : return myReversalPenalty;
313 : }
314 : }
315 : }
316 :
317 :
318 839 : static const E* getStraightPredecessor(const E* edge, std::vector<const E*>& prevRoute, int backIndex) {
319 : const E* result = nullptr;
320 : #ifdef RailwayRouter_DEBUG_ROUTES
321 : std::cout << " getStraightPredecessor edge=" << edge->getID() << " prevRouteSize=" << prevRoute.size() << " backIndex=" << backIndex << "\n";
322 : #endif
323 839 : if ((int)prevRoute.size() > backIndex) {
324 20 : return prevRoute[(int)prevRoute.size() - 1 - backIndex];
325 : }
326 1983 : for (const E* cand : edge->getPredecessors()) {
327 1249 : if (!cand->isInternal() && cand->getBidiEdge() != edge) {
328 : //std::cout << " cand=" << cand->getID() << "\n";
329 636 : if (result == nullptr) {
330 : result = cand;
331 : } else {
332 : // predecessor not unique. Better abort with a warning
333 : return nullptr;
334 : }
335 : }
336 : }
337 : return result;
338 : }
339 :
340 : private:
341 : _InternalRouter* myInternalRouter;
342 : RailwayRouter<E, V>* const myOriginal;
343 : /// @brief a RailEdge for every existing edge, filled on construction (but not in clones)
344 : std::vector<_RailEdge*> myInitialEdges;
345 : /// @brief complete rail network filled on demand (but not in clones)
346 : std::vector<_RailEdge*> myRailEdges;
347 :
348 : /// @brief whether to suppress warning/error if no route was found
349 : const bool mySilent;
350 :
351 : const double myMaxTrainLength;
352 :
353 : /// @brief track previous edge for correct bulk routing
354 : const E* myLastFrom;
355 :
356 : #ifdef HAVE_FOX
357 : /// The mutex used to avoid concurrent updates of myRailEdges
358 : mutable FXMutex myLock;
359 : #endif
360 :
361 : /// @brief The object's operation to perform. (hack)
362 : static typename SUMOAbstractRouter<E, V>::Operation myStaticOperation;
363 :
364 : static double myReversalPenalty;
365 : static double myReversalPenaltyFactor;
366 :
367 : private:
368 : /// @brief Invalidated assignment operator
369 : RailwayRouter& operator=(const RailwayRouter& s);
370 :
371 : };
372 :
373 : template<class E, class V>
374 : typename SUMOAbstractRouter<E, V>::Operation RailwayRouter<E, V>::myStaticOperation(nullptr);
375 : template<class E, class V>
376 : double RailwayRouter<E, V>::myReversalPenalty(60);
377 : template<class E, class V>
378 : double RailwayRouter<E, V>::myReversalPenaltyFactor(0.2); // 1/v
|
