Patent ID: 8103532

Claim:
A computer implemented method to reduce vehicle travel time and a number of vehicles in a vehicle routing plan having vehicle routes which include vehicles and customers serviced by the vehicles, the method comprising: in a processor, executing cross-exchanges of the customers for combinations of vehicle routes in the vehicle routing plan, comprising: calculating a travel time or time savings of executed cross-exchanges; saving, in a cross-exchange matrix comprising combinations of the vehicle routes, a cross-exchange resulting in the minimal travel time or maximum travel time savings for vehicle route combinations; and modifying the vehicle routing plan by performing the saved cross-exchange in the cross-exchange matrix resulting in the minimal travel time or maximum travel time savings and eliminating the vehicle route combination row and column of the cross-exchange matrix represented by the performed cross-exchange, and repeating modifying of the vehicle routing plan until all the vehicle route combinations in the cross-exchange matrix have been eliminated; in the processor, eliminating one of the vehicles in the vehicle routing plan; and in the processor, performing insertions of unrouted customers and exchanges of unrouted customers with routed customers, comprising: calculating a minimum time delay or travel time savings for feasible insertions of an unrouted customer into a vehicle route; saving, in a feasible insertion matrix representing unrouted customer to vehicle route combinations, a feasible insertion of the unrouted customer into the vehicle route resulting in a minimum time delay or maximum travel time savings; calculating the minimum time delay or travel time savings for feasible exchanges of an unrouted customer with a routed customer in a vehicle route; saving, in a feasible exchange matrix representing unrouted customer to vehicle route combinations, a feasible exchange of the unrouted customer into the vehicle route resulting in a minimum time delay or maximum travel time savings; modifying the vehicle routing plan by performing the saved feasible insertion resulting in the minimum time delay or maximum travel time saving and eliminating the row and column of the feasible insertion matrix and the feasible exchange matrix represented by the performed feasible insertion, and repeating modifying of the vehicle routing plan until all the unrouted customer to vehicle route combinations in the feasible insertion matrix have been eliminated; and modifying the vehicle routing plan by performing the remaining saved feasible exchange resulting in the minimum time delay or maximum travel time savings and eliminating the row and column of the feasible exchange matrix represented by the performed feasible exchange, and repeating modifying of the vehicle routing plan until all the unrouted customer to vehicle route combinations in the feasible exchange matrix have been eliminated.