Multi-Commodity Flow and Storage

Whenever we think of vehicle route planning, we think of networks on maps and on how to find the best routes.  In this case, we make frequent use of flow analyses and observe the flow of traffic on a map, for instance.  Flow analyses are mathematically elegant and they can be applied not only on geographical maps, but also over time.

Time-space networks consider the geographical space per point in time and are therefore able to represent a progression. This is where the flow analysis starts: this “space-time” is considered as a network and balance equations are used  in order to describe the flows of traffic not just across the locations but also over time.

Whereas part 1 of our series was a  general introduction to time-space networks, these will be applied realistically in this article. This is because until now two very simple assumptions have been made:

  • only traffic flows were modelled
  • and for every specific customer demand, an edge was generated in the network (and thus a potential delivery).

In reality, though, the issue is all about specific goods with demand that can fluctuate. What’s more, you do not normally need just-in-time delivery at the exact time the demand exists. Instead there are warehouses which need to be restocked in time.

Goods flow through the network

Mathematically, it makes no difference whether vehicles or goods “flow” through the network. What is clearly more interesting is that the aspect of storage has been introduced. This has two effects:

  • Each customer has his/her stock at any time.
  • The network becomes considerably larger as deliveries can be effected more flexibly

The detailed formulation for this can be found in our whitepaper

So far we have modelled a direct connection between demand and delivery. This will now be substituted by storage: the actual demand can now be met from the stocks, the delivery now replenishes the stocks instead. Therefore, we need to revise one or two constraints:

  • (C1.2) The flow maintenance now includes the stocks and exists per commodity group
  • (C2.2) Previously, the demand was modelled as the upper limit of the trucks in transit - this modeling is no longer relevant
  • (C3.2) There is always missed demand when there is negative stock

This adjustment means that deliveries can be effected more flexibly because when exactly the stocks are replenished results from the stock and demand. However, unlike before, it can include several points in time. More potential connections in time-space networks are created accordingly.

  • (AUX2.2) Deliveries in the network are now potentially useful on a far more frequent basis.

With these additions (as well as the details relating to them in our whitepaper), we have acheived one thing: Demand modelling on the level of commodity groups. This includes the demand for trucks as well as the generation of optimal travel schedules with the benefit of flexibility, which enables storage.

To model delivery plans at commodity group level incluing storage, time-space networks are an elegant solution which allow us to study the benefit of mathematical optimization more closely.