Vehicle routing with restricted loading capacities.

Abstract

This paper considers a combination of vehicle routing and loading dock scheduling. Each route has a start instant at the depot and this instant is subject to capacity constraints for handling the route. This is an example of synchronized routing. Examples of physical constraints are a limited number of loading docks and a limited size of loading crews. During each route, there are also scheduling aspects being taken into account, such as the obedience of compulsory working time directives and meeting strict time windows for delivery. The complexity of this situation is tamed by a decomposition scheme where columns for a master problem (which takes the dock capacity into account) are generated by a routine based on dynamic programming. This column generations framework is assembled as a heuristic: after generating sufficient columns from the point of view of the linear relaxation of the master problem, one single instance of an integer linear program is solved. Strong evidence of the effectiveness of this approach is provided by cases from two large retailers, one based in The Netherlands and the other in the United Kingdom. The latter has the added challenge of an heterogeneous fleet with different dock capacity constraints.