Stochastic local search with learning automaton for the swap-body vehicle routing problem

- This paper presents the algorithm for the Swap-Body Vehicle Routing Problem (SB-VRP) that won the First VeRoLog Solver Challenge.
- The majority of the instances proposed during the challenge had its best known solution improved.
- All algorithmic components are discussed and analyzed, including the hybrid meta-heuristic, considered neighborhoods, subproblem optimization scheme and learning automaton.
- Neighborhoods are grouped into categories and all group combinations are evaluated.
- New SB-VRP instances are proposed.

This work presents the stochastic local search method for the Swap-Body Vehicle Routing Problem (SB-VRP) that won the First VeRoLog Solver Challenge. The SB-VRP, proposed on the occasion of the challenge, is a generalization of the classical Vehicle Routing Problem (VRP) in which customers are served by vehicles whose sizes may be enlarged via the addition of a swap body (trailer). The inclusion of a swap body doubles vehicle capacity while also increasing its operational cost. However, not all customers may be served by vehicles consisting of two bodies. Therefore swap locations are present where one of the bodies may be temporarily parked, enabling double body vehicles to serve customers requiring a single body. Both total travel time and distance incur costs that should be minimized, while the number of customers visited by a single vehicle is limited both by its capacity and by a maximum travel time. State of the art VRP approaches do not accommodate SB-VRP generalizations well. Thus, dedicated approaches taking advantage of the swap body characteristic are desired. The present paper proposes a stochastic local search algorithm with both general and dedicated heuristic components, a subproblem optimization scheme and a learning automaton. The algorithm improves the best known solution for the majority of the instances proposed during the challenge. Results are also presented for a new set of instances with the aim of stimulating further research concerning the SB-VRP.