笔记：调度算法（四）

An Efficient Dynamic Ridesharing Algorithm

Dynamic Taxi Ridesharing Problem is defined as follows: given a set of taxis Taxi on the road network G and a new incoming request \(tr_new\) , find the taxi taxi \(\in\) Taxi that can get the maximum average satisfaction.

Overview

Definition

• Definition 1 (Road Network)：
  • \(G = (V, E, W)\) consists of a vertex set V and an edge set E
  • o, d represent the staring point and the ending point in the road network
• Definition 2 (Trip Request):
  • denote as \(tr = (t, 0, d, wp, wd, det, r, cnt)\)
  • varible definition:
    • t: timestamp
    • o: pickup point
    • d: destination point
    • wp: the time interval when the passenger needs to be picked up at the pickup point
    • wd: the time interval when the passenger needs to be droped off at the destination point
    • det: detour distance/time that passenger can tolerate, using the shortest path
    • r: the ratio for time window in this request
    • cnt: indicate the passenger count in this request
• Definition 3 Taxi Schedule:
  • \(S = (v_1, v_2,\cdots,v_{2n})\) is a temporally ordered sequence of pickup and destination points of n trip requests \((tr_1, tr_2,\cdots,tr_n)\).
• Definition 4 Valid Taxi Schedule:
  1. Orderness: pickup point must happen before its destion point
  2. Waiting time constraint: must not exceed the pickup or drop off time constraint
  3. Detour distance constraint: must not exceed the distance constraint
  4. Passenger number constraint: the number of passengers muat not exceed the taxi capacity
• Definition 5 Slack Time:
  • Definition: \(ST_{V_i} = T_{lateV_i}-T_{arriveV_i}\)
  • \(T_{lateV_i}\): the latest allowed arrival time
  • \(T_{arriveV_i}\): the actual arrival time
• Definition 6 Service Rate:
  • the fraction of the trip request that are satisfied
• Definiton 7 Satisfaction:
  \(Sa_{tr} = tr(r)\frac{ST_{tr(o)}+ST_{tr(d)}}{tr(wp)+tr(wd)}+(1-tr(r))\frac{tr(det)-detour}{tr(det)}\)
  • \(tr(r)>0.5\): the user prefers to save more time
  • \(tr(r)<0.5\): the user prefers to reduce detour distance
  • detour: the actual detour distance
• Definition 8 Average Stisfaction:
  \(AS_{S_i} = \frac{1}{n}\sum_{j=1}^{n}Sa_{tr_j}\)

Constraints

Searching and Scheduling Algorithm

The binary search algorithm based on time

Scheduling algorithm

Taxi Recommender System using Ridesharing Service

Our main aim is to recommend a taxi T that would minimize its travel distance after satisfying all the passenger’s queries that has arrived within a time interval.

Overview

Definition

• Definiton 1 Query:
  • P.p: pickup point of pessenger P
  • P.d: destination of passenger P
  • P.p.t: the time before which the taxi must reach the pickup point
  • P.d.t: the time before which the taxi must reach the destination
• Defination 2 Path:
  • the path of each taxi is dynamiclly updated
• Definiton 3 Constraints:
  1. the current capacity is less than the maximum capacity
  2. the taxi can arrive at the pickup points and destination points whithin the predetermined time-interval after including P.p and P.d in its path
• Defination 4 Taxi Status:
  • current location, T.11-latitude, T.12-longitude
  • id of the taxi T.id
  • number of passengers in the taxi T.p

Dynamic Taxi-Ridesharing Problem

Our aim is to recommend a taxi, which satisfies the passenger’s request with minimum increase in travel distance of that particular taxi.

Taxi Recommender System

• taxi-searching module
• apply time-window scheduling algorithm
  • calculate shortest path between the location of taxi and the location of the passenger
  • divide the city into small regions, each has a centroids \(C_i\)
  • 中心点之间的距离由 Haversine公式 (球面距离计算公式)计算得出
    • C is the angular distance in radians - 弧度的角距离
    • a is the square of half the chord length - 两点之间弦长度一半的平方
  • \(L_i^d\): the distance of \(L_i\) from all other locations in ascending order
  • \(L_i^t\): the taxi-id T.id near to the given location \(L_i\)

Taxi-searching Algorithm

Single-side Taxi Searching

The main concept of this searching is that we search from single-side. We select all the regions near to Lo.

select a taxi if it can reach the passenger within the time-limit:
\(t_{curr} + t_{il} \leq P.p.t\)

Dual-side Taxi Searching

It is a bidirectional searching algorithm. In this searching algorithm we search from both source side as well as destination side simultaneously.

Taxi-scheduling

The purpose of the scheduling is to properly schedule the route of a taxi so that the total distance travelled by the taxi could be minimized.

