We consider a vehicle routing problem with time window and dock capacity constraints(VRPTD).
In the 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. A route is said to be feasible if the route does not violate the dock capacity constraints and time window constraints at each customer. The objective of the problem is to minimize the total cost of the routes.
We propose an mixed integer programming(MIP) formulation of the problem. Since it 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.
