Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-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 IntermodalRouter.h
15 : /// @author Jakob Erdmann
16 : /// @author Michael Behrisch
17 : /// @date Mon, 03 March 2014
18 : ///
19 : // The IntermodalRouter builds a special network and (delegates to a SUMOAbstractRouter)
20 : /****************************************************************************/
21 : #pragma once
22 : #include <config.h>
23 :
24 : #include <string>
25 : #include <vector>
26 : #include <algorithm>
27 : #include <assert.h>
28 : #include <utils/common/MsgHandler.h>
29 : #include <utils/common/SUMOTime.h>
30 : #include <utils/common/ToString.h>
31 : #include <utils/iodevices/OutputDevice.h>
32 : #include "SUMOAbstractRouter.h"
33 : #include "DijkstraRouter.h"
34 : #include "AStarRouter.h"
35 : #include "IntermodalNetwork.h"
36 : #include "EffortCalculator.h"
37 : #include "CarEdge.h"
38 : #include "StopEdge.h"
39 : #include "PedestrianRouter.h"
40 :
41 : //#define IntermodalRouter_DEBUG_ROUTES
42 :
43 :
44 : // ===========================================================================
45 : // class definitions
46 : // ===========================================================================
47 : /**
48 : * @class IntermodalRouter
49 : * The router for pedestrians (on a bidirectional network of sidewalks and crossings)
50 : */
51 : template<class E, class L, class N, class V>
52 : class IntermodalRouter : public SUMOAbstractRouter<E, IntermodalTrip<E, N, V> > {
53 : public:
54 : typedef IntermodalNetwork<E, L, N, V> Network;
55 :
56 : private:
57 : typedef void(*CreateNetCallback)(IntermodalRouter <E, L, N, V>&);
58 : typedef IntermodalEdge<E, L, N, V> _IntermodalEdge;
59 : typedef IntermodalTrip<E, N, V> _IntermodalTrip;
60 : typedef SUMOAbstractRouter<_IntermodalEdge, _IntermodalTrip> _InternalRouter;
61 : typedef MapMatcher<E, L, N> _MapMatcher;
62 : typedef DijkstraRouter<_IntermodalEdge, _IntermodalTrip> _InternalDijkstra;
63 : typedef AStarRouter<_IntermodalEdge, _IntermodalTrip, _MapMatcher> _InternalAStar;
64 :
65 : public:
66 : struct TripItem {
67 239768 : TripItem(const std::string& _line = "") :
68 479536 : line(_line), intended(_line) {}
69 : std::string line;
70 : std::string vType = "";
71 : std::string destStop = "";
72 : std::string intended; // intended public transport vehicle id
73 : double depart = -1.; // intended public transport departure
74 : std::vector<const E*> edges;
75 : double traveltime = 0.;
76 : double cost = 0.;
77 : double length = 0.;
78 : double departPos = INVALID_DOUBLE;
79 : double arrivalPos = INVALID_DOUBLE;
80 : std::string description = "";
81 : std::vector<double> exitTimes;
82 : };
83 :
84 : /// Constructor
85 13656 : IntermodalRouter(CreateNetCallback callback, const int carWalkTransfer, double taxiWait, const std::string& routingAlgorithm,
86 : const int routingMode = 0, EffortCalculator* calc = nullptr) :
87 : SUMOAbstractRouter<E, _IntermodalTrip>("IntermodalRouter", true, nullptr, nullptr, false, false),
88 13656 : myAmClone(false), myInternalRouter(nullptr), myIntermodalNet(nullptr),
89 13656 : myCallback(callback), myCarWalkTransfer(carWalkTransfer), myTaxiWait(taxiWait),
90 13656 : myRoutingAlgorithm(routingAlgorithm),
91 27312 : myRoutingMode(routingMode), myExternalEffort(calc) {
92 13656 : }
93 :
94 : /// Destructor
95 32516 : virtual ~IntermodalRouter() {
96 7739 : delete myInternalRouter;
97 16258 : if (!myAmClone) {
98 13654 : delete myIntermodalNet;
99 : }
100 48774 : }
101 :
102 2604 : SUMOAbstractRouter<E, _IntermodalTrip>* clone() {
103 2604 : createNet();
104 2604 : return new IntermodalRouter<E, L, N, V>(myIntermodalNet, myCarWalkTransfer, myTaxiWait, myRoutingAlgorithm, myRoutingMode, myExternalEffort);
105 : }
106 :
107 : int getCarWalkTransfer() const {
108 5136 : return myCarWalkTransfer;
109 : }
110 :
111 : /** @brief Builds the route between the given edges using the minimum effort at the given time
112 : The definition of the effort depends on the wished routing scheme */
113 211700 : bool compute(const E* from, const E* to,
114 : const double departPos, const std::string& originStopID,
115 : const double arrivalPos, const std::string& stopID,
116 : const double speed, const V* const vehicle,
117 : const SUMOVTypeParameter& pars,
118 : const SVCPermissions modeSet, const SUMOTime msTime,
119 : std::vector<TripItem>& into, const double externalFactor = 0.) {
120 211700 : createNet();
121 211700 : _IntermodalTrip trip(from, to, departPos, arrivalPos, speed, msTime, nullptr, pars, vehicle, modeSet, myExternalEffort, externalFactor);
122 : std::vector<const _IntermodalEdge*> intoEdges;
123 : //std::cout << "compute from=" << from->getID() << " to=" << to->getID() << " dPos=" << departPos << " aPos=" << arrivalPos << " stopID=" << stopID << " speed=" << speed << " veh=" << Named::getIDSecure(vehicle) << " modeSet=" << modeSet << " t=" << msTime << " iFrom=" << myIntermodalNet->getDepartEdge(from, trip.departPos)->getID() << " iTo=" << (stopID != "" ? myIntermodalNet->getStopEdge(stopID) : myIntermodalNet->getArrivalEdge(to, trip.arrivalPos))->getID() << "\n";
124 211700 : const _IntermodalEdge* iFrom = originStopID != "" ? myIntermodalNet->getStopEdge(originStopID) : myIntermodalNet->getDepartEdge(from, trip.departPos);
125 211700 : const _IntermodalEdge* iTo = stopID != "" ? myIntermodalNet->getStopEdge(stopID) : myIntermodalNet->getArrivalEdge(to, trip.arrivalPos);
126 211700 : const bool success = myInternalRouter->compute(iFrom, iTo, &trip, msTime, intoEdges, true);
127 211700 : if (success) {
128 211560 : std::string lastLine = "";
129 : const _IntermodalEdge* lastLineEdge = nullptr;
130 211560 : double lastLineTime = STEPS2TIME(msTime);
131 211560 : double time = STEPS2TIME(msTime);
132 211560 : double effort = 0.;
133 211560 : double length = 0.;
134 : const _IntermodalEdge* prev = nullptr;
135 2161990 : for (const _IntermodalEdge* iEdge : intoEdges) {
136 : bool addedEdge = false;
137 1950430 : if (iEdge->includeInRoute(false)) {
138 1117446 : if (iEdge->getLine() == "!stop") {
139 59148 : if (into.size() > 0) {
140 : // previous stage ends at stop
141 39499 : into.back().destStop = iEdge->getID();
142 39499 : if (myExternalEffort != nullptr) {
143 0 : into.back().description = myExternalEffort->output(iEdge->getNumericalID());
144 : }
145 39499 : if (lastLine == "!ped") {
146 : lastLine = ""; // a stop always starts a new trip item
147 : }
148 : } else {
149 : // trip starts at stop
150 : lastLine = "";
151 58947 : into.push_back(TripItem("!stop"));
152 19649 : into.back().destStop = iEdge->getID();
153 : }
154 : } else {
155 1058298 : if (iEdge->getLine() != lastLine || loopedLineTransfer(lastLineEdge, iEdge, lastLineTime, time)) {
156 : lastLine = iEdge->getLine();
157 : lastLineEdge = iEdge;
158 220119 : lastLineTime = time;
159 220119 : if (lastLine == "!car") {
160 4332 : into.push_back(TripItem(vehicle->getID()));
161 2166 : into.back().vType = vehicle->getParameter().vtypeid;
162 217953 : } else if (lastLine == "!ped") {
163 641502 : into.push_back(TripItem());
164 : } else {
165 8238 : into.push_back(TripItem(lastLine));
166 4119 : into.back().depart = iEdge->getIntended(time, into.back().intended);
167 : }
168 220119 : into.back().departPos = iEdge->getStartPos();
169 : }
170 1058298 : if (into.back().edges.empty() || into.back().edges.back() != iEdge->getEdge()) {
171 571040 : into.back().edges.push_back(iEdge->getEdge());
172 571040 : into.back().arrivalPos = iEdge->getEndPos();
173 : addedEdge = true;
174 : }
175 : }
176 : }
177 1950430 : const double prevTime = time;
178 1950430 : const double prevEffort = effort;
179 1950430 : const double prevLength = length;
180 1950430 : myInternalRouter->updateViaCost(prev, iEdge, &trip, time, effort, length);
181 : // correct intermodal length:
182 1950430 : length += iEdge->getPartialLength(&trip) - iEdge->getLength();
183 : prev = iEdge;
184 1950430 : if (!into.empty()) {
185 1756857 : into.back().traveltime += time - prevTime;
186 1756857 : into.back().cost += effort - prevEffort;
187 1756857 : into.back().length += length - prevLength;
188 1756857 : if (into.back().depart < 0) {
189 235653 : into.back().depart = prevTime;
190 : }
191 1756857 : if (addedEdge) {
192 571040 : into.back().exitTimes.push_back(time);
193 : }
194 : }
195 : }
196 : } else {
197 265 : const std::string oType = originStopID != "" ? "stop" : "edge";
198 140 : const std::string oID = originStopID != "" ? originStopID : from->getID();
199 257 : const std::string dType = stopID != "" ? "stop" : "edge";
200 140 : const std::string dID = stopID != "" ? stopID : to->getID();
201 420 : this->myErrorMsgHandler->informf(TL("No connection between % '%' and % '%' found."), oType, oID, dType, dID);
202 : }
203 211700 : if (into.size() > 0) {
204 211560 : into.back().arrivalPos = arrivalPos;
205 : }
206 : #ifdef IntermodalRouter_DEBUG_ROUTES
207 : double time = STEPS2TIME(msTime);
208 : for (const _IntermodalEdge* iEdge : intoEdges) {
209 : const double edgeEffort = myInternalRouter->getEffort(iEdge, &trip, time);
210 : time += edgeEffort;
211 : std::cout << iEdge->getID() << "(" << iEdge->getLine() << "): " << edgeEffort << " l=" << iEdge->getLength() << " pL=" << iEdge->getPartialLength(&trip) << "\n";
212 : }
213 : std::cout << TIME2STEPS(msTime) << " trip from " << from->getID() << " to " << (to != nullptr ? to->getID() : stopID)
214 : << " departPos=" << trip.departPos
215 : << " arrivalPos=" << trip.arrivalPos
216 : << " modes=" << getVehicleClassNames(modeSet)
217 : << " edges=" << toString(intoEdges)
218 : // << " resultEdges=" << toString(into)
219 : << " time=" << time
220 : << "\n";
221 : #endif
222 211700 : return success;
223 211700 : }
224 :
225 : /** @brief Builds the route between the given edges using the minimum effort at the given time
226 : The definition of the effort depends on the wished routing scheme */
227 0 : bool compute(const E*, const E*, const _IntermodalTrip* const,
228 : SUMOTime, std::vector<const E*>&, bool) {
229 0 : throw ProcessError(TL("Do not use this method"));
230 : }
231 :
232 504 : inline void setBulkMode(const bool mode) {
233 : SUMOAbstractRouter<E, _IntermodalTrip>::setBulkMode(mode);
234 504 : if (myInternalRouter != nullptr) {
235 24 : myInternalRouter->setBulkMode(mode);
236 : }
237 504 : }
238 :
239 208228 : void prohibit(const std::map<const E*, double>& toProhibit) {
240 208228 : createNet();
241 : std::map<const _IntermodalEdge*, double> toProhibitPE;
242 208228 : for (auto item : toProhibit) {
243 0 : toProhibitPE[myIntermodalNet->getBothDirections(item.first).first] = item.second;
244 0 : toProhibitPE[myIntermodalNet->getBothDirections(item.first).second] = item.second;
245 0 : toProhibitPE[myIntermodalNet->getCarEdge(item.first)] = item.second;
246 : }
247 208228 : myInternalRouter->prohibit(toProhibitPE);
248 208228 : }
249 :
250 16 : void writeNetwork(OutputDevice& dev) {
251 16 : createNet();
252 1988 : for (_IntermodalEdge* e : myIntermodalNet->getAllEdges()) {
253 1972 : dev.openTag(SUMO_TAG_EDGE);
254 1972 : dev.writeAttr(SUMO_ATTR_ID, e->getID());
255 1972 : dev.writeAttr(SUMO_ATTR_LINE, e->getLine());
256 1972 : dev.writeAttr(SUMO_ATTR_LENGTH, e->getLength());
257 5916 : dev.writeAttr("successors", toString(e->getSuccessors(SVC_IGNORING)));
258 3944 : dev.closeTag();
259 : }
260 16 : }
261 :
262 8 : void writeWeights(OutputDevice& dev) {
263 8 : createNet();
264 8 : SUMOVTypeParameter dummyVT(DEFAULT_PEDTYPE_ID, SVC_PEDESTRIAN);
265 8 : _IntermodalTrip trip(nullptr, nullptr, 0., 0., DEFAULT_PEDESTRIAN_SPEED, 0, nullptr,
266 : dummyVT, nullptr, SVC_PASSENGER | SVC_BICYCLE | SVC_BUS);
267 1040 : for (_IntermodalEdge* e : myIntermodalNet->getAllEdges()) {
268 1032 : dev.openTag(SUMO_TAG_EDGE);
269 1032 : dev.writeAttr(SUMO_ATTR_ID, e->getID());
270 1032 : dev.writeAttr("traveltime", e->getTravelTime(&trip, 0.));
271 1032 : dev.writeAttr("effort", e->getEffort(&trip, 0.));
272 2064 : dev.closeTag();
273 : }
274 8 : }
275 :
276 : Network* getNetwork() const {
277 74129 : return myIntermodalNet;
278 : }
279 :
280 : EffortCalculator* getExternalEffort() const {
281 4543 : return myExternalEffort;
282 : }
283 :
284 : private:
285 2604 : IntermodalRouter(Network* net, const int carWalkTransfer, double taxiWait, const std::string& routingAlgorithm,
286 : const int routingMode, EffortCalculator* calc) :
287 : SUMOAbstractRouter<E, _IntermodalTrip>("IntermodalRouterClone", true, nullptr, nullptr, false, false),
288 2604 : myAmClone(true), myInternalRouter(nullptr), myIntermodalNet(net),
289 2604 : myCarWalkTransfer(carWalkTransfer),
290 2604 : myTaxiWait(taxiWait),
291 5208 : myRoutingAlgorithm(routingAlgorithm), myRoutingMode(routingMode), myExternalEffort(calc) {
292 2604 : createNet();
293 2604 : }
294 :
295 0 : static inline double getCombined(const _IntermodalEdge* const edge, const _IntermodalTrip* const trip, double time) {
296 0 : return edge->getTravelTime(trip, time) + trip->externalFactor * trip->calc->getEffort(edge->getNumericalID());
297 : }
298 :
299 425160 : inline void createNet() {
300 425160 : if (myIntermodalNet == nullptr) {
301 5136 : myIntermodalNet = new Network(E::getAllEdges(), false, myCarWalkTransfer);
302 5136 : myIntermodalNet->addCarEdges(E::getAllEdges(), myTaxiWait);
303 5136 : myCallback(*this);
304 : }
305 425160 : if (myInternalRouter == nullptr) {
306 7740 : switch (myRoutingMode) {
307 7728 : case 0:
308 7728 : if (myRoutingAlgorithm == "astar") {
309 700 : myInternalRouter = new _InternalAStar(myIntermodalNet->getAllEdges(), true,
310 350 : gWeightsRandomFactor > 1 ? &_IntermodalEdge::getTravelTimeStaticRandomized : &_IntermodalEdge::getTravelTimeStatic, nullptr, true);
311 : } else {
312 14756 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true,
313 7378 : gWeightsRandomFactor > 1 ? &_IntermodalEdge::getTravelTimeStaticRandomized : &_IntermodalEdge::getTravelTimeStatic, nullptr, false, nullptr, true);
314 : }
315 : break;
316 12 : case 1:
317 12 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &_IntermodalEdge::getTravelTimeAggregated, nullptr, false, nullptr, true);
318 12 : break;
319 0 : case 2:
320 0 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &_IntermodalEdge::getEffortStatic, &_IntermodalEdge::getTravelTimeStatic, false, nullptr, true);
321 0 : break;
322 0 : case 3:
323 0 : if (myExternalEffort != nullptr) {
324 : std::vector<std::string> edgeLines;
325 0 : for (const auto e : myIntermodalNet->getAllEdges()) {
326 0 : edgeLines.push_back(e->getLine());
327 : }
328 0 : myExternalEffort->init(edgeLines);
329 0 : }
330 0 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &getCombined, &_IntermodalEdge::getTravelTimeStatic, false, myExternalEffort, true);
331 0 : break;
332 : }
333 : }
334 425160 : }
335 :
336 :
337 838194 : bool loopedLineTransfer(const _IntermodalEdge* prev, const _IntermodalEdge* cur, double prevTime, double time) {
338 : assert(prev != nullptr);
339 1676388 : if (myIntermodalNet->isLooped(cur->getLine())) {
340 : // check if the last two edges are served by different vehicles
341 : std::string intended1;
342 : std::string intended2;
343 30 : prev->getIntended(prevTime, intended1);
344 30 : cur->getIntended(time, intended2);
345 : return intended1 != intended2;
346 : }
347 : return false;
348 : }
349 :
350 : private:
351 : const bool myAmClone;
352 : _InternalRouter* myInternalRouter;
353 : Network* myIntermodalNet;
354 : CreateNetCallback myCallback;
355 : const int myCarWalkTransfer;
356 : const double myTaxiWait;
357 : const std::string myRoutingAlgorithm;
358 : const int myRoutingMode;
359 : EffortCalculator* const myExternalEffort;
360 :
361 :
362 : private:
363 : /// @brief Invalidated assignment operator
364 : IntermodalRouter& operator=(const IntermodalRouter& s);
365 :
366 : };
|
