A New Bounding Procedure for Transportation Problems with Stepwise Costs

Transportation planning often involves not only shipment costs but also setup costs associated with deploying vehicles or transport resources. In many practical logistics operations, this setup cost does not remain constant but increases stepwise with the number of vehicles used, reflecting economies of scale and scheduling thresholds. To capture this realistic feature, this study investigates the transportation problem with stepwise costs, where total costs combine shipment-dependent variable costs and vehicle activation costs. We develop a mixed-integer programming (MIP) model to represent the problem and propose an efficient algorithm based on variable-splitting reformulation and a row-and-column generation scheme. This approach dynamically introduces only the necessary variables and constraints, enabling the solution of large-scale instances that are otherwise computationally challenging. Numerical experiments show that the method produces high-quality solutions much faster than direct MIP solvers. The results highlight the model’s practical value in optimizing fleet utilization and transportation cost structures in real logistics and supply chain systems.