Integer Programming Formulation for freight consolidation with a heterogeneous outsourced fleet, dead freight, and multiple delivery costs

In this paper, we consider a freight consolidation problem arising in the context of road transport. In this problem, a shipper has to deliver multiple items to its customers in a single day using outsourced vehicles from multiple carriers. Besides, each vehicle has a type, a capacity, a minimum contracted load, and a set of item types it can carry. Moreover, a vehicle can visit different customers whenever they are within an allowed maximum distance. Additionally, the prices depend on the type of the vehicle, the number of deliveries (different visited customers), the per unit of weight transportation cost of the consolidated items, and the dead freight corresponding to the unused availability of the vehicles' minimum contracted load. First, we show that the problem is NP-hard. Besides, we propose a mixed-integer programming formulation for the problem. Preliminary experiments using synthetic instances show that the distribution of customers into clusters favors better utilization of the vehicles and finding good solutions by increasing the number of items.