This work presents a hybrid approach to solve a distribution problem of a Portuguese company in the automotive industry. The objective is to determine the minimum cost for daily distribution operations, such as collecting and delivering goods to multiple suppliers. Additional constraints are explicitly considered, such as time windows and loading constraints due to the limited capacity of the fleet in terms of weight and volume. An exhaustive review of the state of the art was conducted, presenting different typology schemes from the literature for the pickup and delivery problems in the distribution field. Two mathematical models were integrated within a matheuristic approach. One model reflects the combination of the Vehicle Routing Problem with Simultaneous Delivery and Pickup with the Capacitated Vehicle Routing Problem with Time Windows. The second one aims to pack all the items to be delivered onto the pallets, reflecting a three-dimensional single bin size Bin Packing Problem. Both formulations proposed—a commodity-flow model and a formulation of the Three-Dimensional Packing Problem must be solved within the matheuristic. All the approaches were tested using real instances from data provided by the company. Additional computational experiments using benchmark instances were also performed.

Despite other variants of the standard knapsack problem, very few solution approaches have been devised for the multiscenario max-min knapsack problem. The problem consists in finding the subset of items whose total profit is maximized under the worst possible scenario. In this paper, we describe an exact solution method based on column generation and branch-and-bound for this problem. Our approach relies on a reformulation of the standard compact integer programming model based on the Dantzig-Wolfe decomposition principle. The resulting model is potentially stronger than the original one since the corresponding pricing subproblem does not have the integrality property. The details of the reformulation are presented and analysed together with those concerning the column generation and branch-and-bound procedures. To evaluate the performance of our algorithm, we conducted extensive computational experiments on large scale benchmark instances, and we compared our results with other state-of-the-art approaches under similar circumstances. We focused in particular on different relevant aspects that allow an objective evaluation of the efficacy of our approach. From different standpoints, the branch-and-price algorithm proved to outperform the other state-of-the-art methods described so far in the literature.

In this paper, a capacitated vehicle routing problem with mixed linehauls and backhauls is presented. The addressed problem belongs to the subclass of pickup and delivery problems. Loading and sequencing constraints are also considered. These constraints arise in many real-world situations, and can improve efficiency since backhaul customers do not need to be delayed in a route when it is possible to load their items without rearrangements. The suggested approach is based on an insertion heuristic presented in the literature but extended to tackle the explicit consideration of loading constraints. Different strategies are presented and tested. An exhaustive computational study is performed on instances adapted from benchmark instances for integrated routing and loading problems.