Method and apparatus for providing large scale vehicle routing

An apparatus for providing large scale vehicle routing, comprising:

• a processor;
• and
• a memory including computer program code for a program,
• the memory and the computer program code configured to, with the processor, cause the apparatus to perform at least the following,
• receive a plurality of plans, wherein a plan of the plurality of plans assigns a vehicle, a driver of the vehicle, or a combination thereof a set of rides to traverse;
• cluster the plurality of plans into one or more clusters based on a proximity measure, wherein the proximity measure indicates a proximity of a first plan of the plurality of plans to a second plan of a plurality of plans;
• and
• for each cluster of the one or more clusters, separately compute a solution to a multiple vehicle routing problem for the set of rides in said each cluster.

A non-transitory computer-readable storage medium for providing large scale vehicle routing, carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:

• receiving a plurality of plans, wherein a plan of the plurality of plans assigns a vehicle, a driver of the vehicle, or a combination thereof a set of rides to traverse;
• clustering the plurality of plans into one or more clusters based on a proximity measure, wherein the proximity measure indicates a proximity of a first plan of the plurality of plans to a second plan of a plurality of plans;
• and
• for each cluster of the one or more clusters, separately computing a solution to a multiple vehicle routing problem for the set of rides in said each cluster.