A convoy scheduling problem (Q811336)

The scheduling problem considered is as follows. More than one convoys (a group of vehicles), each having different length and speed, have to travel along the same road to reach fixed destinations distant from the road. Each convoy has to leave its departure point during an imposed time interval and is not allowed to pass or cross any other convoy along the road. The problem is to determine a departure time for each convoy so as to minimize the total time needed, satisfying the above constraints. This paper discusses two different formulations for the above problem, the first one is based on mixed-integer programming, the other based on graphs. The latter leads to an application of a tabu search technique, and its performances has been compared with those of a mixed-integer programming package. It is concluded that the tabu search is efficient and can be used rather safely to get a good solution in reasonable time.