System and method for generating real-time routing for on-demand transportation

A non-transitory storage medium storing processor-readable software instructions thereon that when executed by a processor, cause the processor to perform the steps of:

• receiving new trip requests from a plurality of passenger processing devices during a first period associated with each new trip request, each new trip request comprising trip parameters including an origin location, a destination location and at least one of an earliest departure time and a latest arrival time;
• during a first period associated with each new trip request:
• generating a routing plan for the fleet, the routing plan including routes for one or more of the multi-passenger vehicles, each route comprising an ordered list of route stops and at least one of an arrival time and a departure time associated with each route stop, the routing plan being generated based on the trip parameters of the new trip requests and on trip parameters of previously accepted trip requests and being further based on operator-specific parameters, and
• individually accepting a given one of said new trip requests when a routing plan accommodating the trip parameters thereof is generated;
• during a second period associated with each accepted trip request and subsequent to the first period associated with the accepted trip request:
• updating the routing plan to minimize an objective function representative of a relevance of the routing plan, the objective function being calculated based on at least one of the operating costs and service quality metrics, and
• transmitting to a passenger processing device associated with the accepted trip request, trip details according to the routing plan, the trip details comprising a pickup stop, a pickup time, a drop-off stop, a drop-off time, and a vehicle identification, whereby waiting for the second period to transmit the trip details to the passenger processing device allows for improving the dynamic routing plan, the routing plan further including committed elements which are unmodifiable when the routing plan is generated or updated, the committed elements including at least the trip details transmitted during the second period;
• and
• transmitting, to each of a plurality of vehicle processing devices associated with the fleet of multi-passenger vehicles, routing information comprising route segments and stops of the routes to be traversed by the multi-passenger vehicles, including for at least one of the vehicle at least a next stop and a route segment for the vehicle to traverse to reach the next stop, the committed elements further comprising the transmitted routing information.

A system for determining, in real time, a dynamic routing plan for a fleet of multi-passenger vehicles, the system comprising one or more servers comprising:

• an application interface configured to receive new trip requests from a plurality of passenger processing devices, each new trip request comprising trip parameters including an origin location, a destination location and at least one of an earliest departure time and a latest arrival time;
• an operator-dashboard interface for inputting operator-specific parameters, the operator-specific parameters including at least operating costs of the multi-passenger vehicles;
• and
• a route planning module for generating, during a first period associated with each new trip request, a routing plan for the fleet, each route in said routing plan comprising at least a list of route stops to visit, an arrival time and/or a departure time at each route stop, each route in said routing plan being generated based on the trip parameters of the new trip requests and on trip parameters of previously accepted trip requests, each route being further based on operator-specific parameters, the operator-specific parameters including at least operating costs of the multi-passenger vehicles,
• the application interface configured for sending, during the first period associated with each new trip request, notices to the plurality of passenger processing devices, acceptance notices being sent when a routing plan accommodating the trip parameters and the operator-specific parameters can be generated;
• the route planning module configured for updating, during a second period associated with each accepted trip request and subsequent to the first period associated with the accepted trip request, the routing plan to minimize at least an objective function associated with the routing plan and being indicative of a relevance of the routing plan, the objective function being calculated based on at least one of the operating costs and service quality metrics;
• the application interface configured for sending, during the second period associated with each of accepted trip requests, to passenger processing devices associated with the accepted trip requests, trip details associated with a most recently updated routing plan, the trip details comprising a pickup stop, a pickup time, a drop-off stop, a drop-off time, and a vehicle identification,
• the routing plan further comprising committed elements including at least the trip details transmitted during the second period, wherein the committed elements are unmodifiable when generating and updating the routing plan;
• and
• the application interface configured for sending, to each of a plurality of vehicle processing devices associated with the fleet of multi-passenger vehicles, routing information comprising route segments and stops of the routes to be traversed by the multi-passenger vehicles, including for at least one of the vehicle at least a next stop and a route segment for the vehicle to traverse to reach the next stop, the committed elements further comprising the transmitted routing information.