Premium
Variable neighborhood search algorithms for the vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls
Author(s) -
Pinto Telmo,
Alves Cláudio,
Valério de Carvalho José
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12509
Subject(s) - vehicle routing problem , computer science , mathematical optimization , variable neighborhood search , backhaul (telecommunications) , heuristic , variable (mathematics) , routing (electronic design automation) , pickup , local search (optimization) , algorithm , mathematics , metaheuristic , artificial intelligence , computer network , telecommunications , mathematical analysis , wireless , image (mathematics)
In this paper, we explore a vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls. The addressed problem belongs to a subclass of general pickup and delivery problems. Two‐dimensional loading 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 earlier and without rearrangements of the items. To tackle this problem, we report extensive computational experiments to assess the performance of different variants of the variable neighborhood search approaches. The initial solution relies on an insertion heuristic. Both shaking and local search phases resort to 10 neighborhood structures. Some of those structures were specially developed for this problem. The feasibility of routes is heuristically obtained with a classical bottom‐left based method to tackle the explicit consideration of loading constraints. All the strategies were implemented and exhaustively tested on instances adapted from the literature. The results of this computational study are discussed at the end of this paper.