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 <microsim/MSNet.h>
24 : #include <microsim/MSEdge.h>
25 : #include <microsim/MSGlobals.h>
26 : #include <microsim/transportables/MSTransportable.h>
27 : #include "MSRoutingEngine.h"
28 : #include "MSDispatch.h"
29 :
30 : //#define DEBUG_RESERVATION
31 : //#define DEBUG_DETOUR
32 : //#define DEBUG_COND2(obj) (obj->getID() == "p0")
33 : #define DEBUG_COND2(obj) (true)
34 :
35 :
36 : // ===========================================================================
37 : // Reservation methods
38 : // ===========================================================================
39 :
40 : // ===========================================================================
41 : // MSDispatch methods
42 : // ===========================================================================
43 :
44 815 : MSDispatch::MSDispatch(const Parameterised::Map& params) :
45 : Parameterised(params),
46 815 : myOutput(nullptr),
47 815 : myReservationCount(0),
48 1630 : myRoutingMode(StringUtils::toInt(getParameter("routingMode", "1")))
49 : {
50 815 : const std::string opt = "device.taxi.dispatch-algorithm.output";
51 815 : if (OptionsCont::getOptions().isSet(opt)) {
52 336 : OutputDevice::createDeviceByOption(opt, "DispatchInfo");
53 168 : myOutput = &OutputDevice::getDeviceByOption(opt);
54 : }
55 1630 : myKeepUnreachableResTime = string2time(OptionsCont::getOptions().getString("device.taxi.dispatch-keep-unreachable"));
56 815 : }
57 :
58 815 : MSDispatch::~MSDispatch() {
59 1190 : for (auto item : myGroupReservations) {
60 750 : for (Reservation* res : item.second) {
61 375 : delete res;
62 : }
63 : }
64 : myGroupReservations.clear();
65 815 : }
66 :
67 :
68 : Reservation*
69 2846 : 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 : // no new reservation nedded if the person can be added to an existing group
82 2846 : if (group == "") {
83 : // the default empty group implies, no grouping is wanted (and
84 : // transportable ids are unique)
85 2580 : group = person->getID();
86 : } else {
87 : auto it2 = myRunningReservations.find(group);
88 266 : if (it2 != myRunningReservations.end()) {
89 62 : for (auto item : it2->second) {
90 : Reservation* res = const_cast<Reservation*>(item.first);
91 : if (res->persons.count(person) == 0
92 60 : && res->from == from
93 60 : && res->to == to
94 60 : && res->fromPos == fromPos
95 60 : && res->toPos == toPos) {
96 : MSDevice_Taxi* taxi = item.second;
97 : if (taxi->getState() == taxi->PICKUP
98 58 : && remainingCapacity(taxi, res) > 0
99 118 : && taxi->compatibleLine(taxi->getHolder().getParameter().line, line)) {
100 : //std::cout << SIMTIME << " addPerson=" << person->getID() << " extendRes=" << toString(res->persons) << " taxi=" << taxi->getHolder().getID() << " state=" << taxi->getState() << "\n";
101 : res->persons.insert(person);
102 58 : taxi->addCustomer(person, res);
103 : return res;
104 : }
105 : }
106 : }
107 : }
108 : }
109 : Reservation* result = nullptr;
110 : bool added = false;
111 : auto it = myGroupReservations.find(group);
112 2788 : if (it != myGroupReservations.end()) {
113 : // try to add to existing reservation
114 141 : for (Reservation* res : it->second) {
115 : if (res->persons.count(person) == 0
116 129 : && res->from == from
117 129 : && res->to == to
118 129 : && res->fromPos == fromPos
119 129 : && res->toPos == toPos) {
120 129 : if (res->persons.size() > 0 && (*res->persons.begin())->isPerson() != person->isPerson()) {
121 0 : WRITE_WARNINGF(TL("Mixing reservations of persons and containers with the same group is not supported for % and %"),
122 : (*res->persons.begin())->getID(), person->getID());
123 : }
124 252 : if ((person->isPerson() && (int)res->persons.size() >= maxCapacity) ||
125 141 : (!person->isPerson() && (int)res->persons.size() >= maxContainerCapacity)) {
126 : // split group to ensure that at least one taxi is capable of delivering group size.
127 12 : continue;
128 : }
129 : res->persons.insert(person);
130 : result = res;
131 : added = true;
132 117 : break;
133 : }
134 : }
135 : }
136 2788 : if (!added) {
137 2671 : Reservation* newRes = new Reservation(toString(myReservationCount++), {person}, reservationTime, pickupTime, earliestPickupTime, from, fromPos, fromStop, to, toPos, toStop, group, line);
138 2671 : myGroupReservations[group].push_back(newRes);
139 : result = newRes;
140 : }
141 2788 : myHasServableReservations = true;
142 : #ifdef DEBUG_RESERVATION
143 : if (DEBUG_COND2(person)) std::cout << SIMTIME
144 : << " addReservation p=" << person->getID()
145 : << " rT=" << time2string(reservationTime)
146 : << " pT=" << time2string(pickupTime)
147 : << " from=" << from->getID() << " fromPos=" << fromPos
148 : << " to=" << to->getID() << " toPos=" << toPos
149 : << " group=" << group
150 : << " added=" << added
151 : << "\n";
152 : #endif
153 2788 : return result;
154 : }
155 :
156 :
157 : std::string
158 87 : MSDispatch::removeReservation(MSTransportable* person,
159 : const MSEdge* from, double fromPos,
160 : const MSEdge* to, double toPos,
161 : std::string group) {
162 87 : if (group == "") {
163 : // the default empty group implies, no grouping is wanted (and
164 : // transportable ids are unique)
165 77 : group = person->getID();
166 : }
167 87 : std::string removedID = "";
168 : auto it = myGroupReservations.find(group);
169 87 : if (it != myGroupReservations.end()) {
170 77 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
171 77 : Reservation* res = *itRes;
172 : if (res->persons.count(person) != 0
173 77 : && res->from == from
174 77 : && res->to == to
175 77 : && res->fromPos == fromPos
176 77 : && res->toPos == toPos) {
177 : res->persons.erase(person);
178 77 : if (res->persons.empty()) {
179 77 : removedID = res->id;
180 77 : it->second.erase(itRes);
181 : // cleans up MSDispatch_Greedy
182 77 : fulfilledReservation(res);
183 77 : if (it->second.empty()) {
184 : myGroupReservations.erase(it);
185 : }
186 : }
187 : break;
188 : }
189 : }
190 : } else {
191 : auto it2 = myRunningReservations.find(group);
192 10 : if (it2 != myRunningReservations.end()) {
193 10 : for (auto item : it2->second) {
194 : const Reservation* res = item.first;
195 : if (res->persons.count(person) != 0
196 10 : && res->from == from
197 10 : && res->to == to
198 10 : && res->fromPos == fromPos
199 10 : && res->toPos == toPos) {
200 : MSDevice_Taxi* taxi = item.second;
201 10 : taxi->cancelCustomer(person);
202 10 : if (res->persons.empty()) {
203 0 : removedID = res->id;
204 : }
205 : break;
206 : }
207 : }
208 : }
209 : }
210 87 : myHasServableReservations = myGroupReservations.size() > 0;
211 : #ifdef DEBUG_RESERVATION
212 : if (DEBUG_COND2(person)) std::cout << SIMTIME
213 : << " removeReservation p=" << person->getID()
214 : << " from=" << from->getID() << " fromPos=" << fromPos
215 : << " to=" << to->getID() << " toPos=" << toPos
216 : << " group=" << group
217 : << " removedID=" << removedID
218 : << " hasServable=" << myHasServableReservations
219 : << "\n";
220 : #endif
221 87 : return removedID;
222 : }
223 :
224 :
225 : Reservation*
226 150 : MSDispatch::updateReservationFromPos(MSTransportable* person,
227 : const MSEdge* from, double fromPos,
228 : const MSEdge* to, double toPos,
229 : std::string group, double newFromPos) {
230 150 : if (group == "") {
231 : // the default empty group implies, no grouping is wanted (and
232 : // transportable ids are unique)
233 : group = person->getID();
234 : }
235 : Reservation* result = nullptr;
236 150 : std::string updatedID = "";
237 : auto it = myGroupReservations.find(group);
238 150 : if (it != myGroupReservations.end()) {
239 66 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
240 66 : Reservation* res = *itRes;
241 : // TODO: if there is already a reservation with the newFromPos, add to this reservation
242 : // TODO: if there are other persons in this reservation, create a new reservation for the updated one
243 : if (res->persons.count(person) != 0
244 66 : && res->from == from
245 66 : && res->to == to
246 66 : && res->fromPos == fromPos
247 66 : && res->toPos == toPos) {
248 : // update fromPos
249 66 : res->fromPos = newFromPos;
250 : result = res;
251 66 : updatedID = res->id;
252 : break;
253 : }
254 : }
255 : }
256 : #ifdef DEBUG_RESERVATION
257 : if (DEBUG_COND2(person)) std::cout << SIMTIME
258 : << " updateReservationFromPos p=" << person->getID()
259 : << " from=" << from->getID() << " fromPos=" << fromPos
260 : << " to=" << to->getID() << " toPos=" << toPos
261 : << " group=" << group
262 : << " newFromPos=" << newFromPos
263 : << " updatedID=" << updatedID
264 : << "\n";
265 : #endif
266 150 : return result;
267 : }
268 :
269 :
270 : std::vector<Reservation*>
271 19538 : MSDispatch::getReservations() {
272 : std::vector<Reservation*> reservations;
273 38892 : for (const auto& it : myGroupReservations) {
274 19354 : reservations.insert(reservations.end(), it.second.begin(), it.second.end());
275 : }
276 19538 : return reservations;
277 0 : }
278 :
279 :
280 : std::vector<const Reservation*>
281 4214 : MSDispatch::getRunningReservations() {
282 : std::vector<const Reservation*> result;
283 9551 : for (auto item : myRunningReservations) {
284 10674 : for (auto item2 : item.second) {
285 5337 : result.push_back(item2.first);
286 : }
287 : }
288 4214 : return result;
289 0 : }
290 :
291 :
292 : void
293 2348 : MSDispatch::servedReservation(const Reservation* res, MSDevice_Taxi* taxi) {
294 2348 : auto itR = myRunningReservations.find(res->group);
295 2348 : if (itR != myRunningReservations.end() && itR->second.count(res) != 0) {
296 : return; // was redispatch
297 : }
298 2224 : auto it = myGroupReservations.find(res->group);
299 2224 : if (it == myGroupReservations.end()) {
300 0 : throw ProcessError(TL("Inconsistent group reservations."));
301 : }
302 2224 : auto it2 = std::find(it->second.begin(), it->second.end(), res);
303 2224 : if (it2 == it->second.end()) {
304 0 : throw ProcessError(TL("Inconsistent group reservations (2)."));
305 : }
306 2224 : myRunningReservations[res->group][res] = taxi;
307 2224 : const_cast<Reservation*>(*it2)->state = Reservation::ASSIGNED;
308 2224 : it->second.erase(it2);
309 2224 : if (it->second.empty()) {
310 : myGroupReservations.erase(it);
311 : }
312 : }
313 :
314 :
315 : void
316 4 : MSDispatch::swappedRunning(const Reservation* res, MSDevice_Taxi* taxi) {
317 4 : myRunningReservations[res->group][res] = taxi;
318 4 : }
319 :
320 :
321 : void
322 2272 : MSDispatch::fulfilledReservation(const Reservation* res) {
323 2272 : myRunningReservations[res->group].erase(res);
324 2272 : if (myRunningReservations[res->group].empty()) {
325 : myRunningReservations.erase(res->group);
326 : }
327 2272 : delete res;
328 2272 : }
329 :
330 :
331 : SUMOAbstractRouter<MSEdge, SUMOVehicle>&
332 14325 : MSDispatch::getRouter() const {
333 28650 : return myRoutingMode == 1 ? MSRoutingEngine::getRouterTT(0, SVC_TAXI) : MSNet::getInstance()->getRouterTT(0);
334 : }
335 :
336 :
337 : SUMOTime
338 3495 : MSDispatch::computePickupTime(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
339 : ConstMSEdgeVector edges;
340 3495 : double fromPos = taxi->getHolder().getPositionOnLane() - NUMERICAL_EPS;
341 3495 : const MSEdge* from = *taxi->getHolder().getRerouteOrigin();
342 3495 : const bool originDiffers = from != taxi->getHolder().getEdge();
343 6957 : router.compute(from, originDiffers ? 0 : fromPos, res.from, res.fromPos, &taxi->getHolder(), t, edges, true);
344 3495 : if (edges.empty()) {
345 : return SUMOTime_MAX;
346 : } else {
347 2587 : if (originDiffers) {
348 : assert(from = *(taxi->getHolder().getCurrentRouteEdge() + 1));
349 33 : edges.insert(edges.begin(), taxi->getHolder().getEdge());
350 : }
351 2587 : return TIME2STEPS(router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, res.fromPos, t));
352 : }
353 3495 : }
354 :
355 :
356 : bool
357 3099 : MSDispatch::isReachable(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
358 : ConstMSEdgeVector edges;
359 3099 : router.compute(res.from, res.fromPos, res.to, res.toPos, &taxi->getHolder(), t, edges, true);
360 3099 : return !edges.empty();
361 3099 : }
362 :
363 :
364 : double
365 440 : MSDispatch::computeDetourTime(SUMOTime t, SUMOTime viaTime, const MSDevice_Taxi* taxi,
366 : const MSEdge* from, double fromPos,
367 : const MSEdge* via, double viaPos,
368 : const MSEdge* to, double toPos,
369 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router,
370 : double& timeDirect) {
371 : ConstMSEdgeVector edges;
372 440 : if (timeDirect < 0) {
373 384 : router.compute(from, fromPos, to, toPos, &taxi->getHolder(), t, edges, true);
374 384 : timeDirect = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, toPos, t);
375 : edges.clear();
376 : }
377 :
378 440 : router.compute(from, fromPos, via, viaPos, &taxi->getHolder(), t, edges, true);
379 440 : const double start = STEPS2TIME(t);
380 440 : const double leg1 = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, viaPos, t);
381 : #ifdef DEBUG_DETOUR
382 : std::cout << " leg1=" << toString(edges) << " startPos=" << fromPos << " toPos=" << viaPos << " time=" << leg1 << "\n";
383 : #endif
384 440 : const double wait = MAX2(0.0, STEPS2TIME(viaTime) - (start + leg1));
385 : edges.clear();
386 440 : const SUMOTime timeContinue = TIME2STEPS(start + leg1 + wait);
387 440 : router.compute(via, viaPos, to, toPos, &taxi->getHolder(), timeContinue, edges, true);
388 440 : const double leg2 = router.recomputeCostsPos(edges, &taxi->getHolder(), viaPos, toPos, timeContinue);
389 440 : const double timeDetour = leg1 + wait + leg2;
390 : #ifdef DEBUG_DETOUR
391 : std::cout << " leg2=" << toString(edges) << " startPos=" << viaPos << " toPos=" << toPos << " time=" << leg2 << "\n";
392 : std::cout << " t=" << STEPS2TIME(t) << " vt=" << STEPS2TIME(viaTime)
393 : << " from=" << from->getID() << " to=" << to->getID() << " via=" << via->getID()
394 : << " direct=" << timeDirect << " detour=" << timeDetour << " wait=" << wait << "\n";
395 : #endif
396 440 : return timeDetour;
397 440 : }
398 :
399 :
400 : int
401 4002 : MSDispatch::remainingCapacity(const MSDevice_Taxi* taxi, const Reservation* res) {
402 : assert(res->persons.size() > 0);
403 4002 : return ((*res->persons.begin())->isPerson()
404 4002 : ? taxi->getHolder().getVehicleType().getPersonCapacity()
405 192 : : taxi->getHolder().getVehicleType().getContainerCapacity()) - (int)res->persons.size();
406 : }
407 :
408 :
409 : /****************************************************************************/
|
