Iterated local search and simulated annealing algorithms for the inventory routing problem

• Published date: 01 November 2018
• Author: Aldair Alvarez,Pedro Munari,Reinaldo Morabito
• DOI: http://doi.org/10.1111/itor.12547
• Date: 01 November 2018

Intl. Trans. in Op. Res. 25 (2018) 1785–1809

DOI: 10.1111/itor.12547

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Iterated local search and simulated annealing algorithms

for the inventory routing problem

Aldair Alvarez, Pedro Munari and Reinaldo Morabito

Department of Production Engineering, FederalUniversity of S ˜

ao Carlos, Rodovia WashingtonLu´

ıs - Km 235, 13565-905,

S˜

ao Carlos-SP, Brazil

E-mail: aldair@dep.ufscar.br [Alvarez]; munari@dep.ufscar.br [Munari]; morabito@ufscar.br [Morabito]

Received 13 December 2016; receivedin revised form 28 March 2018; accepted 28 March 2018

Abstract

This paper addresses the inventory routing problem (IRP), which consists in defining the customer visit

schedule, the deliveryquantities, and the vehicle routing plan to meet the demands of a set of customers over a

given time horizon. Weconsider the variant with a single item, a single supplier, multiple vehicles,and a finite

multiperiod planning horizon, minimizing the sum of inventory and travel costs. In addition, we address an

alternative objective function that minimizes the logistic ratio, defined as the total travel cost divided by the

total quantity delivered to customers. This second objective function, while more realistic in some logistics

settings, poses a challenge for integer programming models and exact methods because of its nonlinearity. To

our knowledge, no heuristic method has been proposedto address this objective in the IRP variant addressed

in this paper. To solve this problemwith each of these objective functions, we propose effective metaheuristic

algorithms based on iterated local search and simulated annealing. Computational experiments show that

these algorithms provide reasonably high-quality solutions in relativelyshort running times for both objective

functions when compared to other methods for well-known instances from the literature. Moreover, the

algorithms produce new best solutions for some of these instances.

Keywords:inventory routing problem; metaheuristics; iterated local search; simulated annealing; logisticratio

1. Introduction

Inventory control and distribution are strongly related activities in supply chain management,

especially in the context of vendor-managed inventory (VMI) business approaches. VMI allows

suppliers to manage the inventory levels and purchasing orders of their customers while reducing

logistics costs and improving the supply chain efficiency. Suppliers must ensure that customers

will not experience stockouts. The inventory routing problem (IRP) models this situation in an

integrated manner by combining two main decisions into one problem, namely vehicle routing and

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies

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

USA.

1786 A. Alvarez et al. / Intl. Trans.in Op. Res. 25 (2018) 1785–1809

inventory management. The IRP determines the best visit schedule, delivery quantities, and vehicle

routing plan to meet customer demands over the planning horizon.

Since a pioneering paper by Bell et al. (1983) who solved an integrated inventory management

and vehicle routing problem for the distribution of industrial gases, different variants of the IRP

have been studied. Dror et al. (1985) solved a long-term IRP using a rolling horizon strategy; later,

Dror and Ball (1987) approached the same problem by reducing the planning horizon to a single-

period problem, defining costs reflecting long-term decisions, safety inventory levels, and subsets

of customers to be considered. Campbell and Savelsbergh (2004) developed a two-phase hybrid

approach for an IRP minimizing transportation costs only. In their approach, the visit schedule

and delivery sizes are determined solving an integer linear model while the delivery routes are

constructed with heuristic algorithms. Savelsbergh and Song (2007, 2008) focused on the IRP with

continuous moves, motivated by a real-life application that includes pickup and delivery routes

spanning multiple time periods. The authors developed heuristic and hybrid algorithms to solve

the problem. Archetti and Speranza (2016) showed the importance of the IRP by comparing the

heuristic solution of the IRP with the solution obtained by sequentially solving to optimality an

inventory management problem and then a vehicle routing problem.

Other extensions of the IRP havebeen addressed by Le et al. (2013), who used a column generation

based heuristic to solve an IRP with perishability constraints. Cordeau et al. (2014) solved the

multiproduct IRP with a three-phase decomposition-based heuristic algorithm. Abdelmaguid et al.

(2009) proposed heuristic algorithms for an IRP with backlogging. Shiguemoto and Armentano

(2010) developed a tabu search metaheuristic for an integrated production–distribution problem,

which was also applied to the IRP. Benoist et al. (2011) and Singh et al. (2015) solveddifferent IRPs

by applying heuristic algorithms to real-life distributionproblems in the bulk gas industry.For other

studies on applications and variants of the IRP, see the comprehensive reviews by Andersson et al.

(2010) and Coelho et al. (2014).

Regarding solution approaches for basic IRP variants (Coelho et al., 2014), hybrid methods com-

bining metaheuristic algorithms with mathematical programming have been proposed by Archetti

et al. (2012), Coelho et al. (2012), Adulyasak et al. (2014b), and Santos et al. (2016). Exact methods

have also been presentedin recent years, based on branch-and-cut (B&C) and branch-price-and-cut

(BPC) algorithms (Archetti et al., 2007, 2014; Solyalı and S¨

ural, 2011; Coelho and Laporte, 2013a,

2014; Desaulniers et al., 2016). As observed in the computational results presented in these papers,

exact approaches are able to solve only small- to medium-sized instances within running times

acceptable in practice.

Recently, Archetti et al. (2017) presented a BPC-based method to address the IRP with an

alternative objective function based on the logistic ratio. This criterion consists in minimizing the

average cost to deliver one unit of product, rather than the standard total cost given by the sum of

distribution and inventoryholding costs. The logistic ratio can be of great valuein practical contexts,

as it can better reflect the efficiency of the distribution process. Despite its practical motivation,

only a few studies have dealt with this kind of objective function in the context of IRPs (Benoist

et al., 2011; Singh et al., 2015; Archetti et al., 2017). The logistic ratio imposes challenges to integer

programming formulations and exact methods, as it corresponds to a nonlinear function.

In this paper, we address a single-item, multivehicle, and multiperiod IRP. We propose two

metaheuristic algorithms based on iterated local search (ILS) and simulatedannealing (SA) to solve

this variant. ILS combines a local search heuristic with a perturbation algorithm to escape from

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies