A heuristic algorithm for a vehicle dispatching problem with time window rearrangement

An algorithm for a new vehicle dispatch model with time window rearrangement is proposed. The customer calls company and asks for service and time window in which service begin, and the company arrange the appropriate position for each customer without violating time window constraint. If the need of customer can not be satisfied, another time window is assigned to the customer. Firstly, the initial routings are constructed by some strategy in which the rearrangement of time window is considered, and then a tabu search algorithm is employed to improve the initial routings to minimize the total traveling cost. With the customer data produced randomly, the experiment results indicate that the algorithm produces encouraging performance.