• attend n number of queries within a time window t;
• calculate the distance of current query from a filled taxi;
• If this distance comes out to be less than the previously attended query, then the current query is assigned the given taxi.

Pricing Scheme

1. taxi fare per kilometre is higher for multiple passengers than for a single passenger, this property is beneficial for the driver
2. the taxi fare distribution is even among all the passengers; as a result, if more people share a taxiride, then each individual pays less for the ride

• r: the taxi-fare per kilometre
• k: the initial fare parameter
• d1*r: the initial fare of distance d1 whithout ridesharing
• ? fare per individual is calculated as below:
  \(Individual\_fare = r*d1 + \frac{(r+1.5)*d_{1-10}}{m_{1-10}}+\frac{(r+1.2)*d_{11-30}}{m_{11-30}}+\frac{(r+1.2-(dc-30)/10^4)*d_{30-}}{m_{30-}}\)
• ? total profit for taxi drivers is calculated as below:
  \(Total\_profit = r*D_n +(r+1.5)*d_{1-10}+(r+1.2)*d_{11-30}+(r+1.2-(d_c-1.65)/10^4)*d_{30-}\)

GrabShare: The Construction of a Realtime Ridesharing Service

The construction of GrabShare demonstrates many teams and disciplines working together to provide intelligent transportation solutions that make the best use of available technology to meet the needs of today’s rapidly growing population of smartphone users in Southeast Asia.

Grabshare Core Cconcepts and Workflow

items

• Passenger：Customer who wants to travel from some pickup location to some dropoff location
• Driver: User who controls a vehicle
• Booking: An individual transportation request
• Step: An instruction to go to a particular location and pick up or drop off a passenger
• Driver Plan: A sequence of steps to be performed in order

The Scheduling System

The scheduling system is responsible for taking new bookings and proposing appropriate driver plans.

The GrabShare team internally uses trip notation:

• \(\overline{A}\): pickup step
• \(\underline{A}\): dropoff step
• Example plan: \(\overline{A}\overline{B}\underline{A}\underline{B}\)

Rules:

• do not allow dropoff steps to be be scheduled any more than 3 steps after their corresponding pickup steps;
• do not make driver plans with more than 2 bookings sharing;

We consider only the nearest candidate drivers. Grab’s existing services for tracking and updating known driver locations and getting the drivers nearest to a given location are used for this.

Process:

• enumerate the possible new driver plans that arise from adding the steps A̅ and A̲, following the restrictions outlined above 列举出所有不违反上述规则的计划
• estimate how long each step will take to carry out using a course geometric estimate of travel time for each step 估算出每一步需要大概需要的时间
• score each candidate plan according to a number of features that characterize good plans 根据一些特征给每个候选计划打分
• for the k best-scoring plans, recompute the estimated step travel times using a more accurate but more computation-ally costly estimate from a directions web service 选出最好的 k 个，更准确地估算每一步所花时间
• rescore each of these plans using the new travel time estimates 重新打分
• return these candidate plans to the booking service, which is then responsible for offering the booking to the drivers in order until an acceptance is confirmed 将计划发送给出租车，先确认的接单

Scoring Features

• Minimize ETA to passenger pickup；
• Minimize the amount of expected additional journey time, over and above the predicted direct travel time
• Maximize the overlap between bookings
• Minimize the angle between the bookings

Internally, the scoring features are all normalized to return scores between -1 (bad) and 1 (good). For example, if the maximum expected time to pickup is set to t minutes, a normalized scoring function might be 1 - 2x/t, so that at x = 0 minutes, the score is a perfect 1, at x = t/2 minutes a neutral 0 score, and at x = t minutes, a negative 1 score.

Pricing And Incentives

Passenger Discounts from Predicted Efficiency Pricing

The discount offered is proportional to an estimate of the efficiency likely to be gained from matching this booking.

The predicted efficiency algorithm proceeds as follows:

• Given a new booking A, find the existing bookings whose match with the new booking would give a high efficiency.
• Rank the top k such bookings to give a set{Bi}
• Compute a weighted score measuring the efficiency that can be gained by carrying out bookings A and B together
• Normalize this score to a discount in the range 0 to 1

Driver Incentives

• With more passenger bookings completed, driver monthly incomes have also increased

Other Areas Vital to Ridesharig

• Routing and Traffic Resources
  • assist with traffic planning and infrastructure investments
  • leading to directions and ETA estimates that are tailor-made for different vehicle types
• Scheduling Research and Simulation
• User Experience Design
• Feedback from Passengers and Drivers
• Geographic Diversity

Real time ridesharing: understanding user behavior and policies impact

Despite the fact that the service allows real time matching between supply and demand, Moovit cannot be defined as a “calling” service because it is the driver who inserts his path on the platform and allows the passenger to visualize it.

• Previous
  笔记：调度算法（三）
• Next
  笔记：算法练习