Two-Stage Sort Planning for Express Parcel Delivery

The design and control of effective sortation systems have become more complex as both the volume of parcels and also the number of time-definite service options offered by parcel carriers have grown. In this paper, we describe 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 stations for final sort. We define a sort planning optimization problem in this setting using mixed-integer programming, where the primary objective is to minimize operational cost subject to machine capacity and parcel deadline constraints. Since a detailed optimization problem for sort planning based on flows in a time-space network is difficult to solve for realistically-sized instances, we develop an alternative formulation that is easier to solve and shares the same feasible region of first-stage sorting decisions with the detailed model; for many practical objective functions, this simpler model can be used to find cost-optimal solutions to the detailed model. We illustrate the proposed modeling approach and its effectiveness using real-world instances obtained from a large parcel express service provider.