Shipment Consolidation with Multiple Shipping Methods Under Nonlinear Cost Structures

• 成果类型: Article
• 署名作者: Xu, Zhou; Li, Feng; Chen, Zhi-Long
• 署名单位: Hong Kong Polytechnic University; Huazhong University of Science & Technology; University System of Maryland; University of Maryland College Park
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2023.4835
• 发表日期: 2024
• 关键词: shipment consolidation; nonlinear cost structures; long-haul and short-haul shipping; First-Due-First-Delivered policy; No-Wait policy; dynamic programming; Approximation algorithms

摘要

We study a shipment consolidation problem commonly faced by companies that outsource logistics operations and operate in a commit-to-delivery mode. It involves delivering a given set of orders to their destinations by their committed due times using multiple shipping methods at the minimum total shipping and inventory cost. The shipping cost is generally nonlinear in shipping quantity and can be represented by a subadditive piecewise linear function. We investigate two shipping scenarios, one involving long-haul shipping only and the other involving joint long-haul and short-haul shipping. We develop analytical results and solution algorithms for the shipment consolidation problem under each shipping scenario. The problem under the first shipping scenario is shown to be strongly NP-hard. We find that a simple policy, called the First-Due-First-Delivered (FDFD) policy, which assigns orders with earlier delivery due times to shipping methods with earlier destination arrival times, is very effective. This policy enables us to develop a polynomial time algorithm, which not only solves the problem under the concave shipping cost structure optimally but also achieves a performance guarantee of 2 for the problem under the general subadditive shipping cost structure. For the problem under the second shipping scenario, we extend the FDFD policy for long-haul shipping and derive another policy, called the No-Wait policy, for short-haul shipping. We use these policies to develop a polynomial time algorithm and analyze its performance guarantee. Our computational experiments show that the algorithm significantly outperforms a commercial optimization practical situations.