Heuristic algorithms based on column generation for an online product shipping problem

In this paper, we consider a product shipping problem (PSP). Given a time horizon and a set of products, each with a weight, a release date, and a due date, the PSP calls for product shipping to be planned between a fixed origin–destination pair so as to minimize the total shipping cost. Given several types of boxes with different sizes and shipping costs, packing several products into one larger box may lead to cheaper shipping costs than sending them separately in smaller boxes. The online PSP is a problem with an online constraint that requires a decision to be made for each day without knowing about future demands or being able to change boxes that have already been packed and shipped. For the online PSP, we propose column-generation-based algorithms with six different criteria, incorporating ideas such as iterative surplus reduction, and heuristic column generation. In the computational experiments, we tested 15 types of online algorithms under each criterion. Computational results on three different sets of instances show that one type of the proposed algorithms with one of the six criteria called “regret with cost of remaining capacity” obtains high-quality solutions with average gaps of 3.4% over all the tested instances.