Eclipse SUMO - Simulation of Urban MObility
MSDispatch_Greedy.cpp
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2007-2020 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 /****************************************************************************/
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>
26 #include "MSRoutingEngine.h"
28 
29 //#define DEBUG_RESERVATION
30 //#define DEBUG_DISPATCH
31 //#define DEBUG_SERVABLE
32 //#define DEBUG_TRAVELTIME
33 //#define DEBUG_DETOUR
34 //#define DEBUG_COND2(obj) (obj->getID() == "p0")
35 #define DEBUG_COND2(obj) (true)
36 
37 // ===========================================================================
38 // MSDispatch_Greedy methods
39 // ===========================================================================
40 
41 void
42 MSDispatch_Greedy::computeDispatch(SUMOTime now, const std::vector<MSDevice_Taxi*>& fleet) {
43  int numDispatched = 0;
44  int numPostponed = 0;
45  // find available vehicles
46  std::set<MSDevice_Taxi*, MSVehicleDevice::ComparatorNumericalVehicleIdLess> available;
47  for (auto* taxi : fleet) {
48  if (taxi->isEmpty()) {
49  available.insert(taxi);
50  }
51  }
52  // greedy assign closest vehicle in reservation order
54  std::vector<Reservation*> reservations = getReservations();
55  std::sort(reservations.begin(), reservations.end(), time_sorter());
56 #ifdef DEBUG_DISPATCH
57  std::cout << SIMTIME << " computeDispatch fleet=" << fleet.size() << " available=" << available.size() << " reservations=" << toString(reservations) << "\n";
58 #endif
59  for (auto it = reservations.begin(); it != reservations.end();) {
60  if (available.size() == 0) {
61  break;
62  }
63  Reservation* res = *it;
64  if (res->recheck > now) {
65  it++;
66  numPostponed++;
67  continue;
68  }
69  //Position pos = res.from->getLanes().front()->geometryPositionAtOffset(res.fromPos);
70  MSDevice_Taxi* closest = nullptr;
71  SUMOTime closestTime = SUMOTime_MAX;
72  bool tooEarly = false;
73  for (auto* taxi : available) {
74  if (taxi->getHolder().getVehicleType().getPersonCapacity() < (int)res->persons.size()) {
75  continue;
76  }
77  SUMOTime travelTime = computePickupTime(now, taxi, *res, router);
78 #ifdef DEBUG_TRAVELTIME
79  if (DEBUG_COND2(person)) {
80  std::cout << SIMTIME << " taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons) << " traveltime=" << time2string(travelTime) << "\n";
81  }
82 #endif
83  if (travelTime < closestTime) {
84  closestTime = travelTime;
85  closest = taxi;
86  SUMOTime taxiWait = res->pickupTime - (now + closestTime);
87  if (taxiWait > myMaximumWaitingTime) {
88  // no need to service this customer now
89  tooEarly = true;
90  res->recheck += MAX2(now + myRecheckTime, res->pickupTime - closestTime - myRecheckSafety);
91  break;
92  }
93  }
94  }
95  if (tooEarly || closest == nullptr) {
96  // too early or all taxis are too small
97  it++;
98  numPostponed++;
99  } else {
100  numDispatched += dispatch(closest, it, router, reservations);
101  available.erase(closest);
102  }
103  }
104  // check if any taxis are able to service the remaining requests
105  myHasServableReservations = reservations.size() > 0 && (available.size() < fleet.size() || numPostponed > 0 || numDispatched > 0);
106 #ifdef DEBUG_SERVABLE
107  std::cout << SIMTIME << " reservations=" << reservations.size() << " avail=" << available.size()
108  << " fleet=" << fleet.size() << " postponed=" << numPostponed << " dispatched=" << numDispatched << "\n";
109 #endif
110 }
111 
112 
113 int
114 MSDispatch_Greedy::dispatch(MSDevice_Taxi* taxi, std::vector<Reservation*>::iterator& resIt, SUMOAbstractRouter<MSEdge, SUMOVehicle>& /*router*/, std::vector<Reservation*>& reservations) {
115 #ifdef DEBUG_DISPATCH
116  if (DEBUG_COND2(person)) {
117  std::cout << SIMTIME << " dispatch taxi=" << taxi->getHolder().getID() << " person=" << toString((*resIt)->persons) << "\n";
118  }
119 #endif
120  taxi->dispatch(**resIt);
121  servedReservation(*resIt); // deleting res
122  resIt = reservations.erase(resIt);
123  return 1;
124 }
125 
126 
127 // ===========================================================================
128 // MSDispatch_GreedyClosest methods
129 // ===========================================================================
130 
131 void
132 MSDispatch_GreedyClosest::computeDispatch(SUMOTime now, const std::vector<MSDevice_Taxi*>& fleet) {
133  bool havePostponed = false;
134  int numDispatched = 0;
135  // find available vehicles
136  std::set<MSDevice_Taxi*, MSVehicleDevice::ComparatorNumericalVehicleIdLess> available;
137  for (auto* taxi : fleet) {
138  if (taxi->isEmpty()) {
139  available.insert(taxi);
140  }
141  }
142 #ifdef DEBUG_DISPATCH
143  std::cout << SIMTIME << " computeDispatch fleet=" << fleet.size() << " available=" << available.size() << "\n";
144 #endif
145  // greedy assign closest vehicle
147  std::vector<Reservation*> activeReservations;
148  for (Reservation* res : getReservations()) {
149  if (res->recheck <= now) {
150  activeReservations.push_back(res);
151  }
152  }
153  while (available.size() > 0 && activeReservations.size() > 0) {
154  Reservation* closest = nullptr;
155  MSDevice_Taxi* closestTaxi = nullptr;
156  SUMOTime closestTime = SUMOTime_MAX;
157  for (Reservation* res : activeReservations) {
158  SUMOTime recheck = SUMOTime_MAX;
159  for (auto* taxi : available) {
160  if (taxi->getHolder().getVehicleType().getPersonCapacity() < (int)res->persons.size()) {
161  continue;
162  }
163  SUMOTime travelTime = computePickupTime(now, taxi, *res, router);
164  SUMOTime taxiWait = res->pickupTime - (now + travelTime);
165 #ifdef DEBUG_TRAVELTIME
166  if (DEBUG_COND2(person)) std::cout << SIMTIME << " taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons)
167  << " traveltime=" << time2string(travelTime)
168  << " pickupTime=" << time2string(res->pickupTime)
169  << " taxiWait=" << time2string(taxiWait) << "\n";
170 #endif
171  if (travelTime < closestTime) {
172  if (taxiWait < myMaximumWaitingTime) {
173  closestTime = travelTime;
174  closest = res;
175  closestTaxi = taxi;
176  } else {
177  recheck = MIN2(recheck,
178  MAX2(now + myRecheckTime, res->pickupTime - closestTime - myRecheckSafety));
179  }
180  }
181  }
182  /*
183  if (closestTaxi == nullptr) {
184  // all taxis would arrive to early. postpone recheck
185  res.recheck = recheck;
186  }
187  */
188  }
189  if (closestTaxi != nullptr) {
190  auto closeIt = std::find(activeReservations.begin(), activeReservations.end(), closest);
191  numDispatched += dispatch(closestTaxi, closeIt, router, activeReservations);
192  available.erase(closestTaxi);
193  } else {
194  // all current reservations are too early or too big
195  havePostponed = true;
196  break;
197  }
198  }
199  // check if any taxis are able to service the remaining requests
200  myHasServableReservations = getReservations().size() > 0 && (available.size() < fleet.size() || havePostponed || numDispatched > 0);
201 #ifdef DEBUG_SERVABLE
202  std::cout << SIMTIME << " reservations=" << getReservations().size() << " avail=" << available.size()
203  << " fleet=" << fleet.size() << " postponed=" << havePostponed << " dispatched=" << numDispatched << "\n";
204 #endif
205 }
206 
207 
208 /****************************************************************************/
#define DEBUG_COND2(obj)
std::string time2string(SUMOTime t)
convert SUMOTime to string
Definition: SUMOTime.cpp:68
#define SUMOTime_MAX
Definition: SUMOTime.h:32
#define SIMTIME
Definition: SUMOTime.h:60
long long int SUMOTime
Definition: SUMOTime.h:31
@ SVC_TAXI
vehicle is a taxi
T MIN2(T a, T b)
Definition: StdDefs.h:73
T MAX2(T a, T b)
Definition: StdDefs.h:79
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:44
A device which collects info on the vehicle trip (mainly on departure and arrival)
Definition: MSDevice_Taxi.h:48
void dispatch(const Reservation &res)
service the given reservation
sorts reservations by time
Definition: MSDispatch.h:89
void computeDispatch(SUMOTime now, const std::vector< MSDevice_Taxi * > &fleet)
computes dispatch and updates reservations
const SUMOTime myRecheckTime
recheck interval for early reservations
virtual void computeDispatch(SUMOTime now, const std::vector< MSDevice_Taxi * > &fleet)
computes dispatch and updates reservations
const int myRoutingMode
which router/edge weights to use
virtual int dispatch(MSDevice_Taxi *taxi, std::vector< Reservation * >::iterator &resIt, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router, std::vector< Reservation * > &reservations)
trigger taxi dispatch.
const SUMOTime myRecheckSafety
const SUMOTime myMaximumWaitingTime
maximum time to arrive earlier at customer
static SUMOTime computePickupTime(SUMOTime t, const MSDevice_Taxi *taxi, const Reservation &res, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router)
compute time to pick up the given reservation
Definition: MSDispatch.cpp:139
bool myHasServableReservations
whether the last call to computeDispatch has left servable reservations
Definition: MSDispatch.h:139
std::vector< Reservation * > getReservations()
retrieve all reservations
Definition: MSDispatch.cpp:111
void servedReservation(const Reservation *res)
Definition: MSDispatch.cpp:121
static MSNet * getInstance()
Returns the pointer to the unique instance of MSNet (singleton).
Definition: MSNet.cpp:171
SUMOAbstractRouter< MSEdge, SUMOVehicle > & getRouterTT(const int rngIndex, const MSEdgeVector &prohibited=MSEdgeVector()) const
Definition: MSNet.cpp:1199
static SUMOAbstractRouter< MSEdge, SUMOVehicle > & getRouterTT(const int rngIndex, SUMOVehicleClass svc, const MSEdgeVector &prohibited=MSEdgeVector())
return the router instance
SUMOVehicle & getHolder() const
Returns the vehicle that holds this device.
const std::string & getID() const
Returns the id.
Definition: Named.h:73
SUMOTime pickupTime
Definition: MSDispatch.h:58
SUMOTime recheck
Definition: MSDispatch.h:64
std::set< MSTransportable * > persons
Definition: MSDispatch.h:56