With increasing concern over the environment, shipment consolidation has become one of a main initiative to reduce CO₂ emissions and transportation cost among the logistics service providers. Increased delivery time caused by shipment consolidation may lead to customer’s order cancellation. Thus, order cancellation should be considered as a factor in order uncertainty to determine the optimal shipment consolidation policy. We develop mathematical models for quantity-based and time-based policies and obtain optimality properties for the models. Efficient algorithms using optimal properties are provided to compute the optimal parameters for ordering and shipment decisions. To compare the performances of the quantity-based policy with the time-based policy, extensive numerical experiments are conducted, and the total cost is compared.