Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-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 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 6244 : 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 14245 : for (auto* taxi : fleet) {
46 8001 : if (taxi->isEmpty()) {
47 : available.insert(taxi);
48 : }
49 : }
50 : // greedy assign closest vehicle in reservation order
51 6246 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router = myRoutingMode == 1 ? MSRoutingEngine::getRouterTT(0, SVC_TAXI) : MSNet::getInstance()->getRouterTT(0);
52 6244 : std::vector<Reservation*> reservations = getReservations();
53 6244 : 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 7290 : for (auto it = reservations.begin(); it != reservations.end();) {
58 2119 : if (available.size() == 0) {
59 : break;
60 : }
61 1048 : Reservation* res = *it;
62 1048 : if (res->recheck > now) {
63 : it++;
64 0 : numPostponed++;
65 0 : continue;
66 : }
67 : //Position pos = res.from->getLanes().front()->geometryPositionAtOffset(res.fromPos);
68 1048 : MSDevice_Taxi* closest = nullptr;
69 : SUMOTime closestTime = SUMOTime_MAX;
70 : bool tooEarly = false;
71 2407 : for (auto* taxi : available) {
72 1359 : if (remainingCapacity(taxi, res) < 0 || !taxi->compatibleLine(res)) {
73 68 : continue;
74 : }
75 1291 : SUMOTime travelTime = computePickupTime(now, taxi, *res, router);
76 : #ifdef DEBUG_TRAVELTIME
77 : if (DEBUG_COND2(person)) {
78 : std::cout << SIMTIME << " taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons) << " traveltime=" << time2string(travelTime) << "\n";
79 : }
80 : #endif
81 1291 : if (travelTime < closestTime) {
82 : closestTime = travelTime;
83 1196 : closest = taxi;
84 1196 : SUMOTime taxiWait = res->pickupTime - (now + closestTime);
85 1196 : if (taxiWait > myMaximumWaitingTime) {
86 : // no need to service this customer now
87 : tooEarly = true;
88 0 : res->recheck += MAX2(now + myRecheckTime, res->pickupTime - closestTime - myRecheckSafety);
89 : break;
90 : }
91 : }
92 : }
93 1048 : if (tooEarly || closest == nullptr) {
94 : // too early or all taxis are too small
95 : it++;
96 38 : numPostponed++;
97 : } else {
98 1010 : numDispatched += dispatch(closest, it, router, reservations);
99 : available.erase(closest);
100 : }
101 : }
102 : // check if any taxis are able to service the remaining requests
103 6242 : myHasServableReservations = reservations.size() > 0 && (available.size() < fleet.size() || numPostponed > 0 || numDispatched > 0);
104 : #ifdef DEBUG_SERVABLE
105 : std::cout << SIMTIME << " reservations=" << reservations.size() << " avail=" << available.size()
106 : << " fleet=" << fleet.size() << " postponed=" << numPostponed << " dispatched=" << numDispatched << "\n";
107 : #endif
108 12486 : }
109 :
110 :
111 : int
112 819 : MSDispatch_Greedy::dispatch(MSDevice_Taxi* taxi, std::vector<Reservation*>::iterator& resIt, SUMOAbstractRouter<MSEdge, SUMOVehicle>& /*router*/, std::vector<Reservation*>& reservations) {
113 : #ifdef DEBUG_DISPATCH
114 : if (DEBUG_COND2(person)) {
115 : std::cout << SIMTIME << " dispatch taxi=" << taxi->getHolder().getID() << " person=" << toString((*resIt)->persons) << "\n";
116 : }
117 : #endif
118 819 : taxi->dispatch(**resIt);
119 817 : servedReservation(*resIt); // deleting res
120 817 : resIt = reservations.erase(resIt);
121 817 : return 1;
122 : }
123 :
124 :
125 : // ===========================================================================
126 : // MSDispatch_GreedyClosest methods
127 : // ===========================================================================
128 :
129 : void
130 196 : MSDispatch_GreedyClosest::computeDispatch(SUMOTime now, const std::vector<MSDevice_Taxi*>& fleet) {
131 : bool havePostponed = false;
132 : int numDispatched = 0;
133 : // find available vehicles
134 : std::set<MSDevice_Taxi*, MSVehicleDevice::ComparatorNumericalVehicleIdLess> available;
135 576 : for (auto* taxi : fleet) {
136 380 : if (taxi->isEmpty()) {
137 : available.insert(taxi);
138 : }
139 : }
140 : #ifdef DEBUG_DISPATCH
141 : std::cout << SIMTIME << " computeDispatch fleet=" << fleet.size() << " available=" << available.size() << "\n";
142 : #endif
143 : // greedy assign closest vehicle
144 196 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router = myRoutingMode == 1 ? MSRoutingEngine::getRouterTT(0, SVC_TAXI) : MSNet::getInstance()->getRouterTT(0);
145 : std::vector<Reservation*> activeReservations;
146 636 : for (Reservation* res : getReservations()) {
147 440 : if (res->recheck <= now) {
148 440 : activeReservations.push_back(res);
149 : }
150 196 : }
151 274 : while (available.size() > 0 && activeReservations.size() > 0) {
152 112 : Reservation* closest = nullptr;
153 112 : MSDevice_Taxi* closestTaxi = nullptr;
154 : SUMOTime closestTime = SUMOTime_MAX;
155 428 : for (Reservation* res : activeReservations) {
156 : SUMOTime recheck = SUMOTime_MAX;
157 734 : for (auto* taxi : available) {
158 418 : if (remainingCapacity(taxi, res) < 0 || !taxi->compatibleLine(res)) {
159 58 : continue;
160 : }
161 360 : SUMOTime travelTime = computePickupTime(now, taxi, *res, router);
162 360 : SUMOTime taxiWait = res->pickupTime - (now + travelTime);
163 : #ifdef DEBUG_TRAVELTIME
164 : if (DEBUG_COND2(person)) std::cout << SIMTIME << " taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons)
165 : << " traveltime=" << time2string(travelTime)
166 : << " pickupTime=" << time2string(res->pickupTime)
167 : << " taxiWait=" << time2string(taxiWait) << "\n";
168 : #endif
169 360 : if (travelTime < closestTime) {
170 128 : if (taxiWait < myMaximumWaitingTime) {
171 : closestTime = travelTime;
172 128 : closest = res;
173 128 : closestTaxi = taxi;
174 : #ifdef DEBUG_DISPATCH
175 : if (DEBUG_COND2(person)) std::cout << SIMTIME << " bestTaxi=" << taxi->getHolder().getID() << " bestRes=" << toString(res->persons)
176 : << " taxiPos=" << taxi->getHolder().getPositionOnLane() << " resFromPos=" << res->fromPos << " traveltime=" << time2string(travelTime) << " taxiWait=" << time2string(taxiWait) << "\n";
177 : #endif
178 : } else {
179 : recheck = MIN2(recheck,
180 : MAX2(now + myRecheckTime, res->pickupTime - closestTime - myRecheckSafety));
181 : }
182 : }
183 : }
184 : /*
185 : if (closestTaxi == nullptr) {
186 : // all taxis would arrive to early. postpone recheck
187 : res.recheck = recheck;
188 : }
189 : */
190 : }
191 112 : if (closestTaxi != nullptr) {
192 78 : auto closeIt = std::find(activeReservations.begin(), activeReservations.end(), closest);
193 78 : numDispatched += dispatch(closestTaxi, closeIt, router, activeReservations);
194 : available.erase(closestTaxi);
195 : } else {
196 : // all current reservations are too early or too big
197 : havePostponed = true;
198 34 : break;
199 : }
200 : }
201 : // check if any taxis are able to service the remaining requests
202 196 : myHasServableReservations = getReservations().size() > 0 && (available.size() < fleet.size() || havePostponed || numDispatched > 0);
203 : #ifdef DEBUG_SERVABLE
204 : std::cout << SIMTIME << " reservations=" << getReservations().size() << " avail=" << available.size()
205 : << " fleet=" << fleet.size() << " postponed=" << havePostponed << " dispatched=" << numDispatched << "\n";
206 : #endif
207 392 : }
208 :
209 :
210 : /****************************************************************************/
|
