Recent years have brought significant changes in the operations of parcel transportation services, most notably due to the growing demand for e-commerce worldwide. Parcel sortation systems are used within sorting facilities in these transportation networks to enable the execution of effective consolidation plans with low per-unit handling and shipping costs. Designing and implementing effective parcel sort systems has grown in complexity as both the volume of parcels and also the number of time-definite service options offered by parcel carriers has grown. In this paper, we introduce approaches for planning two-stage parcel sort operations that explicitly consider time deadlines and sorting capacities. In two-stage sorting, parcels are sorted into groups by a primary sorter and then parcels from these groups are dispatched to secondary sort stations for final sort. We define a sort planning optimization problem in this setting using mixed-integer programming, where the objective is to minimize operational cost and workload imbalance subject to machine capacity and parcel deadline constraints. Since the full optimization problem can be difficult, we propose a decomposition approach for the problem that we show is guaranteed to generate optimal solutions for many practical objective functions. We illustrate the effectiveness of the proposed approach using real-world instances obtained from a large express delivery service provider.
School of Industrial and Systems Engineering, Georgia Institute of Technology, May 2020