Hybrid heuristic for vehicle routing problem with due times

The vehicle routing problem with due times is considered. The vehicles are supposed to visit customers within the due times, and a penalty cost is imposed in case the vehicle arrives past the due times. A mixed integer programming formulation and a hybrid tabu search (HTS) is presented to minimize the weighted sum of the traveling time and the tardiness of the service customers. HTS is compared with other heuristics, the computational results show that HTS produces high quality results within a reasonable computing time.