Optimal Ride Scheduling And Sharing For Crowdsourced Transport System

With the rapid development of Internet and information technology,sharing economy is becoming more and more popular in recent years.The idea of sharing economy has been used in many areas,such as Airbnb in the fields of rentals,e Bay in the fields of goods,and Uber or Didi in the fields of transportations.In particular,the transportation area is undoubtedly one of the most widely affected areas within the global range.In this paper,we study two important problems in transport system,including ride scheduling and ride sharing.For the former problem,the current solutions used by existing vehicle sharing systems such as Didi or Uber often assumed that different passengers are scheduled independently.That is,when a passenger submits a request,the system will schedule the corresponding car immediately,without considering the requests of other users.Although independent scheduling can respond to passengers quickly,it has many disadvantages.For example,it only considers the current user requests and available vehicles in the current time,without considering the user requests and the available vehicles that may arrive in the short future.This will result in the loss of system performance.To solve this problem,we propose a joint scheduling strategy which introduces a delay scheduling window and considers the passenger’s patience.The key idea is to delay the passengers’ requests to wait for more passengers and vehicles,so that multiple passengers’ requests can be scheduled jointly and the social performance can be increased.In this work,we study three different kinds of vehicle scheduling/sharing scenarios.In the first scenario,there is no ride sharing,that is,a car can only pick up one passenger at the same time.We formulate the optimal ride scheduling problem as a passenger-vehicle matching problem,and solve the problem systematically by using classic optimization methods.In the second scenario,there is ride sharing,that is,a car can pick up multiple passengers at the same time within its capacity.We formulate the optimal ride scheduling and sharing problem as a joint passenger-vehicle matching and per-vehicle routing problem.We analyze the necessary and sufficient conditions of feasible scheduling/sharing,based on which we further analyze the optimal scheduling/sharing systematically.In the third scenario,we consider an extension version of the second scenario,by allowing some existing passengers in each car.We show that the optimal ride scheduling/sharing problem in this scenario can be formulated as a similar problem as in the second scenario,by altering some system parameters.Finally,we perform extensive simulations to evaluate the social welfare,average waiting t ime of passengers,average pick-up time of passengers,and total number of served passengers under different system settings.From simulations,we find that the social welfare and total number of served passengers first increase and then tend to be stable with the car number as well as car speed,while the average waiting time of passengers and the average pick-up time of passengers decreases with the car number and speed.Based on the above results,we further consider the delay scheduling window and the passenger’s patience.The delay scheduling window is used to delay the passengers’ requests,so that multiple passengers’ requests can be scheduled jointly.We perform simulations to study the impact of these factors on the scheduling performance.We find that the optimal delay scheduling window depends on the certain passenger’s patience.In particular,a larger passenger’s patience corresponds to a higher optimal delay scheduling window.We further compare the scheduling performance with and without the delay scheduling window.Finally,we realized the compromise between the system performance and the time delay.According to the simulation results,the social welfare and total number of served passengers first increase and then decrease with the length of delay scheduling window.The average waiting time of passengers and the average pick-up time of passengers always increase with the length of delay scheduling window.