| Article ID: | iaor19911583 |
| Country: | Netherlands |
| Volume: | 30 |
| Issue: | 1 |
| Start Page Number: | 1 |
| End Page Number: | 14 |
| Publication Date: | Jan 1991 |
| Journal: | Discrete Applied Mathematics |
| Authors: | De Werra D., Bovet J., Constatin C. |
A mixed-integer programming formulation is given for the problem of scheduling the movements of a collection of convoys along a road. Each convoy has a fixed speed and a given length; it cannot leave its origin before a given ready-time and it cannot reach its destination after a given deadline. This problem is NP-complete as can be seen easily. A heuristic approach based on tabu search is described. Computational results are presented for problems having up to 50 convoys.