Publications - Preprint

Emergent hypercongestion in Vickrey bottleneck networks

agtPreprint
Dario Frascaria, Neil Olver and Erik Verhoef
Tinbergen Institute Discussion Paper TI 2020-002/VIII

Hypercongestion—the phenomenon that higher traffic densities can reduce throughput—is well understood at the link level, but has also been observed in a macroscopic form at the level of traffic networks; for instance, in morning rush-hour traffic into a downtown core. In this paper, we show that macroscopic hypercongestion can occur as a purely emergent effect of dynamic equilibrium behaviour on a network, even if the underlying link dynamics (we consider Vickrey bottlenecks with spaceless vertical queues) do not exhibit hypercongestion.

Improved approximation algorithms for inventory problems

approximationnetworkPreprint
Thomas Bosman and Neil Olver
Preprint (arXiv:1912.00101). Accepted to IPCO 2020.

We give new approximation algorithms for the submodular joint replenishment problem and the inventory routing problem, using an iterative rounding approach. In both problems, we are given a set of N items and a discrete time horizon of T days in which given demands for the items must be satisfied. Ordering a set of items incurs a cost according to a set function, with properties depending on the problem under consideration. Demand for an item at time t can be satisfied by an order on any day prior to t, but a holding
cost is charged for storing the items during the intermediate period; the goal is to minimize the sum of the ordering and holding cost. Our approximation factor for both problems is O(log log min(N,T)); this
improves exponentially on the previous best results.