Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-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 MSDispatch_Greedy.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/transportables/MSTransportable.h>
26 : #include "MSRoutingEngine.h"
27 : #include "MSDispatch_GreedyShared.h"
28 :
29 : //#define DEBUG_DISPATCH
30 : //#define DEBUG_SERVABLE
31 : //#define DEBUG_TRAVELTIME
32 : //#define DEBUG_COND2(obj) (obj->getID() == "p0")
33 : #define DEBUG_COND2(obj) (true)
34 :
35 : // ===========================================================================
36 : // MSDispatch_Greedy methods
37 : // ===========================================================================
38 :
39 : void
40 12126 : MSDispatch_Greedy::computeDispatch(SUMOTime now, const std::vector<MSDevice_Taxi*>& fleet) {
41 : int numDispatched = 0;
42 : int numPostponed = 0;
43 : // find available vehicles
44 : std::set<MSDevice_Taxi*, MSVehicleDevice::ComparatorNumericalVehicleIdLess> available;
45 31293 : for (auto* taxi : fleet) {
46 19167 : if (taxi->isEmpty()) {
47 : available.insert(taxi);
48 : }
49 : }
50 : // greedy assign closest vehicle in reservation order
51 12128 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router = myRoutingMode == 1 ? MSRoutingEngine::getRouterTT(0, SVC_TAXI) : MSNet::getInstance()->getRouterTT(0);
52 12126 : std::vector<Reservation*> reservations = getReservations();
53 12126 : std::sort(reservations.begin(), reservations.end(), time_sorter());
54 : #ifdef DEBUG_DISPATCH
55 : std::cout << SIMTIME << " computeDispatch fleet=" << fleet.size() << " available=" << available.size() << " reservations=" << toString(reservations) << "\n";
56 : #endif
57 13946 : for (auto it = reservations.begin(); it != reservations.end();) {
58 3151 : if (available.size() == 0) {
59 : break;
60 : }
61 1822 : Reservation* res = *it;
62 1822 : if (res->recheck > now) {
63 : it++;
64 0 : numPostponed++;
65 0 : continue;
66 : }
67 : //Position pos = res.from->getLanes().front()->geometryPositionAtOffset(res.fromPos);
68 1822 : MSDevice_Taxi* closest = nullptr;
69 : SUMOTime closestTime = SUMOTime_MAX;
70 : bool tooEarly = false;
71 : bool unreachable = false;
72 : bool unreachableDest = false;
73 4263 : for (auto* taxi : available) {
74 2441 : if (remainingCapacity(taxi, res) < 0 || !taxi->compatibleLine(res)) {
75 68 : continue;
76 : }
77 2373 : SUMOTime travelTime = computePickupTime(now, taxi, *res, router);
78 2373 : const bool destConnected = isReachable(now, taxi, *res, router);
79 : #ifdef DEBUG_TRAVELTIME
80 : if (DEBUG_COND2(person)) {
81 : std::cout << SIMTIME << " taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons) << " traveltime=" << time2string(travelTime) << " reachable=" << reachable << "\n";
82 : }
83 : #endif
84 2373 : if (travelTime < closestTime && destConnected) {
85 : closestTime = travelTime;
86 1356 : closest = taxi;
87 1356 : SUMOTime taxiWait = res->pickupTime - (now + closestTime);
88 1356 : if (taxiWait > myMaximumWaitingTime) {
89 : // no need to service this customer now
90 : tooEarly = true;
91 0 : res->recheck += MAX2(now + myRecheckTime, res->pickupTime - closestTime - myRecheckSafety);
92 : break;
93 : }
94 1017 : } else if (travelTime == SUMOTime_MAX) {
95 : unreachable = true;
96 109 : } else if (!destConnected) {
97 : unreachableDest = true;
98 : }
99 : }
100 1822 : if (tooEarly || closest == nullptr) {
101 : // too early or all taxis are too small
102 654 : SUMOTime resWait = now - res->pickupTime;
103 654 : if ((unreachable || unreachableDest) && resWait > myKeepUnreachableResTime) {
104 10 : it = reservations.erase(it);
105 10 : if (unreachable) {
106 30 : WRITE_WARNINGF("Aborting reservation for customers '%' from '%' after waiting time % because no taxi can reach the pickup location, time=%.",
107 : toString(res->persons), res->from->getID(), time2string(resWait), time2string(SIMSTEP));
108 : } else {
109 0 : WRITE_WARNINGF("Aborting reservation for customers '%' to '%' after waiting time % because no taxi can reach the dropoff location, time=%.",
110 : toString(res->persons), res->from->getID(), time2string(resWait), time2string(SIMSTEP));
111 : }
112 : std::set<const MSTransportable*> persons = res->persons;
113 20 : for (const MSTransportable* p : persons) {
114 30 : removeReservation(const_cast<MSTransportable*>(p), res->from, res->fromPos, res->to, res->toPos, res->group);
115 : }
116 10 : } else {
117 : it++;
118 644 : numPostponed++;
119 : }
120 : } else {
121 1168 : numDispatched += dispatch(closest, it, router, reservations);
122 : available.erase(closest);
123 : }
124 : }
125 : // check if any taxis are able to service the remaining requests
126 12124 : myHasServableReservations = reservations.size() > 0 && (available.size() < fleet.size() || numPostponed > 0 || numDispatched > 0);
127 : #ifdef DEBUG_SERVABLE
128 : std::cout << SIMTIME << " reservations=" << reservations.size() << " avail=" << available.size()
129 : << " fleet=" << fleet.size() << " postponed=" << numPostponed << " dispatched=" << numDispatched << "\n";
130 : #endif
131 24250 : }
132 :
133 :
134 : int
135 923 : MSDispatch_Greedy::dispatch(MSDevice_Taxi* taxi, std::vector<Reservation*>::iterator& resIt, SUMOAbstractRouter<MSEdge, SUMOVehicle>& /*router*/, std::vector<Reservation*>& reservations) {
136 : #ifdef DEBUG_DISPATCH
137 : if (DEBUG_COND2(person)) {
138 : std::cout << SIMTIME << " dispatch taxi=" << taxi->getHolder().getID() << " person=" << toString((*resIt)->persons) << "\n";
139 : }
140 : #endif
141 923 : taxi->dispatch(**resIt);
142 921 : servedReservation(*resIt, taxi); // deleting res
143 921 : resIt = reservations.erase(resIt);
144 921 : return 1;
145 : }
146 :
147 :
148 : // ===========================================================================
149 : // MSDispatch_GreedyClosest methods
150 : // ===========================================================================
151 :
152 : void
153 196 : MSDispatch_GreedyClosest::computeDispatch(SUMOTime now, const std::vector<MSDevice_Taxi*>& fleet) {
154 : bool havePostponed = false;
155 : int numDispatched = 0;
156 : // find available vehicles
157 : std::set<MSDevice_Taxi*, MSVehicleDevice::ComparatorNumericalVehicleIdLess> available;
158 576 : for (auto* taxi : fleet) {
159 380 : if (taxi->isEmpty()) {
160 : available.insert(taxi);
161 : }
162 : }
163 : #ifdef DEBUG_DISPATCH
164 : std::cout << SIMTIME << " computeDispatch fleet=" << fleet.size() << " available=" << available.size() << "\n";
165 : #endif
166 : // greedy assign closest vehicle
167 392 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router = myRoutingMode == 1 ? MSRoutingEngine::getRouterTT(0, SVC_TAXI) : MSNet::getInstance()->getRouterTT(0);
168 : std::vector<Reservation*> activeReservations;
169 636 : for (Reservation* res : getReservations()) {
170 440 : if (res->recheck <= now) {
171 440 : activeReservations.push_back(res);
172 : }
173 196 : }
174 274 : while (available.size() > 0 && activeReservations.size() > 0) {
175 112 : Reservation* closest = nullptr;
176 112 : MSDevice_Taxi* closestTaxi = nullptr;
177 : SUMOTime closestTime = SUMOTime_MAX;
178 428 : for (Reservation* res : activeReservations) {
179 : SUMOTime recheck = SUMOTime_MAX;
180 734 : for (auto* taxi : available) {
181 418 : if (remainingCapacity(taxi, res) < 0 || !taxi->compatibleLine(res)) {
182 58 : continue;
183 : }
184 360 : SUMOTime travelTime = computePickupTime(now, taxi, *res, router);
185 360 : SUMOTime taxiWait = res->pickupTime - (now + travelTime);
186 : #ifdef DEBUG_TRAVELTIME
187 : if (DEBUG_COND2(person)) std::cout << SIMTIME << " taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons)
188 : << " traveltime=" << time2string(travelTime)
189 : << " pickupTime=" << time2string(res->pickupTime)
190 : << " taxiWait=" << time2string(taxiWait) << "\n";
191 : #endif
192 360 : if (travelTime < closestTime) {
193 128 : if (taxiWait < myMaximumWaitingTime) {
194 : closestTime = travelTime;
195 128 : closest = res;
196 128 : closestTaxi = taxi;
197 : #ifdef DEBUG_DISPATCH
198 : if (DEBUG_COND2(person)) std::cout << SIMTIME << " bestTaxi=" << taxi->getHolder().getID() << " bestRes=" << toString(res->persons)
199 : << " taxiPos=" << taxi->getHolder().getPositionOnLane() << " resFromPos=" << res->fromPos << " traveltime=" << time2string(travelTime) << " taxiWait=" << time2string(taxiWait) << "\n";
200 : #endif
201 : } else {
202 : recheck = MIN2(recheck,
203 : MAX2(now + myRecheckTime, res->pickupTime - closestTime - myRecheckSafety));
204 : }
205 : }
206 : }
207 : /*
208 : if (closestTaxi == nullptr) {
209 : // all taxis would arrive to early. postpone recheck
210 : res.recheck = recheck;
211 : }
212 : */
213 : }
214 112 : if (closestTaxi != nullptr) {
215 78 : auto closeIt = std::find(activeReservations.begin(), activeReservations.end(), closest);
216 78 : numDispatched += dispatch(closestTaxi, closeIt, router, activeReservations);
217 : available.erase(closestTaxi);
218 : } else {
219 : // all current reservations are too early or too big
220 : havePostponed = true;
221 34 : break;
222 : }
223 : }
224 : // check if any taxis are able to service the remaining requests
225 196 : myHasServableReservations = getReservations().size() > 0 && (available.size() < fleet.size() || havePostponed || numDispatched > 0);
226 : #ifdef DEBUG_SERVABLE
227 : std::cout << SIMTIME << " reservations=" << getReservations().size() << " avail=" << available.size()
228 : << " fleet=" << fleet.size() << " postponed=" << havePostponed << " dispatched=" << numDispatched << "\n";
229 : #endif
230 392 : }
231 :
232 :
233 : /****************************************************************************/
|
