Minimizing late deliveries in a truck loading problem

In this work we address the problem of determining the optimal types of products and their quantities that should be loaded on a fleet of heterogeneous one or two level trucks so that the weighted sum of delivered products is maximized, with the weights being an exponential function of the lateness computed for each unit shipped. We propose a mixed integer linear formulation followed by a two-phase solution approach. During phase one the formulation is solved aiming at maximizing the weighted sum of products delivered, whereas for the second phase, the formulation is solved aiming at minimizing the number of trucks, while ensuring that the objective function attained in phase one is not compromised. A greedy heuristic is also proposed in order to better quantify the advantages of adopting the proposed exact approach with respect to solution quality. To assess the performance of the proposed approach we used two sets of test instances, a large set of randomly generated instances that resemble the practical application that motivated this research, and a small set of real instances provided by the company. The results of our computational experiments suggest that the proposed exact solution approach is very effective in solving realistic sized instances.