A variable neighborhood search heuristic algorithm for the double vehicle routing problem with multiple stacks

• Date: 01 January 2020
• Published date: 01 January 2020
• Author: André G. Santos,Marcone J. F. Souza,Ulisses E. F. Silveira,Jonatas B. C. Chagas
• DOI: http://doi.org/10.1111/itor.12623

Intl. Trans. in Op. Res. 27 (2020) 112–137

DOI: 10.1111/itor.12623

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A variable neighborhood search heuristic algorithm for the

double vehicle routing problem with multiple stacks

Jonatas B. C. Chagasa, Ulisses E. F. Silveirab, Andr´

e G. Santosband

Marcone J. F. Souzaa

aDepartamento de Computac¸˜

ao, Universidade Federal de OuroPreto, Ouro Preto, Brazil

bDepartamento de Inform´

atica, Universidade Federalde Vic¸osa, Vic¸osa, Brazil

E-mail: jonatas.chagas@iceb.ufop.br [Chagas]; ulisses.silveira@ufv.br [Silveira]; andre@dpi.ufv.br [Santos];

marcone@iceb.ufop.br [Souza]

Received 9 February2018; received in revised form 14 December 2018; accepted 14 December 2018

Abstract

This paper addresses the double vehicle routing problem with multiple stacks (DVRPMS) in which a fleet of

vehicles must collect items in a pickup region and then travel to a delivery region where all items are delivered.

The load compartment of all vehicles is divided into rows (horizontal stacks) of fixed profundity (horizontal

heights), and on each row, the unloading process must respect the last-in-first-out policy. The objective of

the DVRPMS is to find optimal routes visiting all pickup and delivery points while ensuring the feasibility

of the vehicle loading plans. We propose a new integer linear programming formulation, which was useful to

find inconsistencies in the results of exact algorithms proposed in the literature, and a variable neighborhood

search based algorithm that was able to find solutions with same or higher quality in shorter computational

time for most instances when compared to the methods already present in the literature.

Keywords: vehicle routing; pickup and delivery; loading constraints; mathematical formulation; variable neighborhood

search

1. Introduction

The double vehicle routing problem with multiple stacks (DVRPMS) arose in its simplest form as

the double traveling salesman problem with multiple stacks (DTSPMS), proposed by Petersen and

Madsen (2009), when a software company that set up routes in its intermodal traffic encountered

this problem with one of its customers.

In the DTSPMS, a single vehicle, which has its load compartment (container) divided into

rows (horizontal stacks) of fixed depth (horizontal heights), must collect all items spread in a

region known as pickup region and, henceforth, deliver all these collected items in another region,

denominated delivery region. All items have the same size and shape. The items are stored in the

C

2019 The Authors.

International Transactionsin Operational Research C

2019 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.

J. B.C. Chagas et al. / Intl. Trans. in Op. Res. 27 (2020) 112–137 113

Fig. 1. DTSPMS example—adapted from Iori and Riera-Ledesma (2015).

stacks as they are collected. It is important to state that the items are not stored on top of each

other, they are arranged in the same plane (container base) according to rows (horizontal stacks)

and their depths (horizontal heights). The items’ positions cannot be changed when they are already

inside the container, that is, the items should be stationary until their unloading. The delivery must

then respect the last-in-first-out (LIFO) policy. Thus, the delivery route is limited by the stack

configurations set up by the pickup route.

The DTSPMS is a variation of the pickup and delivery traveling salesman problem (TSP) with

multiple stacks (Cordeau et al., 2010; Cˆ

ot´

e et al., 2012; Sampaio and Urrutia, 2016), where the

pickup and delivery operationsmust be completely separate. This is due to the fact thatthe DTSPMS

arises in the context where the pickup and delivery regions are widely separated. In this way,

all items in the pickup region must be gathered prior to any unloading in the delivery region.

The transportation cost between the two regions is fixed and it is not considered as part of the

optimization problem. The problem has applicability in deliveries where items are loaded and

unloaded from the rear of the vehicle and item reallocation is prohibited due to the fact that the

items are heavy and/or fragile or the handling of these items is dangerous.

The objective of the DTSPMS is to find two Hamiltonian cycles, one for the pickup region and

the other for the delivery region, so that the sum of the distances traveled in both regions is the

minimum possible, respecting the precedence constraints imposed by the vehicle’s stacks.

Figure 1 depicts a feasible solution for the DTSPMS in a case involving 16 items. Each item is

associated with a pickup client and a delivery client (item 1 is associated with pickup client 1 and

with delivery client 1, item 2 is associated with pickup client 2 and with delivery client 2, and so

on). The container of this vehicle is divided into two stacks of height 8, that is, the container has

dimensions (2×8). The vehicle always starts its route in the pickup region at the vertex 0 (depot)

and, in this example, the vehicle visits customer 15, collects and stores the item in the first stack,

then visits customer 7, storing the item in the second stack, then customer 1 is visited and has his

item stored on the first stack. The gathering continues as shown in the figure until all customers

have been served and their items stored in the vehicle container. At the end, the vehicle returns to

the depot from where the entire container is transported tothe delivery region depot. In the delivery

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation of OperationalResearch Societies