Variable neighborhood search algorithms for the vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls

• Author: Telmo Pinto,Cláudio Alves,José Valério de Carvalho
• Date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12509
• Published date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 549–572

DOI: 10.1111/itor.12509

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Variable neighborhood search algorithms for the vehicle

routing problem with two-dimensional loading constraints

and mixed linehauls and backhauls

Telmo Pinto, Cl´

audio Alves and Jos´

eVal

´

erio de Carvalho

Centro Algoritmi da Universidadedo Minho, Escola de Engenharia, Universidade do Minho, 4710-057 Braga, Portugal

E-mail: telmo@dps.uminho.pt [Pinto]; claudio@dps.uminho.pt [Alves]; vc@dps.uminho.pt [Val´

erio de Carvalho]

Received 4 February2017; received in revised form 23 October 2017; accepted 23 December 2017

Abstract

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 improveefficiency 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.

Keywords:routing; loading constraints; backhauls; variable neighborhood search

1. Introduction

The vehicle routing problem with mixed linehauls and backhauls (VRPMB) consists of a vehicle

routing problem in which the set of customers is divided into two distinct sets: the set of linehaul

and the set of backhaul customers. The former set is characterized by a demand of given product

for each customer while the latter set is composed of customers having a given supply quantity of

goods. The transportation of loads can be only performed from or to the depot, that is, customers

cannot supply goods to each other. Additionally, customers can be visited indistinctly, whichmeans

that backhaul customers can be visited before or between the visit of the linehaul ones.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

550 T. Pinto et al. / Intl. Trans. in Op. Res. 27 (2020) 549–572

Some of the solution methods for the VRPMB are based on insertion heuristics (Casco et al.,

1988; Salhi and Nagy, 1999). Generally, these heuristics start by obtaining a solution for the vehicle

routing problem only for linehaul customers. Then, each backhaul customer is assigned to a route

point aiming to minimize the associated insertion cost. The expression used to compute this cost

relies on different criteria, such as the number of deliveries or quantity to be delivered after a given

insertion point, or the distance to the depot. Wade and Salhi (2002) suggested that the user can

define a given threshold: one backhaul customer can only be inserted in a given arcif the percentage

of delivered items is below the mentioned threshold.

The VRPMB belongs to the class of vehicle routing problemswith backhauls (VRPB). This class,

in turn, belongs to the general pickup and delivery problems (GPDP; Parragh et al., 2008a). The

problems belonging to the VRPB class share the same feature: the transportation is only performed

from or to the depot. This means that the depot is simultaneously the only source of goods to

be delivered and the only destination of the picked goods. Other pickup and delivery problems

(PDP) consider that the transportation of goods can be performed between customers, that is, the

customers are the source and/or the destination of goods. These problems are known as vehicle

routing problems with pickup and deliveries (Parragh et al., 2008b).

Some problems belonging to the GPDP consider the inclusion of loading and unloading con-

straints. However, there are very few approaches for PDP with two- or three-dimensional items.

Malapert et al. (2008) considered the PDP with two-dimensional items. Sequential constraints are

imposed, which mean that unloading an item must be performedin a straight move, without moving

other items. These constraints are also known as LIFO (last-in, first-out) constraints. Considering

the three-dimensional case,a PDP with loading constraints is addressed by Bart ´

ok and Imreh (2011).

No sequential loading and unloading constraints are considered. In contrast, LIFO constraints are

considered in the PDP proposed by M¨

annel and Bortfeldt (2016). The authors claim that these

constraints do not eliminate the reloading effort. Therefore, additional constraints are explicitly

considered in order to tackle this issue. These additional constraints are combined in five variants

of the problem. In these three PDP contributions with loading constraints, the transportation of

loads is performed between the nodes, that is, between the customers. On the other hand, there are

situations considering the depot as the only source and as the only destinationof all loads (Bortfeldt

et al., 2015).

In this paper, we address a vehicle routing problem with two-dimensional loading constraints

and mixed linehauls and backhauls (2L-VRPMB). Generally, this problem corresponds to the

integration of the vehicle routing problem with the two-dimensional bin packing problem (Iori

et al., 2007; Gendreau et al., 2008; Zachariadis et al., 2009), in which customers are divided into

backhaul and linehaul customers.

Some examples of VRPMB applications were defined in the literature. Casco et al. (1988) pre-

sented a grocery scenario where supermarkets were linehaul customers, while the grocery suppliers

could be seen as backhaul customers. More recently, Belmecheri et al. (2013) identified this problem

in a French transport companythat delivers goods to the customers and it collects goods from other

customers to the depot. In the 2L-VRPMB, only two dimensions are considered. These situations

arise when the fragility, weight, or nature of cargo do not allow stacking. Gendreau et al. (2008)

identified some of these situations: kitchen appliancesand catering equipment. Other real-world situ-

ations include furniture and construction equipment. Frequently,loading and unloading operations

are performed by lift trucks, and thus, the rotation of items in the loading area may be forbidden.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies