Real-Time City-Scale Taxi Ridesharing

ABSTRACT

• propose and develop a taxi-sharing system
  • a taxi searching algorithm based on spatio-temporal index
  • a scheduling process selecting the most satisfied taxi

1 INTRODUCTION

• Real-time taxi-sharing has not been well explored.
• Real-time-taxi-sharing is more challenging due to the dynamic changes in both ride requests and taxi positions.
• Compared to existing carpooling systems, this model considers more practical constraints, such as time windows, capacity and monetary constraints.
• This paper’s contributions:
  • propose and develop a taxi-sharing system using the mobile-cloud architecture
    • a spatio-temporal indexing structure
    • a taxi searching algorithm
    • a scheduling algorithm
  • considers and models monetary constraints in ridesharing
    • passengers will pay less and drivers can make more
  • perform extensive experiments to validate the effectiveness of this system
• This paper’s structure:
  • Section 2: formally describe the real-time-ride-sharing problem
  • Section 3: overview the architecture of the system
  • Section 4: describe the index of taxis and taxi searching algorithm
  • Section 5: describe the scheduling process
  • Section 6: evaluation
  • Section 7: related work

2 RTTS PROBLEM

2.1 Data Model

• Ride Request

• Taxi Status

V.s : a temporally-ordered sequence of origin points and destination points, such as Q1.o, Q2.o, Q1.d…

• Qi.o should proceeds Qi.d
• Qi.o should not only exist in the sequence

V.r : a sequence of road network

2.2 Constraints

• Vehicle Capacity make sure that the number of passengers is less than the number of taxi seats

• Time Window all passengers should be able to depart from the origin point and arrive at the destination point during the pickup and delivery time window

• Monetary passengers should pay less and drivers should earn more

2.3 Objective Function & Problem Definition

• definition of the optimal taxi
  satisfy Q with minimum increase in V’s scheduled travel distance

• feature of this problem
  

  • the real-time taxi-sharing problem inherently resembles a greedy problem
  • the problem of minimizing the total travel distance of all taxis is NP-C

3 SYSTEM ARCHITECTURE

4 TAXI SEARCHING

4.1 Index of Taxis

The spatio-temporal index of taixs is built for speeding up the taxi searching process.

• parttion the road network using a grid

• choose the road network node which is closeest to the geographical center of the grid cell as the anchor node
  

• compute the distance between grid i and grid j, denoted by \(d_{ij}\)

• compute the travel time between grid i and grid j, denoted by \(t_{ij}\)

• in this paper, \(d_{ij}\) and \(t_{ij}\) are calculated only once

• the distance betweeen two girds is approximated by the distance between two corresponding anchor nodes

• each gird maintains three lists:

  • a temporally-ordered grid list \(g_i.l_c^t\), the list of other girds sorted in ascending order of the travel time from these grids to \(g_i\)

  • a spatially-order grid cell list \(g_i.l_c^s\), the list of other grids sorted on ascending order of the travel distance from these grids to \(g_i\)

  • a taxi list list \(g_i.l_v\), records the IDs of all taxis which are scheduled to enter \(g_i\) in near future, each taxi is is tagged with a timestamp \(t_a\) indicating when the taxi will enter the grid cell, all taxis in the list are sorted in ascending order of associated timestamp \(t_a\), \(V_j\) is removed from list when \(V_j\) leaves \(g_i\), \(V_k\) is inserted into list when it is newly scheduled to enter \(g_i\).

4.2 Searching Algorithm

4.2.1 Single-Side Taxi Searching

Any other arbitrary grid cell \(g_i\) is selected if it meets Eq.(1):

The single-side algorithm simply tests all grids in the temporally-ordered grid cell list and find the first grid \(g_f\) which fails to hold Eq.(1). Taxis in grids before \(g_i\) are selected as candidate taxis.

Shortcomings: only considers taxis currently “near” the pickup point and the number of candidate taxis could be large which would lead to large computation cost;

4.2.2 Dual-Side Taxi Searching

Any other arbitrary grid cell \(g_i\) is selected if it both hold Eq.(1) and Eq.(2):

Shortcomings: may result larger increase in travel distance;

Advantages: select far fewer taxis for schedule step and reduce the computation cost;

Performance: the number of selected taxis is reduced by 50% while the increase in travel distance is just 1%;

5 TAXI SCHEDULING

The purpose of the taxi scheduling process is to find the taxi status in SV which satisfies Q with minimum travel distance increase.

Given a taxi status, theoretically we need to try all possible ways of inserting Q into the schedule of the taxi status in order to choose the insertion which results in minimum increase in travel distance.

All possible ways of insertion can be created via three steps:

1. reorder the points in the current schedule, subject to the precedence rule;
2. insert Q.o into the schedule;
3. insert the Q.d into the schedule;

The capacity and time window constraints are checked in all three steps, during which the insertion fails immediately if any constraint is violated.

The monetary constraints are then checked for the insertion after all three steps have been done successfully.

Finally, among all insertions that satisfy all constraints, we choose the insertion that results in minimum increase in travel distance for the given taxi status.

5.1 Time Window Constraints

Given a schedule of \(n\) points, there is clearly \(O(n^2)\) ways to insert a new ride request into the schedule.

To ease the computation load, using the fastest path from one point to another during insertion.

Question: how to get a balance between time and distance?

Restrictions on insertion:

In the example in Fig. 11, if \(t_d \leq \min\{(Q_1.d)_{st}, (Q_2.d)_{st}\}\), then insertion successes.

5.2 Monetary Constraints

An insertion satisfies the monetary constraints only when all current riders on the taxi support the pickup decision： \(\Delta f_i / \Delta T_i \geq Q_i.r\).

Two constraints to encourage riders to participate in taxi-sharing:

• rider who participates in taxi-sharing should not pay more;

• rider whose travel time is lengthened due to the pickup of Q should get a decrease in taxi fare;

• driver should charge for all distances;

Some riders may think the fare decrease is not worth the increase in travel time and thus reject the pickup decision. Therefore, let every rider \(Q_i\) set a parameter \(Q_i.r\), if \(\Delta f_i / \Delta T_i \geq Q_i.r\), then inform the rider.

• Previous
  思考：如何写论文？
• Next
  笔记：调度算法（二）