METHOD AND SYSTEM FOR FAST LOCAL SEARCH AND INSERTION HEURISTICS FOR VEHICLE ROUTING

摘要

Methods and systems reduce vehicle travel time in a vehicle routing plan having vehicle routes which include vehicles and customers serviced by the vehicles, including executing cross-exchanges of the customers for combinations of vehicle routes in the vehicle routing plan. Executing cross-changes includes determining a travel time or time savings of executed cross-exchanges, saving a cross-exchange resulting in a minimal travel time or maximum travel time savings for vehicle route combinations, and modifying the vehicle routing plan by performing the saved cross-exchange resulting in the minimal travel time or maximum travel time savings until all vehicle route combinations are exhausted. The methods and systems may further reduce a number of vehicles in the vehicle routing plan including, eliminating one of the vehicles in the vehicle routing plan, and performing insertions of unrouted customers and exchanges of unrouted customers with routed customers. Performing insertions and exchanges of unrouted customers includes determining a minimum time delay or travel time savings for feasible insertions of an unrouted customer into a vehicle route, saving a feasible insertion of the unrouted customer into the vehicle route resulting in a minimum time delay or maximum travel time savings, determining the minimum time delay or maximum travel time savings for feasible exchanges of an unrouted customer into a vehicle route, saving 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 savings until all the unrouted customer to vehicle route combinations are exhausted, and modifying the vehicle routing plan by performing the saved feasible exchange resulting in the minimum time delay or maximum travel time savings until all the unrouted customer to vehicle route combinations are exhausted.