A tabu search algorithm for the vehicle routing problem with time window and dock capacity constraints

We consider a vehicle routing problem with time window and dock capacity constraints (VRPTD). In most traditional models of vehicle routing problems with time window (VRPTW), each customer must be assigned to only one vehicle route. However demand of a customer may exceed the capacity of one vehicle, hence at least two vehicles may need to visit the customer. We assume that each customer has its own dock capacity. Hence, the customer can be served by only a limited number of vehicles simultaneously. Given a depot, customers, their demands, their time windows and dock capacities, VRPTD is to get a set of feasible routes which pass the depot and some customers such that all demands of each customer are satisfied. Since VRPTD is NP-hard, a meta-heuristic algorithm is developed. The algorithm consists of two procedures; the route construction procedure and the route scheduling procedure. We tested the algorithm on a number of instances and computational results are reported.