This repository contains a Python implementation of the RLPW algorithm proposed in [1] and also an implementation of the algorithm proposed by Schrijver et al. [2]. Our algorithm improves upon the runtime of the latter by a factor of K, where K is the number of non-zero demands. The runtime of the proposed algorithm is thus O(n^2).
The proposed algorithm is located in proposed/ring_loading.py.
In can be invoked using the function ring_loading(n, demands), where demands is a SymmetricMatrix containing the demands.
The implementation of Schrijver et al.'s algorithm can be found in schrijver/ring_loading.py, where it, too, can be invoked
using the ring_loading(n, demands) function. Note that here, demands is a list containing all non-zero demands.
Runtime experiments can be conducted using runtime_test.py in the experiments directory.
The results given in [1] were derived from the computational results in result.json, which contains tuples
of type (seed, time_ms).
[1] Nikolas Klug, 2022. Computing Minimal Solutions to the Ring Loading Problem. Term Paper.
[2] Schrijver, A., Seymour, P. and Winkler, P., 1999. The Ring Loading Problem. SIAM review, 41(4), pp.777-791.