Paper Image

Efficient algorithms for parcel sortation in logistic networks

Published on:

9 November 2023

Primary Category:

Discrete Mathematics

Paper Authors:

Madison Van Dyk,

Kim Klause,

Jochen Koenemann,

Nicole Megow


Key Details

Proposes math model for optimal sort point allocation in parcel networks

NP-hard even when underlying network is a tree

Local search algorithm solves single-source tree instances optimally

1-additive approximation for general tree networks

2-approximation algorithm for star networks

AI generated summary

Efficient algorithms for parcel sortation in logistic networks

This paper proposes a mathematical model to determine an optimal allocation of sort points in parcel logistic networks. The goal is to minimize the maximum number of sort points required at any warehouse. The problem is shown to be NP-hard, even when the underlying network is a tree. For tree networks, the paper presents several polynomial-time algorithms and approximation results. A simple local search algorithm solves single-source instances optimally in O(n log^2 n) time. For multi-source trees, a 1-additive approximation algorithm is given. Lower bounds based on disjoint cuts are used to analyze performance. For star networks, a 2-approximation algorithm is provided.

Answers from this paper


No comments yet, be the first to start the conversation...

Sign up to comment on this paper

Sign Up