Scientific Program > Talks by Speaker > Errico Fausto

In this presentation we consider a new variant of the vehicle routing problem with time windows where the items (e.g., pallets or containers) delivered by a vehicle are positioned in stacks. Once the item has been placed, it cannot be moved, except for its delivery. Two types of items are considered: heavy or light. The fragility constraint forbids stacking a heavy item over a light one. We first consider the case of stacks of height 2. To solve this problem we develop different branch-price-and-cut algorithms. Some of them exploit theoretical results on the feasibility of a route subject to a fragility constraint. These theoretical results, as well as the branch-price-and-cut algorithms, are then generalized to the case of stacks of arbitrary height. Based on the Solomon's dataset for the vehicle routing problem with time windows, we generate a new dataset by varying several parameters such as the number of customers, the vehicle capacity, the ratio between the number of heavy and light items, the height of the stacks, etc. To assess the efficiency of our algorithm, we performed an extensive computational campaign. Preliminary results show that our algorithms are able to solve problem instances with up to 100 customers. Furthermore, the branch-price-and-cut algorithm featuring a bi-directional labeling algorithm to solve the subproblem in the column generation step seems to outperform the other algorithms.