The growing cost of transportation and distribution pushes companies, especially small and medium transportation enterprises, to form partnership and to exploit economies of scale. On the other hand, to increase their competitiveness on the market, companies are asked to consider preferences of the customers as well. Therefore, tools for logistics management need to manage collective resources, as many depots and heterogeneous fleets, providing flexible preference handling at the same time. In this paper we tackle a pickup and delivery vehicle routing problem involving such aspects; customers place preferences on visiting time (represented as soft time windows), and their violation is allowed at a price. Our interest in this problem stems from an ongo- ing industrial project. First we propose an exact branch-and-price algorithm, having as a core advanced dynamic programming techniques. Then we analyze through a computational campaign the impact of soft time windows management on the optimal solution in terms of both routing and overall distribution costs. Our experiments show that our approach can solve instances of real size, and clarify the practical usefulness of soft time windows management.
We face the issue of finding alternative paradigms for the resolution of generic Mixed Integer Programs (MIP), by considering the perspective option of general purpose solvers which switch to decomposition methods when pertinent. Currently, the main blocking factor in their design is the problem of automatic decomposition of MIPs, that is to produce good MIP decompositions algorithmically, looking only at the algebraic structure of the MIP instance. We propose to employ Dantzig–Wolfe reformulation and machine learning methods to obtain a fully data driven automatic decomposition framework. We also design strategies and introduce algorithmic techniques in order to make such a framework computationally effective. An extensive experimental analysis shows our framework to grant substantial improvements, in terms of both solutions quality and computing time, with respect to state-of-the-art automatic decomposition techniques. It also allows us to gain insights into the relative impact of different techniques. As a side product of our research, we provide a dataset of more than 31 thousand random decompositions of MIPLIB instances, with 121 features, including computations of their root node relaxation.