Sponsor: La Poste
Context
La Poste, the French postal service, uses small containers to transport mail (imagine bins that can hold around 200 letters). There are 3 types of containers, called “A”, “B” and “C”.
A geographical imbalance between mail senders and receivers results in a shortage of empty containers for some sites, and an overabundance for others. Every day, some sites declare themselves to be in need of containers, and other sites declare themselves to be suppliers. Offers and requests are expressed in kind (type of container “A”, “B” or “C”) and in quantity (number of containers requested or offered).
Each type of container has a very specific use, adapted to letter formats and the sorting machines that process them. They are not interchangeable. The same site can therefore offer one type of container and request another. Of course, a site can also be a requester or supplier of several types of containers.
With a few random exceptions, the supply of one type of container is not equal to the demand for the same type of container. This is why human intervention is required to balance supply and demand for each type of container, either by clipping demand or by using the reserves of certain “storage” sites. Thus, for the problem submitted, supply is exactly equal to demand for each type of container.
Empty containers are unmarked. A request can be met by any supplier, and possibly by several suppliers. In this sense, it's more a supply problem than a “return logistics” problem.
Suppliers supply requesters using trucks. A truck can carry any type of container, and several types of containers can be loaded on the same truck.
The capacity of a truck is expressed in terms of its floor area, and the unit of area used is that of a container, given that all containers have the same surface area on its floor, whatever their type. So an empty truck has a carrying capacity of 52 empty containers.
Truck transport falls into 2 categories: regular line haulage and supplementary line haulage.
Regular lines are set up to transport mail between La Poste sites. They are made up of stages carried out by a single truck. Each stage connects a departure site and an arrival site, the departure site of a stage corresponding to the arrival site of the previous stage if this one exists. A stage of a transport line is characterized by a stage number (which is a strictly positive integer), a departure site, an arrival site, a departure time and an arrival time. Stage points can be suppliers and requesters or not.
At each stage point, all or part of a truck can be unloaded and/or loaded to capacity. Some of these stages are not saturated, but have residual carrying capacity (measured in terms of the number of empty containers, as previously stated). Then it is possible to complete a load of full containers (with mail) with additional empty containers.
Supplementary lines can be set up between all La Poste sites to transport empty containers. Consisting of a single stage, they all use the same type of truck with a capacity of 52 empty containers. There is a choice of departure times, with the arrival time determined by the departure time and the distance to be covered. A supplementary line can be used by several trucks.
Certain well-identified sites are also hubs. A hub is a junction point between different transport lines, and therefore between different trucks. This junction point is a staging point for the lines in question, but not necessarily the first or last of a transport line. At a hub, all or part of a truck can be unloaded to be reloaded onto one or more other trucks belonging to other transport lines. Hubs can be suppliers and requesters or not.
This transshipment operation can be carried out between any type of line (regular or supplementary). There is no transshipment between successive stages of a regular line. All or part of a truck's load can be retained from one stage to the next, without any handling of the load.
A transshipment is realized in exactly one hour whatever the number of transshipments to be realized at the same time.
A supplementary line can be created between any two La Poste sites, but it will only make sense if its departure site and its arrival site are either a requesting site, a supplying site or a hub.
Objectives
The cost of transport (of empty containers) on a regular line is zero, as it is paid for by the full containers.
The cost of transport on a supplementary line is proportional to the distance (with a “floor” cost for short distances) and is proportional to the number of trucks, whatever the quantities transported. In this sense, the problem differs significantly from a “multi-commodity flow problem”.
The cost of transshipment is a constant value, whatever the quantity unloaded and the number of trucks to be reloaded. But we'll consider that there are as many transshipments as there are trucks to unload.
The aim is to satisfy all requests and offers expressed within a defined global time slot at minimum cost. This is a global time slot, and there are no time or deadline constraints specific to each site.