Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-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 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 DijkstraRouter<_IntermodalEdge, _IntermodalTrip> _InternalDijkstra;
62 : typedef AStarRouter<_IntermodalEdge, _IntermodalTrip> _InternalAStar;
63 :
64 : public:
65 : struct TripItem {
66 211309 : TripItem(const std::string& _line = "") :
67 422618 : line(_line), intended(_line) {}
68 : std::string line;
69 : std::string vType = "";
70 : std::string destStop = "";
71 : std::string intended; // intended public transport vehicle id
72 : double depart = -1.; // intended public transport departure
73 : std::vector<const E*> edges;
74 : double traveltime = 0.;
75 : double cost = 0.;
76 : double length = 0.;
77 : double departPos = INVALID_DOUBLE;
78 : double arrivalPos = INVALID_DOUBLE;
79 : std::string description = "";
80 : std::vector<double> exitTimes;
81 : };
82 :
83 : /// Constructor
84 17313 : IntermodalRouter(CreateNetCallback callback, const int carWalkTransfer, double taxiWait, const std::string& routingAlgorithm,
85 : const int routingMode = 0, EffortCalculator* calc = nullptr) :
86 : SUMOAbstractRouter<E, _IntermodalTrip>("IntermodalRouter", true, nullptr, nullptr, false, false),
87 17313 : myAmClone(false), myInternalRouter(nullptr), myIntermodalNet(nullptr),
88 17313 : myCallback(callback), myCarWalkTransfer(carWalkTransfer), myTaxiWait(taxiWait),
89 17313 : myRoutingAlgorithm(routingAlgorithm),
90 34626 : myRoutingMode(routingMode), myExternalEffort(calc) {
91 17313 : }
92 :
93 : /// Destructor
94 39334 : virtual ~IntermodalRouter() {
95 7073 : delete myInternalRouter;
96 19667 : if (!myAmClone) {
97 17311 : delete myIntermodalNet;
98 : }
99 59001 : }
100 :
101 2356 : SUMOAbstractRouter<E, _IntermodalTrip>* clone() {
102 2356 : createNet();
103 2356 : return new IntermodalRouter<E, L, N, V>(myIntermodalNet, myCarWalkTransfer, myTaxiWait, myRoutingAlgorithm, myRoutingMode, myExternalEffort);
104 : }
105 :
106 : int getCarWalkTransfer() const {
107 4718 : return myCarWalkTransfer;
108 : }
109 :
110 : /** @brief Builds the route between the given edges using the minimum effort at the given time
111 : The definition of the effort depends on the wished routing scheme */
112 184834 : bool compute(const E* from, const E* to,
113 : const double departPos, const std::string& originStopID,
114 : const double arrivalPos, const std::string& stopID,
115 : const double speed, const V* const vehicle, const SVCPermissions modeSet, const SUMOTime msTime,
116 : std::vector<TripItem>& into, const double externalFactor = 0.) {
117 184834 : createNet();
118 184834 : _IntermodalTrip trip(from, to, departPos, arrivalPos, speed, msTime, 0, vehicle, modeSet, myExternalEffort, externalFactor);
119 : std::vector<const _IntermodalEdge*> intoEdges;
120 : //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";
121 184834 : const _IntermodalEdge* iFrom = originStopID != "" ? myIntermodalNet->getStopEdge(originStopID) : myIntermodalNet->getDepartEdge(from, trip.departPos);
122 184834 : const _IntermodalEdge* iTo = stopID != "" ? myIntermodalNet->getStopEdge(stopID) : myIntermodalNet->getArrivalEdge(to, trip.arrivalPos);
123 184834 : const bool success = myInternalRouter->compute(iFrom, iTo, &trip, msTime, intoEdges, true);
124 184834 : if (success) {
125 184739 : std::string lastLine = "";
126 : const _IntermodalEdge* lastLineEdge = nullptr;
127 184739 : double lastLineTime = STEPS2TIME(msTime);
128 184739 : double time = STEPS2TIME(msTime);
129 184739 : double effort = 0.;
130 184739 : double length = 0.;
131 : const _IntermodalEdge* prev = nullptr;
132 1914790 : for (const _IntermodalEdge* iEdge : intoEdges) {
133 : bool addedEdge = false;
134 1730051 : if (iEdge->includeInRoute(false)) {
135 1000917 : if (iEdge->getLine() == "!stop") {
136 57303 : if (into.size() > 0) {
137 : // previous stage ends at stop
138 38098 : into.back().destStop = iEdge->getID();
139 38098 : if (myExternalEffort != nullptr) {
140 0 : into.back().description = myExternalEffort->output(iEdge->getNumericalID());
141 : }
142 38098 : if (lastLine == "!ped") {
143 : lastLine = ""; // a stop always starts a new trip item
144 : }
145 : } else {
146 : // trip starts at stop
147 : lastLine = "";
148 57615 : into.push_back(TripItem("!stop"));
149 19205 : into.back().destStop = iEdge->getID();
150 : }
151 : } else {
152 943614 : if (iEdge->getLine() != lastLine || loopedLineTransfer(lastLineEdge, iEdge, lastLineTime, time)) {
153 : lastLine = iEdge->getLine();
154 : lastLineEdge = iEdge;
155 192104 : lastLineTime = time;
156 192104 : if (lastLine == "!car") {
157 4076 : into.push_back(TripItem(vehicle->getID()));
158 2038 : into.back().vType = vehicle->getParameter().vtypeid;
159 190066 : } else if (lastLine == "!ped") {
160 559284 : into.push_back(TripItem());
161 : } else {
162 7276 : into.push_back(TripItem(lastLine));
163 3638 : into.back().depart = iEdge->getIntended(time, into.back().intended);
164 : }
165 192104 : into.back().departPos = iEdge->getStartPos();
166 : }
167 943614 : if (into.back().edges.empty() || into.back().edges.back() != iEdge->getEdge()) {
168 511231 : into.back().edges.push_back(iEdge->getEdge());
169 511231 : into.back().arrivalPos = iEdge->getEndPos();
170 : addedEdge = true;
171 : }
172 : }
173 : }
174 1730051 : const double prevTime = time;
175 1730051 : const double prevEffort = effort;
176 1730051 : const double prevLength = length;
177 1730051 : myInternalRouter->updateViaCost(prev, iEdge, &trip, time, effort, length);
178 : // correct intermodal length:
179 1730051 : length += iEdge->getPartialLength(&trip) - iEdge->getLength();
180 : prev = iEdge;
181 1730051 : if (!into.empty()) {
182 1563284 : into.back().traveltime += time - prevTime;
183 1563284 : into.back().cost += effort - prevEffort;
184 1563284 : into.back().length += length - prevLength;
185 1563284 : if (into.back().depart < 0) {
186 207675 : into.back().depart = prevTime;
187 : }
188 1563284 : if (addedEdge) {
189 511231 : into.back().exitTimes.push_back(time);
190 : }
191 : }
192 : }
193 : } else {
194 175 : const std::string oType = originStopID != "" ? "stop" : "edge";
195 95 : const std::string oID = originStopID != "" ? originStopID : from->getID();
196 175 : const std::string dType = stopID != "" ? "stop" : "edge";
197 95 : const std::string dID = stopID != "" ? stopID : to->getID();
198 285 : this->myErrorMsgHandler->informf(TL("No connection between % '%' and % '%' found."), oType, oID, dType, dID);
199 : }
200 184834 : if (into.size() > 0) {
201 184739 : into.back().arrivalPos = arrivalPos;
202 : }
203 : #ifdef IntermodalRouter_DEBUG_ROUTES
204 : double time = STEPS2TIME(msTime);
205 : for (const _IntermodalEdge* iEdge : intoEdges) {
206 : const double edgeEffort = myInternalRouter->getEffort(iEdge, &trip, time);
207 : time += edgeEffort;
208 : std::cout << iEdge->getID() << "(" << iEdge->getLine() << "): " << edgeEffort << " l=" << iEdge->getLength() << " pL=" << iEdge->getPartialLength(&trip) << "\n";
209 : }
210 : std::cout << TIME2STEPS(msTime) << " trip from " << from->getID() << " to " << (to != nullptr ? to->getID() : stopID)
211 : << " departPos=" << trip.departPos
212 : << " arrivalPos=" << trip.arrivalPos
213 : << " modes=" << getVehicleClassNames(modeSet)
214 : << " edges=" << toString(intoEdges)
215 : // << " resultEdges=" << toString(into)
216 : << " time=" << time
217 : << "\n";
218 : #endif
219 184834 : return success;
220 184834 : }
221 :
222 : /** @brief Builds the route between the given edges using the minimum effort at the given time
223 : The definition of the effort depends on the wished routing scheme */
224 0 : bool compute(const E*, const E*, const _IntermodalTrip* const,
225 : SUMOTime, std::vector<const E*>&, bool) {
226 0 : throw ProcessError(TL("Do not use this method"));
227 : }
228 :
229 288 : inline void setBulkMode(const bool mode) {
230 : SUMOAbstractRouter<E, _IntermodalTrip>::setBulkMode(mode);
231 288 : if (myInternalRouter != nullptr) {
232 24 : myInternalRouter->setBulkMode(mode);
233 : }
234 288 : }
235 :
236 183233 : void prohibit(const std::vector<E*>& toProhibit) {
237 183233 : createNet();
238 : std::vector<_IntermodalEdge*> toProhibitPE;
239 183233 : for (typename std::vector<E*>::const_iterator it = toProhibit.begin(); it != toProhibit.end(); ++it) {
240 0 : toProhibitPE.push_back(myIntermodalNet->getBothDirections(*it).first);
241 0 : toProhibitPE.push_back(myIntermodalNet->getBothDirections(*it).second);
242 0 : toProhibitPE.push_back(myIntermodalNet->getCarEdge(*it));
243 : }
244 183233 : myInternalRouter->prohibit(toProhibitPE);
245 183233 : }
246 :
247 16 : void writeNetwork(OutputDevice& dev) {
248 16 : createNet();
249 1772 : for (_IntermodalEdge* e : myIntermodalNet->getAllEdges()) {
250 1756 : dev.openTag(SUMO_TAG_EDGE);
251 : dev.writeAttr(SUMO_ATTR_ID, e->getID());
252 : dev.writeAttr(SUMO_ATTR_LINE, e->getLine());
253 1756 : dev.writeAttr(SUMO_ATTR_LENGTH, e->getLength());
254 5268 : dev.writeAttr("successors", toString(e->getSuccessors(SVC_IGNORING)));
255 3512 : dev.closeTag();
256 : }
257 16 : }
258 :
259 8 : void writeWeights(OutputDevice& dev) {
260 8 : createNet();
261 8 : _IntermodalTrip trip(nullptr, nullptr, 0., 0., DEFAULT_PEDESTRIAN_SPEED, 0, 0, nullptr, SVC_PASSENGER | SVC_BICYCLE | SVC_BUS);
262 832 : for (_IntermodalEdge* e : myIntermodalNet->getAllEdges()) {
263 824 : dev.openTag(SUMO_TAG_EDGE);
264 : dev.writeAttr(SUMO_ATTR_ID, e->getID());
265 824 : dev.writeAttr("traveltime", e->getTravelTime(&trip, 0.));
266 824 : dev.writeAttr("effort", e->getEffort(&trip, 0.));
267 1648 : dev.closeTag();
268 : }
269 8 : }
270 :
271 : Network* getNetwork() const {
272 38963 : return myIntermodalNet;
273 : }
274 :
275 : EffortCalculator* getExternalEffort() const {
276 4220 : return myExternalEffort;
277 : }
278 :
279 : private:
280 2356 : IntermodalRouter(Network* net, const int carWalkTransfer, double taxiWait, const std::string& routingAlgorithm,
281 : const int routingMode, EffortCalculator* calc) :
282 : SUMOAbstractRouter<E, _IntermodalTrip>("IntermodalRouterClone", true, nullptr, nullptr, false, false),
283 2356 : myAmClone(true), myInternalRouter(nullptr), myIntermodalNet(net),
284 2356 : myCarWalkTransfer(carWalkTransfer),
285 2356 : myTaxiWait(taxiWait),
286 4712 : myRoutingAlgorithm(routingAlgorithm), myRoutingMode(routingMode), myExternalEffort(calc) {
287 2356 : createNet();
288 2356 : }
289 :
290 0 : static inline double getCombined(const _IntermodalEdge* const edge, const _IntermodalTrip* const trip, double time) {
291 0 : return edge->getTravelTime(trip, time) + trip->externalFactor * trip->calc->getEffort(edge->getNumericalID());
292 : }
293 :
294 372803 : inline void createNet() {
295 372803 : if (myIntermodalNet == nullptr) {
296 4718 : myIntermodalNet = new Network(E::getAllEdges(), false, myCarWalkTransfer);
297 4718 : myIntermodalNet->addCarEdges(E::getAllEdges(), myTaxiWait);
298 4718 : myCallback(*this);
299 : }
300 372803 : if (myInternalRouter == nullptr) {
301 7074 : switch (myRoutingMode) {
302 7062 : case 0:
303 7062 : if (myRoutingAlgorithm == "astar") {
304 642 : myInternalRouter = new _InternalAStar(myIntermodalNet->getAllEdges(), true,
305 321 : gWeightsRandomFactor > 1 ? &_IntermodalEdge::getTravelTimeStaticRandomized : &_IntermodalEdge::getTravelTimeStatic, nullptr, true);
306 : } else {
307 13482 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true,
308 6741 : gWeightsRandomFactor > 1 ? &_IntermodalEdge::getTravelTimeStaticRandomized : &_IntermodalEdge::getTravelTimeStatic, nullptr, false, nullptr, true);
309 : }
310 : break;
311 12 : case 1:
312 12 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &_IntermodalEdge::getTravelTimeAggregated, nullptr, false, nullptr, true);
313 12 : break;
314 0 : case 2:
315 0 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &_IntermodalEdge::getEffortStatic, &_IntermodalEdge::getTravelTimeStatic, false, nullptr, true);
316 0 : break;
317 0 : case 3:
318 0 : if (myExternalEffort != nullptr) {
319 : std::vector<std::string> edgeLines;
320 0 : for (const auto e : myIntermodalNet->getAllEdges()) {
321 0 : edgeLines.push_back(e->getLine());
322 : }
323 0 : myExternalEffort->init(edgeLines);
324 0 : }
325 0 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &getCombined, &_IntermodalEdge::getTravelTimeStatic, false, myExternalEffort, true);
326 0 : break;
327 : }
328 : }
329 372803 : }
330 :
331 :
332 751525 : bool loopedLineTransfer(const _IntermodalEdge* prev, const _IntermodalEdge* cur, double prevTime, double time) {
333 : assert(prev != nullptr);
334 1503050 : if (myIntermodalNet->isLooped(cur->getLine())) {
335 : // check if the last two edges are served by different vehicles
336 : std::string intended1;
337 : std::string intended2;
338 30 : prev->getIntended(prevTime, intended1);
339 30 : cur->getIntended(time, intended2);
340 : return intended1 != intended2;
341 : }
342 : return false;
343 : }
344 :
345 : private:
346 : const bool myAmClone;
347 : _InternalRouter* myInternalRouter;
348 : Network* myIntermodalNet;
349 : CreateNetCallback myCallback;
350 : const int myCarWalkTransfer;
351 : const double myTaxiWait;
352 : const std::string myRoutingAlgorithm;
353 : const int myRoutingMode;
354 : EffortCalculator* const myExternalEffort;
355 :
356 :
357 : private:
358 : /// @brief Invalidated assignment operator
359 : IntermodalRouter& operator=(const IntermodalRouter& s);
360 :
361 : };
|
