Overlap optimization of vehicle routes

A system for optimizing vehicle route overlap in vehicle routing plans, the system comprising:

• a non-transitory memory medium configured to store instructions for processing a vehicle routing plan including a plurality of vehicle routes, the vehicle routing plan being optimized according to at least one optimization criterion other than an overlap criterion, each of the plurality of vehicle routes including a plurality of destination nodes for a respective vehicle and satisfying capacity and timing parameters for the respective vehicle to serve the plurality of destination nodes;
• and
• one or more processors configured to execute the instructions stored in the non-transitory memory medium to:
• compute a plurality of overlap metrics of the plurality of vehicle routes;
• select a first vehicle route and a second vehicle route of the plurality of vehicle routes using the plurality of overlap metrics;
• reallocate the destination nodes of the first vehicle route and the second vehicle route to a first new route and a second new route using an ordered projection of the destination nodes onto a line passing through the first vehicle route and the second vehicle route, the first new route satisfying first capacity and timing parameters of the first vehicle route, the second new route satisfying second capacity and timing parameters of the second vehicle route, wherein reallocating the destination nodes of the first vehicle route and the second vehicle route comprises:
• determining the line passing through the first vehicle route and the second vehicle route, wherein the line intersects a first centroid of the first vehicle route and a second centroid of the second vehicle route, and wherein said line intersecting the first centroid of the first vehicle route and the second centroid of the second vehicle route is determined subsequent to selection of the first vehicle route and the second vehicle route using the plurality of overlap metrics;
• determining projections of the destination nodes of the first vehicle route and the second vehicle route onto the line, wherein each of the destination nodes of the first vehicle route and the second vehicle route have a corresponding projection on the line;
• determining a sequential order of the destination nodes of the first vehicle route and the second vehicle route, according to an order of the projections of the destination nodes onto the line;
• allocating the destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order, to a first candidate route until respective limits on at least one of capacity and timing parameters of the first candidate route are reached, the first candidate route satisfying the first capacity and timing parameters of the first vehicle route;
• and
• allocating remaining destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order to the second candidate route, the second candidate route satisfying the second capacity and timing parameters of the first vehicle route;
• determine an overlap-optimized vehicle routing plan including the first new route and the second new route;
• and
• provide the overlap-optimized vehicle routing plan to control dispatch of a plurality of vehicles.

A non-transitory memory medium configured to store instructions executable by one or more processors to perform the acts of:

• storing in a non-transitory memory medium a vehicle routing plan including a plurality of vehicle routes, the vehicle routing plan being optimized according to at least one optimization criterion other than an overlap criterion, each of the plurality of vehicle routes including a plurality of destination nodes for a respective vehicle and satisfying capacity and timing parameters for the respective vehicle to serve the plurality of destination nodes;
• computing a plurality of overlap metrics of the plurality of vehicle routes;
• selecting a first vehicle route and a second vehicle route of the plurality of vehicle routes using the plurality of overlap metrics;
• reallocating the destination nodes of the first vehicle route and the second vehicle route to a first new route and a second new route using an ordered projection of the destination nodes onto a line passing through the first vehicle route and the second vehicle route, the first new route satisfying first capacity and timing parameters of the first vehicle route, the second new route satisfying second capacity and timing parameters of the second vehicle route, wherein said reallocating comprises:
• determining the line passing through the first vehicle route and the second vehicle route, wherein the line to intersects a first centroid of the first vehicle route and a second centroid of the second vehicle route, and wherein said line intersecting the first centroid of the first vehicle route and the second centroid of the second vehicle route is determined subsequent to selection of the first vehicle route and the second vehicle route using the plurality of overlap metrics;
• determining projections of the destination nodes of the first vehicle route and the second vehicle route onto the line, wherein each of the destination nodes of the first vehicle route and the second vehicle route have a corresponding projection on the line;
• determining a sequential order of the destination nodes of the first vehicle route and the second vehicle route, according to an order of the projections of the destination nodes onto the line;
• allocating the destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order, to a first candidate route until respective limits on at least one of capacity and timing parameters of the first candidate route are reached, the first candidate route satisfying the first capacity and timing parameters of the first vehicle route;
• and
• allocating remaining destination nodes of the first vehicle route and the second vehicle route, in the determined sequential order to the second candidate route, the second candidate route satisfying the second capacity and timing parameters of the second vehicle route;
• determining an overlap-optimized vehicle routing plan including the first new route and the second new route;
• and
• providing the overlap-optimized vehicle routing plan to control dispatch of a plurality of vehicles.