On Modeling The Step Fixed-Charge Transportation Problem

Fixed-charge transportation problem (FCTP) deals with determining optimal quantities of goods to be shipped and the routes to be used to satisfy the customers’ demands at minimal total cost. The total cost contains a fixed component which is incurred for every route that is part of the solution along with the variable cost that is proportional to the amount shipped. Step fixed-charge transportation problem (SFCTP) is a variant of the FCTP where the fixed costs follow a step function. Staircase cost structure is very common in the shipping industry, national postal services and couriers, and materials management. In this work, we propose a MILP model for SFCTP. After explaining the mathematical model in sufficient detail, we demonstrate its applicability on a small numerical example. Using extensive computational experiments, we conclude that the problem is a very hard problem with much “higher degree” of polynomial complexity. We also report that the number of steps in the fixed component appears to be the dominant factor that significantly affects the computational time. Though the proposed MILP model is applicable for SFCTP, with minor modifications, it can be generalized and used for other network optimization problems that warrant modeling of staircase cost structures.