Portal de Periódicos da CAPES

The pallet-loading vehicle routing problem with stability constraints

2022; Elsevier BV; Volume: 302; Issue: 3 Linguagem: Inglês

10.1016/j.ejor.2022.01.035

1872-6860

María Teresa Alonso, Antonio Martínez-Sykora, Ramón Álvarez-Valdés, F. Parreño,

Lignin and Wood Chemistry

• We deal with an integrated routing and loading problem. • It is developed an integer linear model for the problem, with routing and packing constraints together. • It is also designed a more efficient decomposition procedure, relaxing some packing constraints. • An extensive computational study shows how the model and the decomposition work on a set of instances varying the number of customers, pallets, and weight distribution. This paper addresses an integrated routing and loading problem in which the pallets ordered by a set of customers have to be delivered by a set of trucks so that the total distance traveled is minimized. The problem has two main distinctive features. On the one hand, when assigning pallets to trucks, strict packing constraints, concerning axle weight, stability, and sequential loading, must be considered. On the other hand, split delivery is allowed. We have developed an integer linear model for the integrated problem, considering all routing and packing constraints. We have also designed a more efficient decomposition procedure in which some packing constraints are initially relaxed. Each time an integer solution is found in the search tree of the relaxed problem, it is checked to see whether it satisfies the remaining constraints and is therefore a feasible solution to the original problem. If it is not, a heuristic algorithm is first applied to rearrange the solution and, if it fails, an integer model is used, considering the packing problem for a single truck. If this also fails, a constraint is added to the relaxed problem to cut off the infeasible integer solution. An extensive computational study shows how the integer linear model and the decomposition procedure work on a set of instances varying the number of customers, the number of pallets, and their weight distribution.