Problem Definition

The problem is defined in the context of crowdsourced taxicabs searching for customers to pick up. The system consists of four types of entities: a road network, mobile agents (i.e., taxicabs), and stationary resources (i.e., customers), and an assignment authority. All agents are introduced to the system at once at the beginning of the operation, each located at a random location on the road network. The set of agents is fixed throughout the operation, the size of which will be referred to as the agent cardinality. Resources 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. After an agent is introduced to the system, it is labeled as empty and cruises along a path decided by the solution, which we will call a search path. When a resource is introduced to the system, the agent that meets the following conditions is assigned by the assignment authority to the resource:

  • The agent is empty;
  • The agent is closer (by shortest travel time) to the resource than any other empty agent;
  • The shortest travel time from the agent to the resource is less than the resource‚Äôs remaining life time (i.e. MLT minus the time duration since the resource was introduced).

Once an agent is assigned to a resource, the agent is labeled as occupied, and the resource is removed from the system. Then the agent moves to the resource (for pick-up) and then to the destination of the resource (for drop-off), both along the shortest-travel-time path on the road network. Once the agent arrives at the destination, it is labeled as empty. If there is no agent that meets the above conditions, then the resource remains in the system until an agent meeting the above conditions appears or the resource expires. The agent knows neither when and where the future resources will be introduced nor any information about the other agents.

The assignment authority has an optional software module called the data model, which contest participants can choose to implement for the contest. The data model is collectively shared with all of the agents and can be used to represent resource availability patterns and predict future availability. The contest organizers will define a training dataset for participants to build the data model prior to the system operation. The training dataset contains records of the times and locations at which resources became available on a road network in the past. The system will operate on a resource dataset which we will call a test dataset. The test dataset is a randomly chosen subset of the training data. For example, the training dataset covers a year, whereas the test dataset covers random time periods within that year.

Each submission will be evaluated on three aspects of performance, in order of priority:

  • 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);
  • 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:
Search path for each agent.

Objective:
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.

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 agents do not share information with each other;
  3. 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. COMSET, written in Java, implements the fundamental logic of the system described in Section 2, including the handling of maps, the injection of resources, the movement of agents along a given path, the assignment of agent to resource, and the calculation of performance metrics. COMSET provides a base class of agent for participants to extend with implementation of their search algorithm. Similarly, COMSET provides a base class of the data model. The architecture of COMSET is shown in Figure 1. The yellow blocks are the modules to be extended by the participants.

Figure 1
Figure 1: The architecture of COMSET.

The major software modules in COMSET are:

  • Agent: computes search path based on the map and optionally the result of the data model.
  • Assignment Authority: tracks the current position and status of the agents; assigns agents to their nearest resources; computes the search times, wait times, and expiration percentage.
  • Data Model (optional): Represents the resource availability patterns and predicts future resource availability (e.g., when and where there will be likely resources available).

COMSET can be downloaded at https://github.com/Chessnl/COMSET-GISCUP/archive/v1.0.zip