A distributed approach to improve inland water transportation addressing privacy and incremental improvements

Abstract

Currently, inland waterway shipping mainly includes barges and bulk transportation with little to no variation in volume, product, and route. Since transport over water emits less CO2 per tonne-km than road transport, a potential way to reduce CO2 emissions is to transport more containers via inland waterways. Large delays cause unreliability, which in their turn cause an opportunity cost and increased operational costs. These increased costs have a negative impact on the competitiveness of inland water transport with regards to road transport.

An alternative to the way planning is handled currently is by solving a Vehicle Rotaton Planning Problem (VRPP). The problem is solved by minimizing a cost function. For example, the total time spent in a port area (called the sojourn time) can be minimized.

Solving the VRPP results in a rotation plan that dictates the order in which vessels visit terminals and how many containers they should transport from one terminal to another. There are multiple ways to solve the VRPP, one of which is through the use of the Distributed Pseudotree Optimization Protocol (DPOP), where the vessel operators reach an optimal solution together by sharing only information about those variables that share the same constraints with other variables from other agents. An attractive property of DPOP is that it is possible to include privacy constraints in the algorithm, such that vessel operators only have to share minimal information about their journey and not lose a competitive advantage to one another. For example, the operators might only want to share variables like the arrival time, and only want to share it with operators that have the approximately same arrival time.

To ensure the problem can be solved and that the message size does not run out of memory bounds, the memory-bounded version of DPOP is implemented. Because Memory-Bounded Distributed Pseudotree Optimization Protocol (MB-DPOP) requires an exponential number of messages when the inference width is above a certain threshold, an alternative way of formulating and solving the problem is considered using the Maximum Gain Messaging (MGM) algorithm and a formulation that includes how much vessel operators are willing to change their current rotation plan for a lower overall cost. With this formulation, when something changes in the problem definition, the entire calculation does not have to be done again because starting from the previous solution is possible.

Two simulated case studies in the port area of Rotterdam are done to performed the performance of the algorithms. The results show while MB-DPOP can guarantee some level of privacy, it does not scale very well and is thus not really useful in real life. While the algorithm yields a global solution and can guarantee a certain level of privacy, its execution time is in the order of hours, even for relatively small problem sizes. Conversely, the MGM algorithm with reformulation scales quite well and can possibly guarantee some level of privacy as well with extension. While the algorithm does not come up with a global solution, it can be a decent trade off between a level of privacy, and scalable algorithms that are centralized, such as a genetic algorithm.