Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-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 MSDispatch.cpp
15 : /// @author Jakob Erdmann
16 : /// @date 16.12.2019
17 : ///
18 : // An algorithm that performs dispatch for the taxi device
19 : /****************************************************************************/
20 : #include <config.h>
21 :
22 : #include <limits>
23 : #include <utils/xml/SUMOSAXAttributes.h>
24 : #include <microsim/MSNet.h>
25 : #include <microsim/MSEdge.h>
26 : #include <microsim/MSGlobals.h>
27 : #include <microsim/transportables/MSTransportable.h>
28 : #include "MSRoutingEngine.h"
29 : #include "MSDispatch.h"
30 :
31 : //#define DEBUG_RESERVATION
32 : //#define DEBUG_DETOUR
33 : //#define DEBUG_COND2(obj) (obj->getID() == "p0")
34 : #define DEBUG_COND2(obj) (true)
35 :
36 :
37 : // ===========================================================================
38 : // Reservation methods
39 : // ===========================================================================
40 :
41 : // ===========================================================================
42 : // MSDispatch methods
43 : // ===========================================================================
44 :
45 866 : MSDispatch::MSDispatch(const Parameterised::Map& params) :
46 : Parameterised(params),
47 866 : myOutput(nullptr),
48 866 : myReservationCount(0),
49 1732 : myRoutingMode(StringUtils::toInt(getParameter("routingMode", "1"))) {
50 866 : const std::string opt = "device.taxi.dispatch-algorithm.output";
51 866 : if (OptionsCont::getOptions().isSet(opt)) {
52 376 : OutputDevice::createDeviceByOption(opt, "DispatchInfo");
53 188 : myOutput = &OutputDevice::getDeviceByOption(opt);
54 : }
55 1732 : myKeepUnreachableResTime = string2time(OptionsCont::getOptions().getString("device.taxi.dispatch-keep-unreachable"));
56 866 : }
57 :
58 866 : MSDispatch::~MSDispatch() {
59 1255 : for (auto item : myGroupReservations) {
60 778 : for (Reservation* res : item.second) {
61 389 : delete res;
62 : }
63 : }
64 : myGroupReservations.clear();
65 866 : }
66 :
67 :
68 : Reservation*
69 3150 : MSDispatch::addReservation(MSTransportable* person,
70 : SUMOTime reservationTime,
71 : SUMOTime pickupTime,
72 : SUMOTime earliestPickupTime,
73 : const MSEdge* from, double fromPos,
74 : const MSStoppingPlace* fromStop,
75 : const MSEdge* to, double toPos,
76 : const MSStoppingPlace* toStop,
77 : std::string group,
78 : const std::string& line,
79 : int maxCapacity,
80 : int maxContainerCapacity) {
81 : std::string resID;
82 3150 : if (myLoadedReservations.size() > 0) {
83 62 : auto itL = myLoadedReservations.find(person->getID());
84 62 : if (itL != myLoadedReservations.end()) {
85 62 : resID = itL->second;
86 : myLoadedReservations.erase(itL);
87 : }
88 : }
89 : // no new reservation nedded if the person can be added to an existing group
90 3150 : if (group == "") {
91 : // the default empty group implies, no grouping is wanted (and
92 : // transportable ids are unique)
93 2806 : group = person->getID();
94 : } else {
95 : auto it2 = myRunningReservations.find(group);
96 344 : if (it2 != myRunningReservations.end()) {
97 256 : for (auto item : it2->second) {
98 : Reservation* res = const_cast<Reservation*>(item.first);
99 : if (res->persons.count(person) == 0
100 182 : && res->from == from
101 70 : && res->to == to
102 70 : && res->fromPos == fromPos
103 70 : && res->toPos == toPos) {
104 : MSDevice_Taxi* taxi = item.second;
105 : if ((taxi->getState() == taxi->PICKUP
106 60 : && remainingCapacity(taxi, res) > 0
107 60 : && taxi->compatibleLine(taxi->getHolder().getParameter().line, line))
108 70 : || resID == res->id) {
109 : //std::cout << SIMTIME << " addPerson=" << person->getID() << " extendRes=" << toString(res->persons) << " taxi=" << taxi->getHolder().getID() << " state=" << taxi->getState() << "\n";
110 : res->persons.insert(person);
111 60 : taxi->addCustomer(person, res);
112 : #ifdef DEBUG_RESERVATION
113 : if (DEBUG_COND2(person)) std::cout << SIMTIME << " extendedReservation p=" << person->getID() << " resID=" << res->getID() << " taxi=" << taxi->getID() << "\n";
114 : #endif
115 : return res;
116 : }
117 : }
118 : }
119 : }
120 : }
121 : Reservation* result = nullptr;
122 : bool added = false;
123 : auto it = myGroupReservations.find(group);
124 3090 : if (it != myGroupReservations.end()) {
125 : // try to add to existing reservation
126 496 : for (Reservation* res : it->second) {
127 : if (res->persons.count(person) == 0
128 444 : && res->from == from
129 166 : && res->to == to
130 158 : && res->fromPos == fromPos
131 158 : && res->toPos == toPos
132 158 : && (resID.empty() || res->id == resID)) {
133 158 : if (res->persons.size() > 0 && (*res->persons.begin())->isPerson() != person->isPerson()) {
134 0 : WRITE_WARNINGF(TL("Mixing reservations of persons and containers with the same group is not supported for % and %"),
135 : (*res->persons.begin())->getID(), person->getID());
136 : }
137 310 : if ((person->isPerson() && (int)res->persons.size() >= maxCapacity) ||
138 170 : (!person->isPerson() && (int)res->persons.size() >= maxContainerCapacity)) {
139 : // split group to ensure that at least one taxi is capable of delivering group size.
140 12 : continue;
141 : }
142 : res->persons.insert(person);
143 : result = res;
144 : added = true;
145 146 : break;
146 : }
147 : }
148 : }
149 3090 : if (!added) {
150 2944 : if (resID.empty()) {
151 5764 : resID = toString(myReservationCount++);
152 : }
153 2944 : Reservation* newRes = new Reservation(resID, {person}, reservationTime, pickupTime, earliestPickupTime, from, fromPos, fromStop, to, toPos, toStop, group, line);
154 2944 : myGroupReservations[group].push_back(newRes);
155 : result = newRes;
156 : }
157 3090 : myHasServableReservations = true;
158 : #ifdef DEBUG_RESERVATION
159 : if (DEBUG_COND2(person)) std::cout << SIMTIME
160 : << " addReservation p=" << person->getID()
161 : << " addID=" << result->getID()
162 : << " rT=" << time2string(reservationTime)
163 : << " pT=" << time2string(pickupTime)
164 : << " from=" << from->getID() << " fromPos=" << fromPos
165 : << " to=" << to->getID() << " toPos=" << toPos
166 : << " group=" << group
167 : << " added=" << added
168 : << "\n";
169 : #endif
170 3090 : return result;
171 : }
172 :
173 :
174 : std::string
175 87 : MSDispatch::removeReservation(MSTransportable* person,
176 : const MSEdge* from, double fromPos,
177 : const MSEdge* to, double toPos,
178 : std::string group) {
179 87 : if (group == "") {
180 : // the default empty group implies, no grouping is wanted (and
181 : // transportable ids are unique)
182 77 : group = person->getID();
183 : }
184 87 : std::string removedID = "";
185 : auto it = myGroupReservations.find(group);
186 87 : if (it != myGroupReservations.end()) {
187 77 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
188 77 : Reservation* res = *itRes;
189 : if (res->persons.count(person) != 0
190 77 : && res->from == from
191 77 : && res->to == to
192 77 : && res->fromPos == fromPos
193 77 : && res->toPos == toPos) {
194 : res->persons.erase(person);
195 77 : if (res->persons.empty()) {
196 77 : removedID = res->id;
197 77 : it->second.erase(itRes);
198 : // cleans up MSDispatch_Greedy
199 77 : fulfilledReservation(res);
200 77 : if (it->second.empty()) {
201 : myGroupReservations.erase(it);
202 : }
203 : }
204 : break;
205 : }
206 : }
207 : } else {
208 : auto it2 = myRunningReservations.find(group);
209 10 : if (it2 != myRunningReservations.end()) {
210 10 : for (auto item : it2->second) {
211 : const Reservation* const res = item.first;
212 : if (res->persons.count(person) != 0
213 10 : && res->from == from
214 10 : && res->to == to
215 10 : && res->fromPos == fromPos
216 10 : && res->toPos == toPos) {
217 10 : if (res->persons.size() == 1) {
218 10 : removedID = res->id;
219 : }
220 10 : item.second->cancelCustomer(person); // will delete res via fulfilledReservation if necessary
221 : break;
222 : }
223 : }
224 : }
225 : }
226 87 : myHasServableReservations = myGroupReservations.size() > 0;
227 : #ifdef DEBUG_RESERVATION
228 : if (DEBUG_COND2(person)) std::cout << SIMTIME
229 : << " removeReservation p=" << person->getID()
230 : << " from=" << from->getID() << " fromPos=" << fromPos
231 : << " to=" << to->getID() << " toPos=" << toPos
232 : << " group=" << group
233 : << " removedID=" << removedID
234 : << " hasServable=" << myHasServableReservations
235 : << "\n";
236 : #endif
237 87 : return removedID;
238 : }
239 :
240 :
241 : Reservation*
242 150 : MSDispatch::updateReservationFromPos(MSTransportable* person,
243 : const MSEdge* from, double fromPos,
244 : const MSEdge* to, double toPos,
245 : std::string group, double newFromPos) {
246 150 : if (group == "") {
247 : // the default empty group implies, no grouping is wanted (and
248 : // transportable ids are unique)
249 : group = person->getID();
250 : }
251 : Reservation* result = nullptr;
252 150 : std::string updatedID = "";
253 : auto it = myGroupReservations.find(group);
254 150 : if (it != myGroupReservations.end()) {
255 66 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
256 66 : Reservation* res = *itRes;
257 : // TODO: if there is already a reservation with the newFromPos, add to this reservation
258 : // TODO: if there are other persons in this reservation, create a new reservation for the updated one
259 : if (res->persons.count(person) != 0
260 66 : && res->from == from
261 66 : && res->to == to
262 66 : && res->fromPos == fromPos
263 66 : && res->toPos == toPos) {
264 : // update fromPos
265 66 : res->fromPos = newFromPos;
266 : result = res;
267 66 : updatedID = res->id;
268 : break;
269 : }
270 : }
271 : }
272 : #ifdef DEBUG_RESERVATION
273 : if (DEBUG_COND2(person)) std::cout << SIMTIME
274 : << " updateReservationFromPos p=" << person->getID()
275 : << " from=" << from->getID() << " fromPos=" << fromPos
276 : << " to=" << to->getID() << " toPos=" << toPos
277 : << " group=" << group
278 : << " newFromPos=" << newFromPos
279 : << " updatedID=" << updatedID
280 : << "\n";
281 : #endif
282 150 : return result;
283 : }
284 :
285 :
286 : std::vector<Reservation*>
287 19637 : MSDispatch::getReservations() {
288 : std::vector<Reservation*> reservations;
289 41294 : for (const auto& it : myGroupReservations) {
290 21657 : reservations.insert(reservations.end(), it.second.begin(), it.second.end());
291 : }
292 19637 : return reservations;
293 0 : }
294 :
295 :
296 : std::vector<const Reservation*>
297 4242 : MSDispatch::getRunningReservations() {
298 : std::vector<const Reservation*> result;
299 9613 : for (auto item : myRunningReservations) {
300 10742 : for (auto item2 : item.second) {
301 5371 : result.push_back(item2.first);
302 : }
303 : }
304 4242 : return result;
305 0 : }
306 :
307 :
308 : void
309 2606 : MSDispatch::servedReservation(const Reservation* res, MSDevice_Taxi* taxi) {
310 2606 : auto itR = myRunningReservations.find(res->group);
311 2606 : if (itR != myRunningReservations.end() && itR->second.count(res) != 0) {
312 : #ifdef DEBUG_RESERVATION
313 : std::cout << SIMTIME << " servedReservation res=" << res->id << " taxi=" << taxi->getID() << " (running)\n";
314 : #endif
315 : return; // was redispatch
316 : }
317 : #ifdef DEBUG_RESERVATION
318 : std::cout << SIMTIME << " servedReservation res=" << res->id << " taxi=" << taxi->getID() << "\n";
319 : #endif
320 2483 : auto it = myGroupReservations.find(res->group);
321 2483 : if (it == myGroupReservations.end()) {
322 0 : throw ProcessError(TL("Inconsistent group reservations."));
323 : }
324 2483 : auto it2 = std::find(it->second.begin(), it->second.end(), res);
325 2483 : if (it2 == it->second.end()) {
326 0 : throw ProcessError(TL("Inconsistent group reservations (2)."));
327 : }
328 2483 : myRunningReservations[res->group][res] = taxi;
329 2483 : const_cast<Reservation*>(*it2)->state = Reservation::ASSIGNED;
330 2483 : it->second.erase(it2);
331 2483 : if (it->second.empty()) {
332 : myGroupReservations.erase(it);
333 : }
334 : }
335 :
336 :
337 : void
338 4 : MSDispatch::swappedRunning(const Reservation* res, MSDevice_Taxi* taxi) {
339 : #ifdef DEBUG_RESERVATION
340 : std::cout << SIMTIME << " swapped res=" << res->id << " old=" << myRunningReservations[res->group][res]->getID() << " new=" << taxi->getID() << "\n";
341 : #endif
342 4 : myRunningReservations[res->group][res] = taxi;
343 4 : }
344 :
345 :
346 : void
347 2529 : MSDispatch::fulfilledReservation(const Reservation* res) {
348 2529 : myRunningReservations[res->group].erase(res);
349 2529 : if (myRunningReservations[res->group].empty()) {
350 : myRunningReservations.erase(res->group);
351 : }
352 2529 : delete res;
353 2529 : }
354 :
355 :
356 : SUMOAbstractRouter<MSEdge, SUMOVehicle>&
357 14392 : MSDispatch::getRouter() const {
358 28784 : return myRoutingMode == 1 ? MSRoutingEngine::getRouterTT(0, SVC_TAXI) : MSNet::getInstance()->getRouterTT(0);
359 : }
360 :
361 :
362 : SUMOTime
363 3763 : MSDispatch::computePickupTime(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
364 : ConstMSEdgeVector edges;
365 3763 : double fromPos = taxi->getHolder().getPositionOnLane() - NUMERICAL_EPS;
366 3763 : const MSEdge* from = *taxi->getHolder().getRerouteOrigin();
367 3763 : const bool originDiffers = from != taxi->getHolder().getEdge();
368 7493 : router.compute(from, originDiffers ? 0 : fromPos, res.from, res.fromPos, &taxi->getHolder(), t, edges, true);
369 3763 : if (edges.empty()) {
370 : return SUMOTime_MAX;
371 : } else {
372 2855 : if (originDiffers) {
373 : assert(from == *(taxi->getHolder().getCurrentRouteEdge() + 1));
374 33 : edges.insert(edges.begin(), taxi->getHolder().getEdge());
375 : }
376 2855 : return TIME2STEPS(router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, res.fromPos, t));
377 : }
378 3763 : }
379 :
380 :
381 : bool
382 3367 : MSDispatch::isReachable(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
383 : ConstMSEdgeVector edges;
384 3367 : router.compute(res.from, res.fromPos, res.to, res.toPos, &taxi->getHolder(), t, edges, true);
385 3367 : return !edges.empty();
386 3367 : }
387 :
388 :
389 : double
390 438 : MSDispatch::computeDetourTime(SUMOTime t, SUMOTime viaTime, const MSDevice_Taxi* taxi,
391 : const MSEdge* from, double fromPos,
392 : const MSEdge* via, double viaPos,
393 : const MSEdge* to, double toPos,
394 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router,
395 : double& timeDirect) {
396 : ConstMSEdgeVector edges;
397 438 : if (timeDirect < 0) {
398 372 : router.compute(from, fromPos, to, toPos, &taxi->getHolder(), t, edges, true);
399 372 : timeDirect = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, toPos, t);
400 : edges.clear();
401 : }
402 :
403 438 : router.compute(from, fromPos, via, viaPos, &taxi->getHolder(), t, edges, true);
404 438 : const double start = STEPS2TIME(t);
405 438 : const double leg1 = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, viaPos, t);
406 : #ifdef DEBUG_DETOUR
407 : std::cout << " leg1=" << toString(edges) << " startPos=" << fromPos << " toPos=" << viaPos << " time=" << leg1 << "\n";
408 : #endif
409 438 : const double wait = MAX2(0.0, STEPS2TIME(viaTime) - (start + leg1));
410 : edges.clear();
411 438 : const SUMOTime timeContinue = TIME2STEPS(start + leg1 + wait);
412 438 : router.compute(via, viaPos, to, toPos, &taxi->getHolder(), timeContinue, edges, true);
413 438 : const double leg2 = router.recomputeCostsPos(edges, &taxi->getHolder(), viaPos, toPos, timeContinue);
414 438 : const double timeDetour = leg1 + wait + leg2;
415 : #ifdef DEBUG_DETOUR
416 : std::cout << " leg2=" << toString(edges) << " startPos=" << viaPos << " toPos=" << toPos << " time=" << leg2 << "\n";
417 : std::cout << " t=" << STEPS2TIME(t) << " vt=" << STEPS2TIME(viaTime)
418 : << " from=" << from->getID() << " to=" << to->getID() << " via=" << via->getID()
419 : << " direct=" << timeDirect << " detour=" << timeDetour << " wait=" << wait << "\n";
420 : #endif
421 438 : return timeDetour;
422 438 : }
423 :
424 :
425 : int
426 4270 : MSDispatch::remainingCapacity(const MSDevice_Taxi* taxi, const Reservation* res) {
427 : assert(res->persons.size() > 0);
428 4270 : return ((*res->persons.begin())->isPerson()
429 4270 : ? taxi->getHolder().getVehicleType().getPersonCapacity()
430 192 : : taxi->getHolder().getVehicleType().getContainerCapacity()) - (int)res->persons.size();
431 : }
432 :
433 :
434 : void
435 10 : MSDispatch::saveState(OutputDevice& out, SUMOTime nextDispatch) const {
436 10 : out.openTag(SUMO_TAG_DISPATCHER);
437 10 : out.writeAttr(SUMO_ATTR_NEXT, nextDispatch);
438 10 : out.writeAttr(SUMO_ATTR_COUNT, myReservationCount);
439 :
440 10 : std::ostringstream internals;
441 24 : for (const auto& it : myRunningReservations) {
442 28 : for (const auto& item : it.second) {
443 28 : for (const MSTransportable* t : item.first->persons) {
444 14 : internals << t->getID() << " " << item.first->id << " ";
445 : }
446 : }
447 : }
448 54 : for (const auto& it : myGroupReservations) {
449 92 : for (const Reservation* res : it.second) {
450 96 : for (const MSTransportable* t : res->persons) {
451 48 : internals << t->getID() << " " << res->id << " ";
452 : }
453 : }
454 : }
455 10 : out.writeAttr(SUMO_ATTR_CUSTOMERS, internals.str());
456 10 : out.closeTag();
457 10 : }
458 :
459 :
460 : void
461 10 : MSDispatch::loadState(const SUMOSAXAttributes& attrs) {
462 10 : bool ok = true;
463 10 : myReservationCount = attrs.get<int>(SUMO_ATTR_COUNT, "dispatcher", ok);
464 20 : std::istringstream bis(attrs.getString(SUMO_ATTR_CUSTOMERS));
465 : std::string tID, rID;
466 72 : while (bis >> tID && bis >> rID) {
467 62 : myLoadedReservations[tID] = rID;
468 : }
469 10 : }
470 :
471 :
472 :
473 : /****************************************************************************/
|
