The transportation problem with packing constraints

Abstract

We address a new variant of the transportation problem, where a set of different commodities, available at several supply nodes with different prices, are distributed to demand nodes using a set of heterogeneous vehicle fleets available at each supply node. Since each commodity has a specific weight, there is a packing constraint due to the total capacity of each vehicle. The objective of this problem is to minimize the total supply cost, which includes the purchase cost of commodities and the fixed transportation cost based on the traveled distance. This novel variant of the transportation problem poses computational challenges due to its combinatorial structure. To tackle these challenges and solve large-scale instances to near-optimality in reasonable CPU times, we propose a variable neighborhood search algorithm. The proposed algorithm partitions the problem into smaller, more manageable problems to be solved. In order to initialize this methodology, we also propose a decomposition heuristic that prescribes initial feasible solutions in CPU times ranging from 0.6 s to 133.2 s on average with average optimality gaps ranging from 0.09% to 4.62%. Our proposed methodology provides solutions with 0.06% to 3.78% optimality gaps on average within average CPU times ranging from 0.2 s to 386.2 s, while the commercial solvers are unable to find integer solutions or to solve most of the instances to optimality within one CPU-hour time limit.