User's Guide: 3. Implementing your own Algorithm: centralized
Demand-responsive transport systems can be coordinated either by:
- some central authority (dispatcher),
- or by decentralized, self-interested decision making of individual drivers.
In this case, which we call centralized , all the thinking is done by a single dispatcher agent. He receives the requests from passengers, plans the whole trips for all the taxis, and sends the drivers on their way. In this case, drivers have no free will and do exactly what they are told by the dispatcher. This case is a realization of so-called Dial-a-Ride problem (DARP).
In order to implement your own centralized coordination algorithm (DARP alg.), you only need to modify one method processNewRequest(Request request) of the dispatcher logic class. In this tutorial, we'll explain the example implementation that is included in the testbed. Modifying this code is the easiest way to create your own algorithm.
First of all, open the DispatchingLogicExample class that can be found in the following package of CentralizedExample project:
cz.agents.agentpolis.darptestbed.simmodel.agent.dispatching.logic
There, you will find the processNewRequest(Request request) method that is called every time the dispatcher receives a new request from the passenger. This method is quite simplistic and inefficient, but sufficiently demonstrates how to integrate your own algorithms within the testbed. It does the following:
- upon receiving a request, we loop over all the free taxi drivers,
- check if a given driver has free capacity and all the required equipment (if needed),
- check if he can get to departure node in time from his current position,
- and if he can, we:
- plan the optimal trips for this driver and send them to him,
- and let the passenger know who he should wait for. Then we jump out of the loop.
Let us now explain the source code in detail and describe individual classes and methods used:
public void processNewRequest(Request request) {
// print out the request for debugging purposes
LOGGER.info("Request: ["
+ utils.toHoursAndMinutes(request.getTimeWindow().getEarliestDeparture()) + "] from "
+ request.getPassengerId() + ", latest departure: "
+ utils.toHoursAndMinutes(request.getTimeWindow().getLatestDeparture()));LOGGER.info() calls are currently used to display the debugging information in the console, using the log4j library. You can also use the debug(), warn(), error() or fatal() functions of the logger (you can adjust settings and verbosity of the logger in /log/log4j.xml).
In this case, we print certain information about received request (Request class).
Request class has the following set of methods, that can be used to access the most important information about it:
-
getPassengerId(): Returns the unique String id of a passenger that sent this request. -
getFromNode()andgetToNode(): Return the numeric identifiers of the nodes (places) from which and to which the passenger wants to travel. -
getTimeWindow(): Returns the TimeWindow object, containing the earliest and latest departure and arrival times. -
getAdditionalRequirements(): Returns the list of non-standard requirements that the passengers may have (e.g. "wheelchair support" or "child seat"). In a typical case, this is an empty list.
The TimeWindow class has four important functions on its own - getEarliestDeparture(), getLatestDeparture(), getEarliestArrival() and getLatestArrival(). They return corresponding times as a single long number. To convert these times into a human-readable String format, you can use the utils.toHoursAndMinutes() function of the Utils class.
The Utils class contains a collection of various miscellaneous methods. We will only discuss the ones that are used in this example algorithm. Feel free to explore the Utils class by yourself.
// check if there are any free taxi drivers
if (taxiModel.getTaxiDriversFree().size() == 0) {
// if there are no free drivers, dispatcher needs to reject the request
this.sendRequestReject(request.getPassengerId(),request);
LOGGER.debug("Reply: REJECT [no free taxis]");
return;
}Next, we check if there are some free taxi drivers. At any given moment, the taxi driver is either free (idle, waiting for orders) or busy (driving or waiting for passenger to get on board). The TestbedModel class, instantiated by a taxiModel object, keeps track of them for your convenience. The most useful functions provided by it are:
-
getAllTaxiDrivers()andgetTaxiDriversFree(): Return the list of String ids of all (or currently free) taxi drivers. -
getVehicleId(taxiDriverId): Returns the String id of a vehicle belonging to the driver with a given taxiDriverId. -
getNumOfPassenOnBoard(vehicleId): Returns the number of passengers that are currently on board of a vehicle with a given vehicleId. -
getEndOfTripPosition(taxiId): Returns the id of the node where a given taxi will finish its current trip.
If we discover that we have 0 free taxis, we send the request rejection to the passenger, using the sendRequestReject() function. Then we just print a debug message and don't do anything else.
// loop over all free taxi drivers
for (String taxiDriverId : taxiModel.getTaxiDriversFree()) {
// get the object representation of this driver's vehicle
TestbedVehicle taxiVehicle = vehicleStorage.getEntityById(taxiModel.getVehicleId(taxiDriverId));
// skip those taxi drivers, who have currently full capacity
if (taxiModel.getNumOfPassenOnBoard(taxiModel.getVehicleId(taxiDriverId))
>= taxiVehicle.getCapacity())
{
continue;
}
// skip those taxis, which don't meet some of the passenger's
// special requirements (wheel chair support, child seat, etc.)
if (!taxiVehicle.getVehicleEquipments().containsAll(request.getAdditionalRequirements())) {
continue;
}Now we can loop over all the free taxi drivers and skip those, who don't satisfy some basic conditions. First, we request a TestbedVehicle object representing the vehicle of this driver by calling the getEntityById() function of the vehicleStorage object (this object serves basically only this purpose).
To check the vehicle's capacity, we use the getCapacity() function. Other useful functions of the TestbedVehicle class are getId() and getVehicleEquipements() . We use this last one to check if the vehicle satisfies all the special requirements of the passenger.
// compute the driving time between the passenger and the driver
double timeToPassenger = utils.computeDrivingTime(taxiDriverId, request.getPassengerId());
// compute when this driver could pick up the passenger
long pickUpTime = utils.getCurrentTime() + (long) timeToPassenger;
// if this driver is able to pick up the passenger within his departure time window ...
if (pickUpTime <= request.getTimeWindow().getLatestDeparture()) {Next, we want to compute when this driver can get from his current position to the passenger. To do this, we call the computeDrivingTime() function of Utils class, which returns the amount of time needed for that trip and add this value to the current in-simulation timestamp obtained by the getCurrentTime() function. This gives us the estimation of the earliest time when the driver can pick the passenger up. If this estimated time is earlier than requested latest departure, it means that this driver is close enough to the passenger, and therefore suitable for the request. Note that the computeDrivingTime() function calls the pathfinding algorithm, so it can be a bit slow when called for long distances. Use it with caution.
// plan the trips (paths)
// (1) from driver to passenger's departure node and
// (2) from origin to arrival node
Trip toPassenger = utils.planTrip(taxiVehicle.getId(),
positionQuery.getCurrentPositionByNodeId(taxiDriverId),
request.getFromNode());
Trip toDestination = utils.planTrip(taxiVehicle.getId(),
request.getFromNode(), request.getToNode());Now that we know that this driver can get to the passenger in time, we need to plan the exact drive path for him. This drive path will consist of two trips - trip to the passenger and a trip from the passenger to his destination. We can get those two trips by calling the planTrip(vehicleId, originNodeId, destinationNodeId) function of the Utils class. The vehicleId parameter points to driver's vehicle and is needed for our pathfinding algorithm. Two remaining parameters correspond to origin and destination positions for this trip. To obtain the current position of our driver, we call the getCurrentPositionByNodeId() function of the positionQuery object. This object provides a series of functions used to localize various entities within the simulation.
// concatenate those two trips into a drivePath for the driver
Trips drivePath = new Trips();
if (toPassenger != null && toPassenger.numOfCurrentTripItems() > 0)
drivePath.addTrip(toPassenger);
if (toDestination != null && toDestination.numOfCurrentTripItems() > 0)
drivePath.addTrip(toDestination);
// if we didn't successfully find and concatenate two required trips, skip this driver
if (drivePath.numTrips() != 2) continue;Once we have these two trips, we verify each of them (they need to be != null and need to have at least one trip item) and add them one after another to driver's resulting drive path, represented by the Trips class (Trips class is a linked list of trips).
// create a pickup map for this path
// (tells driver where he should pick up which passengers)
Map pickUpAndDropOffMap = Maps.newHashMap();
pickUpAndDropOffMap.put(
request.getFromNode(),
new PassengersInAndOutPair(
new HashSet<>(Arrays.asList(request.getPassengerId())),
new HashSet()));
pickUpAndDropOffMap.put(
request.getToNode(),
new PassengersInAndOutPair(
new HashSet(),
new HashSet<>(Arrays.asList(request.getPassengerId()))));We now have the complete detailed drive path for the driver. However, before we can send him out, we need to tell him where he should pick up and drop off which passengers. For this, we need to construct a pickUpAndDropOffMap hashmap. It maps the trip nodes to PassengersInAndOutPair objects. Each PassengersInAndOutPair merely specifies the set of passengers that need to be picked up and another set of passengers that need to be dropped off on one specific node. In this example case we only transport one passenger at a time, so the PassengersIndAndOutPair object will always contain only one passenger ID.
// send the driver on this path
TripPlan tripPlan = new TripPlan(drivePath, pickUpAndDropOffMap);
// confirm the request and tell the passenger which car will pick him/her up
sendMessageDispatcherSendsOutTaxi(taxiDriverId, tripPlan);
sendMessageDispatcherAcceptsRequest(request,
new TripInfo(taxiDriverId, taxiVehicle.getId()));
// flag this driver as "busy"
taxiModel.setTaxiBusy(taxiVehicle.getId());Finally, we insert the drive path and the pickup/drop-off map into a newly created TripPlan object and send it to the driver. TripPlan object represents the complete instructions for the driver. We send it to him using the sendMessageDispatcherSendsOutTaxi() function. We also need to let the passenger know that we accepted his request and that he needs to wait for the particular car to pick him up. We do this by sendMessageDispatcherAcceptsRequest() function. Also, we need to flag this driver as "busy", so we don't consider him available for future requests (until he finishes his new trip plan).
// print some debug information
LOGGER.info(" Reply: ACCEPT [sending " + taxiVehicle.getId()+"]");
LOGGER.info(" Trips:\n" + tripPlan.getTrips().toString());
// once we've sent the driver out, we can finish the execution of this function
return;
}
}In case we finish looping over the free drivers without finding anyone suitable for this request, we need to sent a request rejection to the passenger. We do this simply by calling the sendRequestReject() function.
sendRequestReject(request.getPassengerId(), request);
LOGGER.info(" Reply: REJECT [suitable taxi not found]");
}Learn also how to implement your own decentralized coordination algorithm in User's Guide part 4.
