Mixed integer programming models for dispatching vehicles at a container terminal

This paper presents scheduling models for dispatching vehicles to accomplish a sequence of container jobs at the container terminal, in which the starting times as well as the order of vehicles for carrying out these jobs need to be determined. To deal with this scheduling problem, three mixed 0–1 integer programming models, Model I, Model II and Model III are provided. We present interesting techniques to reformulate the two mixed integer programming models, Model I and Model II, as pure 0–1 integer programming problems with simple constraint sets and present a lower bound for the optimal value of Model I. Model III is a complicated mixed integer programming model because it involves a set of non-smooth constraints, but it can be proved that its solutions may be obtained by the so-called greedy algorithm. We present numerical results showing that Model III is the best among these three models and the greedy algorithm is capable of solving large scale problems.