A variable neighborhood search simheuristic for the multiperiod inventory routing problem with stochastic demands

• Date: 01 January 2020
• Published date: 01 January 2020
• Author: Aljoscha Gruler,Jesica de Armas,Angel A. Juan,Javier Panadero,José A. Moreno Pérez
• DOI: http://doi.org/10.1111/itor.12540

Intl. Trans. in Op. Res. 27 (2020) 314–335

DOI: 10.1111/itor.12540

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A variable neighborhood search simheuristic for the

multiperiod inventory routing problem with stochastic demands

Aljoscha Grulera, Javier Panaderoa, Jesica de Armasb,

Jos ´

e A. Moreno P´

erezcand Angel A. Juana

aIN3—Computer Science Department, Open University of Catalonia, Castelldefels,Spain

bDepartment of Economics and Business, Universitat PompeuFabra, Barcelona, Spain

cInstituto Universitario de Desarrollo Regional, Universidadde La Laguna, Tenerife, Spain

E-mail: agruler@uoc.edu [Gruler]; jpanaderom@uoc.edu[Panadero]; jesica.dearmas@upf.edu [de Armas];

jamoreno@ull.es [P´

erez]; ajuanp@uoc.edu [Juan]

Received 5 February2017; received in revised form 2 February 2018; accepted 8 March 2018

Abstract

The inventory routingproblem (IRP) combines inventory management and delivery route-planningdecisions.

This work presents a simheuristic approach that integrates Monte Carlo simulation within a variable neigh-

borhood search (VNS) framework to solve the multiperiod IRP with stochastic customer demands. In this

realistic variant of the problem, our goal is to establish the optimal refill policies for each customer–period

combination, that is, those individual refill policies that minimize the total expected cost over the periods.

This cost is the aggregation of both expected inventory and routing costs. Our simheuristic algorithm allows

to consider the inventory changes between periods generated by the realization of the random demands in

each period, which have an impact on the quantities to be delivered in the next period and, therefore, on

the associated routing plans. A range of computational experiments are carried out in order to illustrate the

potential of our simulation–optimization approach.

Keywords: multiperiod inventory routing problem; stochastic demands; variable neighborhood search; metaheuristics;

simheuristics

1. Introduction

Freight logistics and road transportation is of micro- and macroscopic importance. On the one

hand, the costs associated with moving and storing goods constitute a major economic factor for

organizations of different sectors (European Commission, 2016). On the other hand, the usage of

freight delivery vehicles leads to negative externalities such as air pollution, excessive noise, and

traffic congestion (United Nations, 2011; European Union, 2012; United States Environmental

Protection Agency, 2013). While practical and theoretical discussions related to freight logistics

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.

A. Gruler et al. / Intl. Trans. in Op. Res. 27 (2020) 314–335 315

and transportation (L&T) have long focused on the optimization of single company operations,

collaborativebusiness strategies are gaining increased attention (Ming et al., 2014; Ramanathanand

Gunasekaran, 2014). By sharing customer orders, information, and resources, companies operating

in the same supply chain hope to decrease overall value chain costs through centralized L&T

planning.

In this context, the concept of vendor-managed inventories (VMIs) is based on the transfer of

inventory management decisions to the central supplier. In a VMI, a total of nretail centers (RCs)

is stocked from a single supplier located at a central warehouse. Inventory levels at each RC and

necessary replenishment quantities delivered by the supplier are defined through final customer

demands. In noncollaborative supply chains, each RC defines its own replenishment levels based on

its own inventory management decisions, which directly affects the delivery route planning process

of the supplier. On the contrary, the implementation of VMI centralizes inventory and routing

decisions at the supplier, allowing the optimization of both decisions from an overall supply chain

perspective (Andersson et al., 2010; Coelho et al., 2013).

From an optimization point of view, this supply chain strategy is represented by the inventory

routing problem(IRP). This combinatorial optimization problem (COP) can be seen as an extension

to the well-known vehicle routing problem (VRP), making the problem setting NP-hard (Lenstra

and Kan, 1981; Caceres-Cruz et al., 2014). Due to the inherent complexity of the IRP, especially

metaheuristic solving methodologies are used to create inventory and routing plans for large-sized

IRP instances. As is the case of other COPs however, most solving frameworks are only capable of

providingoversimplified problem solutions,in which the natural uncertainty of most real-life systems

is left unaccounted for. This paper overcomes this drawback by presenting a simheuristic extension

of the popular and efficient variable neighborhood search (VNS) metaheuristic (Mladenovi´

cand

Hansen, 1997; Hansen et al., 2010) for solving the multiperiod IRP with stochastic customer

demands at each RC (Fig. 1). Simheuristic algorithms integrate a metaheuristic framework with

simulation to addressoptimization problems under uncertainty conditions (Juan et al., 2015; Grasas

et al., 2016).

Through the integration of Monte Carlo Simulation (MCS) inside the VNS procedure, our

simheuristic algorithm is able to consider random realizations of customer demands and, accord-

ingly,changes in the inventory levels, delivery orders, and routing plans over a multiperiodplanning

horizon. In this realistic variant of the problem, our goal is to establish the optimal refill policies for

each customer–period combination, that is, those individual refill policies that minimize the total

expected cost over the periods. This total expected cost is computed as the aggregation of both

expected inventory and routing costs.

This paper extends the workof Juan et al. (2014), who combined a simple multistart heuristic with

simulation to solve the single-period IRP under demand uncertainty. The main contributionsof this

work can be summarized as follows: (a) a new simheuristic algorithm for the multiperiod IRP with

stochastic demands is presented—the algorithm integrates simulation into a VNS metaheuristic;

and (b) the algorithm is tested in a series of computational experiments that illustrate its potential.

The remainder of this paper is structured as follows: relevant literature on the IRP is reviewed in

Section 2; a mathematical formulation of the multiperiod IRP with stochastic demands is provided

in Section 3; Section 4 outlines the proposed algorithm; a range of computational experiments are

described and analyzed in Section 5; finally, Section 6 concludes this work and highlights future

research lines.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies