×

A convoy scheduling problem. (English) Zbl 0734.90038

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.
Reviewer: H.Kise (Kyoto)

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
90B06 Transportation, logistics and supply chain management
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., Graphes (1985), Gauthier-Villars: Gauthier-Villars Paris · Zbl 0213.25702
[2] Garey, M.; Johnson, D. S., Computers and Intractability (1979), Freeman and Co: Freeman and Co San Francisco, CA
[3] Glover, F., Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13, 533-549 (1986) · Zbl 0615.90083
[4] Glover, F., Tabu search Part I, ORSA J. Comput., 1, 190-206 (1989) · Zbl 0753.90054
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.