A Hybrid Metaheuristic for Bin Packing Problem with Conflicts and Item-Dependent Bin Costs

Abstract

This paper investigates a new transportation problem arising in automotive parts milk-run logistics under a business contract in which the payment for each vehicle is determined by the maximum direct shipment cost among its assigned suppliers, plus a fixed stop-off charge for each additional supplier. The company determines the supplier groups, whereas the carriers arrange the visiting sequences, which do not affect the payment. We formulate this allocation problem as the Bin Packing Problem with Conflicts and Item-dependent Bin Costs (BPPCI), in which suppliers are treated as items and vehicles as bins, with the objective of minimizing total transportation cost under the contract subject to capacity and conflict constraints. We develop a mixed-integer linear programming model and two lower bounds, together with a hybrid metaheuristic that combines prefiltering, variable neighborhood descent, and reactive search within a greedy randomized adaptive search procedure. Computational experiments on 400 benchmark instances show that the proposed algorithm achieves an average gap of 4.91% relative to the tighter of the two lower bounds, with an average runtime of a few seconds. Component analysis examines the contributions of the main algorithmic components to solution quality and computational time. Three company cases involving 24, 53, and 106 suppliers show cost reductions of 12.76%, 11.19%, and 10.28%, respectively, relative to the corresponding manual plans.