Problem Definition

The 2020 GISCUP problem will be an extension of the GISCUP 2019 problem.

The problem is defined in the context of taxicabs searching for customers. The system consists of five types of entities: a road network, mobile agents (i.e., taxicabs), and stationary resources (i.e., customers), agent control authority. This year, contestants will write the agent control authority, also called the Fleet Manager to manage an entire fleet of taxicabs.

This year’s contests will also introduce several new aspects:

  • Dynamic travel times: the road network will model traffic congestion. Travel through road segments will depend on current road conditions.
  • Multi-scenario objectives: there are two objectives of which the first reflects 2019 GISCUP challenge for prioritizing agent utilization and the second is prioritizing customer experience.

Agents (Taxicabs)

  • All agents are introduced to the system at the beginning of the simulation, each located at a random location on the road network.
  • The number of agents are fixed for each simulation run.
  • After an agent is introduced, it is labeled as empty and travels/cruises along a path decided by the Fleet Manager, which we will call a search path.
  • Fleet Manager determines the cruising path of empty agents

Resources (Customers)

  • Riders are introduced to the system in a streaming fashion, each with a destination.
  • Each resource has a maximum life time (MLT) starting from its introduction. If the MLT is reached, the resource will be automatically removed from the system, an outcome that we will call resource expiration.
  • When a resource is introduced to the system, the Fleet Manager assigns an agent to service the resource.

Road Network

  • The road network is a network of road segments.
  • The road network module will return an estimated transit time for Fleet Manager planning.
  • The road network module will return the actual transit time during simulation. The transit time will depend on a congestion model that is unknown to the Fleet Manager. Note that the actual transit time could be different from the estimated transit time.
  • The presence of agents on a road segment does not influence the road segment travel time.

Evaluation Metrics

Each submission will be evaluated on three aspects of performance. The weight of each will depend on the objective (see below).

  • The search time of an agent is the amount of time from when the agent is labeled as empty until it picks up a resource. An agent may experience multiple search times, each corresponding to one assignment.
  • The wait time of a resource is the period of time from its introduction until its pick-up or expiration.
  • The expiration percentage is the percentage of expired resources.

In summary, the problem definition is as follows:

Input:

  • A road network (map), and a travel time model.
  • A training dataset (list of resource locations and timestamps);
  • A test dataset (list of resource locations and timestamps);
  • The number of agents (i.e., agent cardinality) and their initial locations. The agent cardinality may be 5000, 6000, 7000, 8000, 9000, or 10000.

Output:

  • Assignment of agent to resource.
  • Search path for each agent.

Objectives:

Agent utilization scenario: Minimizing (in order of priority) the average search time, average wait time, and expiration percentage. The average search time will be the primary evaluation metric. The average wait time and then the expiration percentage will be used to break ties.
Customer/Resource experience scenario: Minimizing (in order of priority) the resource average wait time, expiration percentage, and average search time. The resource average wait time will be the primary evaluation metric. The expiration percentage and average search time will be used to break ties.

Awards:

Two winners will be selected for each objective, and invited to present their results at a special contest session during the conference.

Software Framework

There are multiple constraints that need to be satisfied by a submission:

  1. An agent does not know when and where resources will be introduced in the future beyond the data model;
  2. The search path of an agent is constrained to the road network and adheres to traffic limitations provided by the map (e.g., route restrictions, speed limits).

To ensure that these constraints are satisfied, an open-source simulation framework called COMpetitive SEarching Testbed (COMSET) will be provided to the participants. This software is based on the software of the same name from 2019. COMSET, written in Java, implements the fundamental logic of the system including the handling of maps, the injection of resources, the movement of agents along a given path, the assignment of agents to resources, and the calculation of performance metrics. COMSET provides a fleet-manager base class for participants to extend with implementation of their search algorithm. The architecture of COMSET is shown in Figure 1. The green block is the module to be extended by the participants.

Figure 1
Figure 1: The architecture of COMSET.

The major software modules in COMSET are:

  • Agent simulates the behavior of agents
  • Resource simulates the behavior of resources
  • Fleet Manager tracks the current position and status of the agents; assigns agents to their nearest resources; computes expected search times, wait times, and expiration percentage.