C&O Reading Group - Madison Van Dyk

Friday, October 20, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

Title: Fast Combinatorial Algorithms for Efficient Sortation

Speaker: Madison Van Dyk
Affiliation: University of Waterloo
Location: MC 6029

Abstract: Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes in typical hub-and-spoke fashion. In practice, such consolidation requires parcel-sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that, in the general model,  it is NP-hard to determine whether a feasible sortation plan exists. We discuss several special settings, where (near-)feasibility of a given sortation instance can be determined efficiently. The algorithms we propose are fast, and construct solutions as well as combinatorial witness set type lower-bounds that are reminiscent and extend those used in early work on degree-bounded spanning trees and arborescences.