  The package shipment problem requires to optimally co-design paths for both
packages and a heterogeneous fleet in a transit center network (TCN). Instances
arising from the package delivery industry in China usually involve more than
ten thousand origin-destination (OD) pairs and have to be solved daily within
an hour. Motivated by the fact that there is no interaction among different
origin centers due to their competitive relationship, we propose a novel
two-layer localized package shipment on a TCN (LPS-TCN) model that exploits
outsourcing for cost saving. Consequently, the original problem breaks into a
set of much smaller shipment problems, each of which has hundreds of OD pairs
and is subsequently modelled as a mixed integer program (MIP). Since the
LPS-TCN model is proved to be Strongly NP-hard and contains tens of thousands
of feasible paths, an off-the-shelf MIP solver cannot produce a reliable
solution in a practically acceptable amount of time. We develop a column
generation based algorithm that iteratively adds "profitable" paths and further
enhance it by problem-specific cutting planes and variable bound tightening
techniques. Computational experiments on realistic instances from a major
Chinese package express company demonstrate that the LPS-TCN model can yield
solutions that bring daily economic cost reduction up to 1 million CNY for the
whole TCN. In addition, our proposed algorithm solves the LPS-TCN model
substantially faster than CPLEX, one of the state-of-the-art commercial MIP
solvers.
