French Army logistics
Multimodal transportation optimization software helps move military materiel, troops from bases to operation scenes.
By Thomas Barthoulot, Jean-Philippe Mangeot, Olivier Briant and Denis Naddef
The French Direction General de l’Armement, CATOD division, sought an answer to the following problem: In the event of military deployment, how can the French Army best transport – quickly and cost-effectively, using a mix of transportation modes – all necessary materiel and troops, from bases to operation scenes?
For background, consider:
- Most of the Army’s bases are in mainland France, while a certain number are in French territories and some friendly countries. For example, France may use navy bases in Djibouti and Dakar, and it has prepositioned forces on land bases in some friendly African countries.
- Transport may consist of a mix of land, air and sea.
- Air transport is done using a heterogeneous fleet, and transport may include rented aircraft such as large Antonov cargo transporters (in which case all rented aircraft are assumed to be in a given location, but one may use travel time to the demanding air base to differentiate them).
- Sea transport is done by ships, some of which may also be rented. Further, navy bases have very little buffer capacity, therefore the cargo must not arrive all at the same time.
- Land transport is done by convoy, and local regulations usually set a maximum number of trucks in such a convoy.
- There are priorities in terms of arrival time of goods and troops being transported.
Two key problems needed to be addressed:
- Given a fixed fleet, what is the minimum time necessary to have everything at the destination?
- Given a required deadline, what is the minimum cost to transport everything to the destination (including the option of renting cargo planes and ships)?
Among the constraints:
- Some troops and some materiel must arrive before others.
- Naval bases have very little buffer capacity.
- Ammunition cannot be transported in planes together with troops.
- Refueling the airplanes may be a problem.
- Pilots have very strict flying regulations. (By agreement with the customer, constraints on the pilots were not taken into account in the software solution described below.)
For answers, the French Direction General de l’Armement turned to a team headed by the four co-authors from the Societe TRYDEA and the University of Grenoble Alpes.
The operation research software solution, like many such modern O.R. solutions, was made up of three components:
Data interface, consisting of a map on which appear the different bases related to the instance to be solved. The bases may be edited and all necessary information provided.
Solution engine, which models the problem as an integer linear program (described in a following section).
Output interface, in which the solution is shown in an animated way on the map used in the data interface.
The interface uses as a background a map of the world, reduced to the part of interest in the study. Bases may be edited; Figure 1 shows the screen corresponding to the Djibouti naval base. The different goods to be transported have their own data screens (see Figures 2 and 3 for the description of a container and of a vehicle).
Figure 4 shows the screen for a certain plane type; the data specifies the maximum capacity, loading and unloading times, fuel consumption, refueling time, cost per hour. Capacity may depend on flight distance. Finally, a list of all goods to be transported is edited (see Figure 5).
A very simple instance of the problem is depicted in Figure 6 in which all bases are shown along with the possible transportation modes between them.
The solution model is a time-indexed graph. For each base there is a node for each time period. A node is therefore characterized by a base and a time, (b, t) refers to base b at time t. The time period used is one hour. One may have several arcs between (b, t) and (b, t + 1), two for each commodity, one for the part of that commodity remaining on the base or on the vessel during that period and one for those being loaded or unloaded. There is also an arc between (b, t) and (b, t + 1) for each type of vessel remaining on the base during that period; these are necessary to enable conservation of flow in the model described below.
Arcs between nodes of different bases (b1, t1) and (b2, t2), t2 > t1, are such that t2 – t1 is exactly the travel time using the corresponding mode of transportation. As already mentioned, we do not take into account the flight time of pilots. We assume that once the solution is found, logistics will be able to fulfill the necessary demand on pilots.
In the first phase we also ignore the bin packing problems related to the loads of the airplanes and the ships. Instead, we approximate the capacity (Later in this article we will explore what happens if we reach an infeasible solution in terms of transportation of goods and troops.)
Therefore the model is now quite simple: We use (0, 1) variables on arcs between bases to say if they are used or not. Other variables account for how much of every commodity travels on those arcs. The constraints are captured as flow-conservation equations on commodities and vessels (airplanes and ships) on each node, plus capacity constraints. These are all linear.
At first this may seem to be a completely intractable approach given the size of the graph, but three key ingredients make it work: i) sparse graph, ii) pricing and iii) branch and price.
We first use a very small subset of all the possible arcs. We use all arcs between consecutive nodes of a same base. We add some arcs between bases until the linear program has a feasible solution. Of course this is done in a clever way.
Pricing is a commonly used technique to deal with linear programs containing a huge number of variables. Using the dual prices obtained when solving the current linear program, one can check whether or not a variable, currently not taken into account, may improve the current solution if it was considered. If we find interesting variables, we add them to the linear program and resolve. The process is repeated until no new interesting variable is found. At this point we perform what is called a branching.
Branching consists in cutting the problem into a number, in general two, smaller problems, called subproblems. For example, our current solution may tell us to use half an Antonov between Base A at time t and Base B at time t + (θ). Consider one subproblem in which no Antonov is used between (A; t) and (B; t + (θ) and one subproblem in which at least one is used. We concentrate, in this phase, only on planes, ships and number of convoys; we do not care about the integrality of troops, containers, vehicles, etc.
The value of the objective function is a lower bound on the value of the optimum solution. We perform depth-first search exploration, favoring always the subproblem in which we take, in the example above, the side in which at least one Antonov is used. When backtracking we only explore subproblems that could improve by more than 2 percent the current best solution value. While performing these operations we continue the pricing process.
At the end of the branching phase we have an integer number of flights, shippings and convoys with their origins, destinations and departure dates. We then try to see whether or not we can fit within them everything that has to be transported. For ships and airplanes we use bin-packing heuristics. For ships, given their size, bin packing generally does not create problems. For airplanes, bin packing is not too difficult. Except for containers, no two articles may be stacked one over the other. Most of the time, no two articles may fit one next to the other, and the problem reduces to one-dimensional bin packing for which many efficient heuristics exist. In the case of very large cargo transporters, at most two may be side-by-side due to the size and because they have to be securely strapped. If we fail to fit all the freight, we reduce artificially the capacity of some vessels and repeat the whole process, keeping, in the sparse graph, all arcs that have been generated so far.
One term of the contract was that the linear programming solver had to be publicly available. We used CLP of the COIN-OR library. In most cases, a solution guaranteed to be not more than 2 percent of the optimal value is obtained in a few minutes. With a smart choice of the branching, we rarely needed to explore a branch other than the one of the initial descent. The solution time is more sensitive to the number of bases than to the amount of goods that have to be transported. It is not a surprise since an extra base increases the size of the underlying graph.
Once the solution is obtained, an output interface helps visualize at any time t the position of all vessels. One may see their type and content just by pointing on them. As shown in Figure 7, one may see that at a given time, the Airbus pointed at is in that position and contains seven containers, five motorcycles and one TRM 1000 (heavy truck).
In conclusion, the time-indexed graph model is a reasonable approach to the multimodal transportation problems, and we believe this approach could be used in environments other than military. It would be interesting to test the limits of this approach in terms of the number of bases it can handle, this time using commercial software for the linear programs.
Thomas Barthoulot (firstname.lastname@example.org) and Jean-Philippe Mangeot (email@example.com) are co-managers at TRYDEA, a software development company based in Nancy, France, that specializes in the field of simulation, operational research and information systems. The company has worked with the French Army since 2007.
Olivier Briant (firstname.lastname@example.org) is an associate professor in operations research with the School of Industrial Engineering, Grenoble Institute of Technology, and a researcher at the G-SCOP laboratory.
Denis Naddef (email@example.com), professor emeritus at Grenoble Institute of Technology, is a researcher at the G-SCOP laboratory. The Grenoble Institute of Technology is part of the University of Grenoble Alpes. The G-SCOP laboratory is a research laboratory affiliated with the University of Grenoble Alpes and the Centre National de la Recherche Scientifique.