Intra Market Optimization for Express Package Carriers with Station to Station Travel and Proportional Sorting

The flow of packages and documents, called splits, of an express package carrier consists of picking up the splits at costumers' locations by a courier and bringing them to a local station for sorting. Next the splits are transported to a major regional sorting facility called the ramp. At the ramp splits can be sorted again and then they depart to a hub. From this hub they are moved to the destination ramp, where the entire process repeats in the reverse order. In this work we focus on the afternoon and evening operations concerning with stations and the ramp. We deal with the sorting and transportation decisions among these locations. If splits are sorted in a particular sequence at the stations, then resorting at the ramp is not required, which can bring cost savings. The most important decisions are: (1) which splits to aggregate at the stations, and (2) what is the most efficient transportation among locations. In this work we enhance the existing model by considering several options for modeling the sorting process at stations and the ramp, as well as the possibility of vehicles traveling from one station to another station to consolidate volume before proceeding to the ramp. We model these processes by means of a dynamic program, where time periods represent time slices in the afternoon and evening. The overall model is solved by approximate dynamic programming, where the value function is approximated by a linear function. Further strategies are developed to speed up the algorithm and decrease the time needed to find feasible solutions. The methodology is tested on several instances from an international express package carrier. Our solutions are substantially better than the current best practice and the best solutions obtained from an integer programming formulation of the problem.