1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-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    MELoop.cpp
11 /// @author  Daniel Krajzewicz
12 /// @date    Tue, May 2005
13 /// @version $Id$
14 ///
15 // The main mesocopic simulation loop
16 /****************************************************************************/
17 
18 
19 // ===========================================================================
20 // included modules
21 // ===========================================================================
22 #include <config.h>
23 
24 #include <queue>
25 #include <vector>
26 #include <map>
27 #include <cmath>
28 
29 #include <microsim/MSNet.h>
30 #include <microsim/MSEdge.h>
31 #include <microsim/MSGlobals.h>
32 #include <microsim/MSLane.h>
33 #include <microsim/MSVehicle.h>
34 #include <microsim/MSVehicleControl.h>
35 #include <utils/options/OptionsCont.h>
36 #include <utils/common/ToString.h>
37 #include <utils/common/FileHelpers.h>
38 #include <utils/common/SUMOTime.h>
39 #include <utils/common/RandHelper.h>
40 #include "MELoop.h"
41 #include "MESegment.h"
42 #include "MEVehicle.h"
43 
44 
45 // ===========================================================================
46 // method definitions
47 // ===========================================================================
MELoop(const SUMOTime recheckInterval)48 MELoop::MELoop(const SUMOTime recheckInterval) : myFullRecheckInterval(recheckInterval), myLinkRecheckInterval(TIME2STEPS(1)) {
49 }
50 
~MELoop()51 MELoop::~MELoop() {
52     for (std::vector<MESegment*>::const_iterator j = myEdges2FirstSegments.begin(); j != myEdges2FirstSegments.end(); ++j) {
53         for (MESegment* s = *j; s != nullptr;) {
54             MESegment* n = s->getNextSegment();
55             delete s;
56             s = n;
57         }
58     }
59 }
60 
61 
62 void
simulate(SUMOTime tMax)63 MELoop::simulate(SUMOTime tMax) {
64     while (!myLeaderCars.empty()) {
65         const SUMOTime time = myLeaderCars.begin()->first;
66         assert(time > tMax - DELTA_T);
67         if (time > tMax) {
68             return;
69         }
70         std::vector<MEVehicle*> vehs = myLeaderCars[time];
71         myLeaderCars.erase(time);
72         for (std::vector<MEVehicle*>::const_iterator i = vehs.begin(); i != vehs.end(); ++i) {
73             checkCar(*i);
74             assert(myLeaderCars.empty() || myLeaderCars.begin()->first >= time);
75         }
76     }
77 }
78 
79 
80 bool
changeSegment(MEVehicle * veh,SUMOTime leaveTime,MESegment * const toSegment,const bool ignoreLink)81 MELoop::changeSegment(MEVehicle* veh, SUMOTime leaveTime, MESegment* const toSegment, const bool ignoreLink) {
82     MESegment* const onSegment = veh->getSegment();
83     if (MESegment::isInvalid(toSegment)) {
84         if (onSegment != nullptr) {
85             onSegment->send(veh, toSegment, leaveTime, toSegment == nullptr ? MSMoveReminder::NOTIFICATION_ARRIVED : MSMoveReminder::NOTIFICATION_VAPORIZED);
86         } else {
87             WRITE_WARNING("Vehicle '" + veh->getID() + "' teleports beyond arrival edge '" + veh->getEdge()->getID() + "', time " + time2string(leaveTime) + ".");
88         }
89         veh->setSegment(toSegment); // signal arrival
90         MSNet::getInstance()->getVehicleControl().scheduleVehicleRemoval(veh);
91         return true;
92     }
93     if (toSegment->hasSpaceFor(veh, leaveTime) && (ignoreLink || veh->mayProceed())) {
94         if (onSegment != nullptr) {
95             onSegment->send(veh, toSegment, leaveTime, onSegment->getNextSegment() == nullptr ? MSMoveReminder::NOTIFICATION_JUNCTION : MSMoveReminder::NOTIFICATION_SEGMENT);
96             toSegment->receive(veh, leaveTime, false, ignoreLink);
97         } else {
98             WRITE_WARNING("Vehicle '" + veh->getID() + "' ends teleporting on edge '" + toSegment->getEdge().getID()
99                           + "':" + toString(toSegment->getIndex()) + ", time " + time2string(leaveTime) + ".");
100             // this is not quite correct but suffices for interrogation by
101             // subsequent methods (veh->getSpeed() needs segment != 0)
102             veh->setSegment(myEdges2FirstSegments[veh->getEdge()->getNumericalID()]);
103             toSegment->receive(veh, leaveTime, false, true);
104         }
105         return true;
106     }
107     return false;
108 }
109 
110 
111 void
checkCar(MEVehicle * veh)112 MELoop::checkCar(MEVehicle* veh) {
113     const SUMOTime leaveTime = veh->getEventTime();
114     MESegment* const onSegment = veh->getSegment();
115     MESegment* const toSegment = nextSegment(onSegment, veh);
116     const bool teleporting = (onSegment == nullptr); // is the vehicle currently teleporting?
117     if (changeSegment(veh, leaveTime, toSegment, teleporting)) {
118         return;
119     }
120     if (MSGlobals::gTimeToGridlock > 0 && veh->getWaitingTime() > MSGlobals::gTimeToGridlock) {
121         teleportVehicle(veh, toSegment);
122         return;
123     }
124     if (veh->getBlockTime() == SUMOTime_MAX) {
125         veh->setBlockTime(leaveTime);
126     }
127     if (leaveTime < toSegment->getEntryBlockTime()) {
128         // receiving segment has recently received another vehicle
129         veh->setEventTime(toSegment->getEntryBlockTime());
130     } else if (toSegment->hasSpaceFor(veh, leaveTime) && !veh->mayProceed()) {
131         // either the junction is blocked or the traffic light is red
132         veh->setEventTime(leaveTime + MAX2(SUMOTime(1), myLinkRecheckInterval));
133     } else {
134         SUMOTime newEventTime = MAX3(toSegment->getEventTime() + 1, leaveTime + 1, leaveTime + myFullRecheckInterval);
135         if (MSGlobals::gTimeToGridlock > 0) {
136             // if teleporting is enabled, make sure we look at the vehicle when the the gridlock-time is up
137             newEventTime = MIN2(newEventTime, veh->getBlockTime() + MSGlobals::gTimeToGridlock + 1);
138         }
139         veh->setEventTime(newEventTime);
140     }
141     addLeaderCar(veh, onSegment->getLink(veh));
142 }
143 
144 
145 void
teleportVehicle(MEVehicle * veh,MESegment * const toSegment)146 MELoop::teleportVehicle(MEVehicle* veh, MESegment* const toSegment) {
147     const SUMOTime leaveTime = veh->getEventTime();
148     MESegment* const onSegment = veh->getSegment();
149     const bool teleporting = (onSegment == nullptr); // is the vehicle already teleporting?
150     // try to find a place on the current edge
151     MESegment* teleSegment = toSegment->getNextSegment();
152     while (teleSegment != nullptr && !teleSegment->hasSpaceFor(veh, leaveTime)) {
153         // @caution the time to get to the next segment here is ignored XXX
154         teleSegment = teleSegment->getNextSegment();
155     }
156     if (teleSegment != nullptr) {
157         if (!teleporting) {
158             // we managed to teleport in a single jump
159             WRITE_WARNING("Teleporting vehicle '" + veh->getID() + "'; waited too long, from edge '" + onSegment->getEdge().getID()
160                           + "':" + toString(onSegment->getIndex())
161                           + " to edge '" + teleSegment->getEdge().getID()
162                           + "':" + toString(teleSegment->getIndex())
163                           + ", time " + time2string(leaveTime) + ".");
164             MSNet::getInstance()->getVehicleControl().registerTeleportJam();
165         }
166         changeSegment(veh, leaveTime, teleSegment, true);
167         teleSegment->setEntryBlockTime(leaveTime); // teleports should not block normal flow
168     } else {
169         // teleport across the current edge and try insertion later
170         if (!teleporting) {
171             // announce start of multi-step teleport, arrival will be announced in changeSegment()
172             WRITE_WARNING("Teleporting vehicle '" + veh->getID() + "'; waited too long, from edge '" + onSegment->getEdge().getID()
173                           + "':" + toString(onSegment->getIndex()) + ", time " + time2string(leaveTime) + ".");
174             MSNet::getInstance()->getVehicleControl().registerTeleportJam();
175             // remove from current segment
176             onSegment->send(veh, nullptr, leaveTime, MSMoveReminder::NOTIFICATION_TELEPORT);
177             // mark veh as teleporting
178             veh->setSegment(nullptr, 0);
179         }
180         // @caution microsim uses current travel time teleport duration
181         const SUMOTime teleArrival = leaveTime + TIME2STEPS(veh->getEdge()->getLength() / MAX2(veh->getEdge()->getSpeedLimit(), NUMERICAL_EPS));
182         const bool atDest = veh->moveRoutePointer();
183         if (atDest) {
184             // teleporting to end of route
185             changeSegment(veh, teleArrival, nullptr, true);
186         } else {
187             veh->setEventTime(teleArrival);
188             addLeaderCar(veh, nullptr);
189             // teleporting vehicles must react to rerouters
190             getSegmentForEdge(*veh->getEdge())->addReminders(veh);
191             veh->activateReminders(MSMoveReminder::NOTIFICATION_JUNCTION);
192         }
193     }
194 }
195 
196 
197 void
addLeaderCar(MEVehicle * veh,MSLink * link)198 MELoop::addLeaderCar(MEVehicle* veh, MSLink* link) {
199     myLeaderCars[veh->getEventTime()].push_back(veh);
200     setApproaching(veh, link);
201 }
202 
203 
204 void
setApproaching(MEVehicle * veh,MSLink * link)205 MELoop::setApproaching(MEVehicle* veh, MSLink* link) {
206     if (link != nullptr) {
207         link->setApproaching(veh, veh->getEventTime() + (link->getState() == LINKSTATE_ALLWAY_STOP ?
208                              (SUMOTime)RandHelper::rand((int)2) : 0), // tie braker
209                              veh->getSpeed(), veh->getSpeed(), true,
210                              veh->getEventTime(), veh->getSpeed(), veh->getWaitingTime(),
211                              // @note: dist is not used by meso (getZipperSpeed is never called)
212                              veh->getSegment()->getLength());
213     }
214 }
215 
216 
217 void
removeLeaderCar(MEVehicle * v)218 MELoop::removeLeaderCar(MEVehicle* v) {
219     std::vector<MEVehicle*>& cands = myLeaderCars[v->getEventTime()];
220     cands.erase(find(cands.begin(), cands.end(), v));
221 }
222 
223 
224 MESegment*
nextSegment(MESegment * s,MEVehicle * v)225 MELoop::nextSegment(MESegment* s, MEVehicle* v) {
226     if (s != nullptr) { // vehicle is not teleporting
227         MESegment* next = s->getNextSegment();
228         if (next != nullptr) {
229             // ok, the street continues
230             return next;
231         }
232     }
233     // we have to check the next edge in the vehicle's route
234     const MSEdge* nextEdge = v->succEdge(1);
235     if (nextEdge == nullptr) {
236         // end of route
237         return nullptr;
238     }
239     return myEdges2FirstSegments[nextEdge->getNumericalID()];
240 }
241 
242 
243 int
numSegmentsFor(const double length,const double sLength)244 MELoop::numSegmentsFor(const double length, const double sLength) {
245     int no = (int)floor(length / sLength + 0.5);
246     if (no == 0) { // assure there is at least one segment
247         return 1;
248     } else {
249         return no;
250     }
251 }
252 
253 
254 void
buildSegmentsFor(const MSEdge & e,const OptionsCont & oc)255 MELoop::buildSegmentsFor(const MSEdge& e, const OptionsCont& oc) {
256     const double length = e.getLength();
257     int no = numSegmentsFor(length, oc.getFloat("meso-edgelength"));
258     const double slength = length / (double)no;
259     MESegment* newSegment = nullptr;
260     MESegment* nextSegment = nullptr;
261     bool multiQueue = oc.getBool("meso-multi-queue");
262     bool junctionControl = oc.getBool("meso-junction-control") || isEnteringRoundabout(e);
263     for (int s = no - 1; s >= 0; s--) {
264         std::string id = e.getID() + ":" + toString(s);
265         newSegment =
266             new MESegment(id, e, nextSegment, slength,
267                           e.getLanes()[0]->getSpeedLimit(), s,
268                           string2time(oc.getString("meso-tauff")), string2time(oc.getString("meso-taufj")),
269                           string2time(oc.getString("meso-taujf")), string2time(oc.getString("meso-taujj")),
270                           oc.getFloat("meso-jam-threshold"), multiQueue, junctionControl);
271         multiQueue = false;
272         junctionControl = false;
273         nextSegment = newSegment;
274     }
275     while (e.getNumericalID() >= static_cast<int>(myEdges2FirstSegments.size())) {
276         myEdges2FirstSegments.push_back(0);
277     }
278     myEdges2FirstSegments[e.getNumericalID()] = newSegment;
279 }
280 
281 
282 MESegment*
getSegmentForEdge(const MSEdge & e,double pos)283 MELoop::getSegmentForEdge(const MSEdge& e, double pos) {
284     if (e.getNumericalID() >= (int)myEdges2FirstSegments.size()) {
285         return nullptr;
286     }
287     MESegment* s = myEdges2FirstSegments[e.getNumericalID()];
288     if (pos > 0) {
289         double cpos = 0;
290         while (s->getNextSegment() != nullptr && cpos + s->getLength() < pos) {
291             cpos += s->getLength();
292             s = s->getNextSegment();
293         }
294     }
295     return s;
296 }
297 
298 
299 bool
isEnteringRoundabout(const MSEdge & e)300 MELoop::isEnteringRoundabout(const MSEdge& e) {
301     for (const MSEdge* succ : e.getSuccessors()) {
302         if (succ->isRoundabout()) {
303             return true;
304         }
305     }
306     return false;
307 }
308 
309 /****************************************************************************/
310