Variable neighborhood search algorithms for pickup and delivery problems with loading constraints

Abstract

In this paper, we explore a capacitated vehicle routing problem with loading constraints and mixed linehauls and backhauls. The problem belongs to the subclass of pickup and delivery problems. To solve this problem, we describe a set of variable neighborhood search approaches whose shaking and local search phases rely on different neighborhood structures. Some of these structures were specially developed for this problem. All the strategies were implemented and exhaustively tested. The results of this computational study are discussed at the end of this paper.