Déplacement de remblai - Lycée Raymond Savignac (Villefranche de Rouergue)

On s’intéresse ici à la planification des trajets des camions qui vont déplacer du remblai pour la
construction d’une autoroute.
Le tracé d’une autoroute fait passer celle-ci dans n zones z1,…,zn. Dans certaines de ces zones, il va falloir amener de la terre. Dans certaines autres zones, il va falloir enlever de la terre. Enfin, certaines zones ne nécessitent ni d’enlever ni d’amener de la terre : elles disposent de la juste quantité de terre nécessaire.
Au total, on considère que la somme des quantités de terre à enlever est égale à la somme des quantités de terre à amener.
Le problème consiste à déterminer un planning efficace de transport de terre, permettant de faire en sorte d’amener exactement la quantité nécessaire de terre dans chacune des zones ayant besoin de terre, et d’enlever toute la terre superflue de chacune des zones étant en excès de terre.