Overview

Background

With the rising prevalence of smart mobile phones in our daily life, Mobility-on-Demand (MoD), or online ride-hailing platforms have emerged as a viable solution to provide more timely and personalized transportation service, led by such companies as DiDi, Uber, and Lyft. These platforms also allow idle vehicle vacancy to be more effectively utilized to meet the growing need of on-demand transportation, by connecting potential mobility requests to eligible drivers. A more efficient MoD system offers better user experience for both driver and passenger groups: Drivers would be able to generate higher income through reduced idle time. Passengers would enjoy shorter waiting time and higher fulfillment rate. The efficiency of an MoD system basically hinges on how well the supply and demand distributions are aligned in both spatial and temporal spaces. There are two important problems for optimizing the operational efficiency of an MoD platform through regulating the supply distribution to better align with the demand: vehicle repositioning and order dispatching (matching). Order dispatching matches idle drivers (vehicles) to open trip orders, transporting passengers (and the drivers) to the trip destinations.  Vehicle repositioning is a proactive measure, by deploying idle vehicles to a specific location in anticipation of future demand at the destination or beyond.

This KDD Cup competition focuses on developing intelligent strategies to increase the drivers’ income on an MoD platform through order dispatching and vehicle repositioning. Higher income for the drivers means better welfare, which in turn tends to translate better service for passengers.

Platform

The competition has been launched at Biendata, please follow the link to participate: https://biendata.com/competition/kdd_didi.

Prizes

Total Prize - 30,000 USD

Please contact the organizers (kddcup2020@didiglobal.com) if you have any problem concerning this challenge.

Tasks

The challenge that the participants are to solve involves a combination of order dispatching (order matching) and vehicle repositioning (fleet management) on an MoD platform.  The teams are to develop algorithms for either or both of these tasks.  The algorithms are evaluated in a simulation environment that simulates the dynamics of an MoD platform. They are encouraged (but not limited) to use reinforcement learning methods to solve the problems. 

Environment dynamics

The test environment maintains the states of all the vehicles and trip orders. Each vehicle can serve only one trip at a time, i.e. carpooling is not considered. The order dispatching algorithm is given the states of the vehicles and orders at the time of invocation, and it is to return an assignment between the vacant vehicles and open orders. It is possible for either a vehicle or an order to be unassigned. The environment invokes the order dispatching algorithm every two seconds and executes the assignment. The assigned vehicles will be dispatched to pick up the order and transport to the destinations. If an order is not matched within its window, it is assumed lost. The passenger can cancel the order if the pick-up time for the matched driver is too long. After dropping off the passenger, the driver becomes idle and can thus move around with a vacant vehicle. During the course of any such movement, the driver is still eligible for order matching. The participants can control the repositioning of a small group (5) of the vehicles in the environment whose identity is unknown to the participants. For any of those vehicles, if the idle time exceeds a threshold of L=5 minutes, the vehicle becomes eligible for repositioning. The environment periodically sends the state information of all eligible vehicles within the selected group to the repositioning algorithm, which instructs the drivers to cruise to a specific destination. If the drivers are to stay around the current locations, they stay for L minutes before another repositioning could be triggered. The drivers other than those selected perform idle movement according to a set of generic transition probabilities. The vehicle speed is set at three meters per second for repositioning along spherical distance (a.k.a. great-circle distance).

There are two tasks for each participating team:

Task 1: Order dispatching

The team is to develop an algorithm to determine the order-driver assignment within a two-second dispatch window. The open orders (trip requests) and available drivers are batched in the window, and their state information will be passed to the order dispatching algorithm. This module will be called repeatedly for each dispatch window throughout the simulation day. The evaluation simulation runs over multiple `days', from where the mean total driver income (defined in Evaluation) is computed as the score for the algorithm.

Task 2: Vehicle repositioning

The team is to develop a repositioning algorithm for a pre-selected small group of vehicles.

The identity of the vehicles for algorithmic repositioning is unknown to the teams, requiring that the algorithms be agnostic to the identity of the vehicles.  For any of those vehicles, if the continuous idle time exceeds a threshold of L=5 minutes, the vehicle becomes eligible for repositioning. The environment periodically sends the state information of all eligible vehicles within the selected group to the repositioning algorithm, which instructs the drivers to cruise to a specific destination. The mean individual income rate (defined in Evaluation) for the group over the simulation period is computed as the score for this algorithm.

The algorithms will be evaluated in a simulation environment which the teams do not have access to, except the scores generated by the environment. The participating teams can choose to develop either or both algorithms. (One can always use the sample code for one of the algorithms, although that obviously will not produce a competitive score.)

The two policies are related (i.e. they are run in the same environment), but they are also sufficiently separate so that skipping one does not necessarily jeopardize the chance of winning on the other.  

The set-up of the competition resembles a real industrial setting, where it is typically not possible to train and explore directly on the production system due to operational and financial risks. On the other hand, there is usually abundance of data from historical operations. A simulator can be built for evaluating potential algorithms, but it is hard to simulate every details of the production system close to reality.

Data

Description

The data to be released to the participating teams is primarily based on the Chengdu data set from the DiDi GAIA program. This data set contains trips within a rectangular box on the map of Chengdu over November, 2016. We have augmented the data set with assigned reward units for each trip to represent the driver income, as well as cancellation probabilities for different pick-up distances. The reward units are a form of score representation for the competition, not necessarily reflecting the actual trip price. The evaluation environment uses the same reward units system. Both the order IDs and driver IDs are anonymized. A given driver ID can be used to query all the trips for the driver within a particular day but not across days.

In addition to the trip data, we will provide a table that defines the hexagon grids covering the geographical area represented by the trip data set. For each unique cell ID, the coordinates of the six vertices that define the hexagon are given. To characterize the general free-time cruising behavior of the drivers, we also provide the transition probabilities for each (hex-cell, hour) combination.

Download

Participants can download the public dataset in the "GAIA Open Dataset - Apply Now" page.

Rules

- All participants need to sign-up in the management system (DiDi Employees are not allowed to participate in this competition).

Challenge Platform: https://biendata.com/competition/kdd_didi

- Participants form teams inside the management system. Each team must consist no more than ten members. Each team needs to appoint a leader. Team title should contain no more than 15 characters.

- Each participant can join only one single team. Registering more than one account to join more than one team will lead to disqualification of all teams involved.

- Teams are allowed to combine before the team merge deadline but teams may not split. Combined teams must consist of no more than ten members.

- It is allowed to use open-source codes or tools, but using codes or tools that require authorization is not allowed.

- Except the datasets provided by the competition organizer, it is not allowed to use any external data.

- Privately sharing code or data outside of teams is not allowed.

- Each team can submit test code through Quick Test Submission.Submissions are limited to 20 times per day per team. The file size for each submission should not exceed 1GB. There is a fifteen-minute timeout limit for the run time.

- Each team is allowed to submit their solution up to 1 time every day for evaluation in the test environment. The file size for each submission should not exceed 1GB. There is a twenty-hour timeout limit for the run time.

- The competition organizers reserve the right to update the competition timeline and rules if they deem it necessary.

Competition Process

The competition is divided into two phases, which are described in details below.

Development

The teams will be given a development kit consisting of data sets, sample source code and other information to develop the required algorithms. The development of a solution does not require building a simulator, although description of important environment dynamics will be provided to the teams, and they can choose to build a simulator at their discretion. The solution is in the form of source code that conforms to the specified module interfaces. The environment will pass the state information of all vacant vehicles and active orders within the current batch window to the order dispatching algorithm, which returns a matching. The vehicle repositioning algorithm will receive upon invocation the state information of the current driver and all the other idle drivers among the specific repositioning drivers, whose identity is unknown to the teams. The teams will be able to discuss any questions that they have with the organizers through the forum on the competition platform.

Validation

The solution is to be submitted in a zip file with a specified file directory structure through the competition platform. Each team is allowed to submit their solution 1 time every day for evaluation in our simulation environment. The evaluation runs offline, and each successful submission will receive two scores corresponding to the two metrics. The scores are updated on the leaderboard. Evaluation of each submission will additionally report other relevant metrics, e.g., fulfillment rate, response rate, as feedback to the teams.

Testing

Before entering the final Testing Phase, the teams will be asked to submit an explanation on how their solution is related to RL in the broad sense (e.g., MDP, Approximate DP, bandits, adaptive control, optimization with long horizon). The union of the top 25 teams for each task (or the total number of teams, whichever is less) from Development Phase enter the final Testing Phase. The last submission of each selected team from Development Phase will be evaluated in a separate test environment (never seen by the teams during training phase but with the same environment dynamics). The last score from the Development Phase carries 40% weight into the final score, while the score from the Testing Phase carries 60%. The teams will be ranked on the two final scores separately.

Evaluation

Each trip order in the released data and the evaluation environment is assigned a reward unit number that represents the potential income for the driver. Evaluation is run over multiple days in simulation, with the same city as the one in the released data set but different time interval. Submissions are evaluated on two metrics corresponding to the two tasks.

Mean total driver income (for order dispatching). For each day of simulation run, let 𝑖= 1, · · · , 𝐼be the indices for all the orders submitted to the system. Let 𝑝(𝑖) (𝜋𝑑, 𝜋𝑟) be the actual income for order 𝑖 under order dispatching policy 𝜋𝑑 and vehicle repositioning policy 𝜋𝑟. If order 𝑖is completed in the simulation, 𝑝(𝑖) is equal to the assigned reward units. Otherwise, 𝑝(𝑖)= 0. The evaluation is run over days 𝑛= 1, · · · , 𝑁. The total income for day 𝑛 and submission 𝜋= (𝜋𝑑, 𝜋𝑟) is

The mean total driver income for the submission 𝜋 is defined as

It is expected that the order dispatching algorithm has the major impact on this metric, as the repositioning algorithm controls only a small group of vehicles, which are unlikely to influence the global context.

Mean individual income rate (for vehicle repositioning). The group of drivers whose repositioning strategy is to be run by 𝜋𝑟 are indexed by 𝑘= 1, · · · , 𝐾. The total income for driver 𝑘 on day 𝑛 is J𝑘(𝑛)(𝜋), and the corresponding online time for the driver is L𝑘(𝑛)(𝜋) . Income rate is defined as the income per unit online time. The mean individual income rate is

The repositioning algorithm is naturally the main influencer on this metric, as the order dispatching algorithm is agnostic to the identity of this group of drivers. 

Timeline and Prizes

Important Dates

- April 2nd, 2020: Competition starts (Development Phase), datasets release and registration opens

- April 7th, 2020: Submission opens

- July 9th, 2020: Development Phase ends

- July 10th, 2020: Final Phase starts (Top 25 teams for each task from Development Phase enter Final Phase).

The last submission from Development Phase will be evaluated in the unseen test environment to produce the final score per calculation described in Competition Process.

- July 17th, 2020: Competition ends

- July 24th, 2020: Winner announcement

- Aug 23rd, 2020: Beginning of KDD 2020

All deadlines are at 11:59 PM UTC on the corresponding day. The organizers reserve the right to update the contest timeline if necessary.

Prizes

The teams will be ranked by their scores of the two tasks (order dispatching and vehicle repositioning) separately. 

Task 1

1st Place: $8,000

2nd Place: $4,000

3rd Place: $2,000

4th to 5th Place: $500 for each

Task 2

1st Place: $8,000

2nd Place: $4,000

3rd Place: $2,000

4th to 5th Place: $500 for each

About

Contact

Please contact kddcup2020@didiglobal.com, if you have any problem concerning this challenge.

Committee

Zhiwei(Tony) Qin, Xiaocheng Tang, Lulu Zhang, Yanhui Ma, Jianhua Zhang, Fan Zhang, Cheng Zhang

About Didi Chuxing

Didi Chuxing (“DiDi”) is the world’s leading mobile transportation platform. The company offers a full range of app-based transportation services for 550 million users across Asia, Latin America and Australia, including Taxi, Express, Premier, Luxe, Bus, Designated Driving, Enterprise Solutions, Bike Sharing, E-bike Sharing, Automobile Solutions and food delivery. Tens of millions of drivers who find flexible work opportunities on the DiDi platform provide 10 billion passenger trips a year. 

DiDi is committed to collaborating with policymakers, the taxi industry, the automobile industry and communities to solve the world’s transportation, environmental and employment challenges with localized smart transportation innovations by leveraging its AI capabilities. By continuously improving user experience and creating social value, DiDi strives to build a safe, inclusive and sustainable mobile transportation ecosystem for cities of future.

About DiDi AI Labs 

DiDi AI Labs was established to solve difficult AI problems, with a focus on the research and application of cutting-edge technologies such as machine learning, natural language processing, computer vision, speech recognition, operational research,statistics, and so on. We actively adopt next-generation technologies, improve mobility efficiency and experience for users, and build a smart mobility ecosystem using technologies. DiDi AI Labs are dedicated to becoming a globally leading science and technology lab for smart transportation technologies, and start a new era of scientific research for DiDi.

About DiDi Technology Ecosystem & Development

DiDi collaborates with universities, colleges and research institutions all over the world to explore cutting-edge technologies along with the commitment to serve as the most trustworthy partner in the academic field. Our unique programs, such as GAIA Open Dataset, Athena Global Talent Program, AI for Social Good, enable us to provide world - class talents with a comprehensive platform to explore technology and improve themselves.

About KDD 2020 Conference

The annual KDD conference is the premier interdisciplinary conference bringing together researchers and practitioners from data science, data mining, knowledge discovery, large-scale data analytics, and big data.

KDD 2020 Conference

- August 23 - 27, 2020

- San Diego Convention Center

- San Diego, California USA

Sponsor

Didi Chuxing