Biased‐randomized iterated local search for a multiperiod vehicle routing problem with price discounts for delivery flexibility

• Author: A. Estrada‐Moreno,M. Savelsbergh,J. Panadero,A. A. Juan
• DOI: http://doi.org/10.1111/itor.12625
• Published date: 01 July 2019
• Date: 01 July 2019

Intl. Trans. in Op. Res. 26 (2019) 1293–1314

DOI: 10.1111/itor.12625

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Biased-randomized iterated local search for a multiperiod

vehicle routing problem with price discounts for delivery

flexibility

A. Estrada-Morenoa,c,M.Savelsbergh

b,A.A.Juan

a,c and J. Panaderoa,c

aIN3 – Computer Science Department, Open University of Catalonia, Av. CarlFriedrich Gauss 5, 08860 Barcelona, Spain

bH. Milton Stewart School of Industrial and Systems Engineering, GeorgiaInstitute of Technology, 755 Ferst Drive,NW,

Atlanta, GA 30332, USA

cEuncet Business School, Ctra. de Terrassa a Talamanca Km.3, 08225 Barcelona, Spain

E-mail: aestradamo@uoc.edu [Estrada-Moreno];martin.savelsbergh@isye.gatech.edu [Savelsbergh];

ajuanp@uoc.edu [Juan]; jpanaderom@uoc.edu[Panadero]

Received 10 June2018; received in revised form 17 December 2018; accepted 28 December 2018

Abstract

The multiperiod vehicle routing problem (MPVRP) is an extension of the vehicle routing problem in which

customer demands have to be delivered in one of several consecutive time periods, for example, the days of a

week. Weintroduce and explore a variantof the MPVRP in which the carrier offers a price discount in exchange

for delivery flexibility. The carrier’s goal is to minimize total costs, which consist of the distribution costs and

the discounts paid. A biased-randomized iterated local search algorithm is proposed for its solution. The

two-stage algorithm first quickly generatesa number of promising customer-to-period assignments, and then

intensively exploresa subset of these assignments. An extensive computational study demonstratesthe efficacy

of the proposed algorithm and highlights the benefit of pricing for delivery flexibility in different settings.

Keywords:vehicle routing problem; multiperiod; price discounts; biased-randomized heuristics; iterated local search

1. Introduction

The multiperiod vehicle routing problem (MPVRP; Francis et al., 2008) is an extension of the well-

known vehicle routing problem (VRP; Toth and Vigo, 2014; Caceres-Cruz et al., 2015) in which

customer demands have to be delivered in one of the several consecutive time periods, for example,

the days of a week. As observed in Archetti et al. (2015), in many practical settings there may

exist some flexibility in the time of service and effectively exploiting that flexibility may result in

significant cost savings. Therefore, we study a variant of the MPVRP in which a service provider

offers a price discount in exchange for delivery flexibility. More specifically, we consider a setting

in which customers place orders to be delivered during a planning horizon consisting of several

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.

1294 A. Estrada-Moreno et al. / Intl. Trans. in Op. Res. 26 (2019) 1293–1314

Fig. 1. An example of the benefits of delivery flexibility.

consecutive days. Each customer specifies a demand quantity, a delivery location, and a preferred

delivery day. If a customer has more than one demand during the planning period, each demand

will be considered separately (i.e., as a different “virtual” customer). The service provider offers

a discount to its customers in exchange for flexibility in the timing of the delivery, for example,

the delivery is allowed to be made one day early or one day late (one day before or one day after

the preferred day). This can be viewed as a for m of collaboration because both parties benefit: a

customer benefits directly by receiving a discount, and the service provider benefits indirectly by

being able to exploit the additional flexibility to reduce distribution costs.

Settings in which delivery flexibility is provided in exchange for a price discount are becoming

more common as such agreements are found in many provider–customer contracts. This may be

due, in part, by the changing landscape of city logistics (Savelsbergh and Van Woensel, 2016).

City councils encourage (or force) service providers to reduce the number of trips into the city,

which may be achieved by serving customers in the same district/region in a single trip. Delivery

flexibility is required for service providers to do so. While the “pricing for delivery flexibility” has

been analyzed in the context of production planning (Li et al., 2012), there is a lack of similar

studies in the VRP context. The primary goal of our research is to answer the following question:

By how much can total costs be reduced for different levels of delivery flexibility and for different

levels of price discounts?

We illustrate the potential benefits of delivery flexibility on a small example in Fig. 1. An optimal

delivery plan for three consecutivedays, when deliveries haveto take place on the preferred delivery

day, is shown in Fig. 1a. In order to simplify the visualization, we assume that the delivery routes on

a particular day start and end at a different location. Figure 1b illustrates how delivering to some

customers a day early or a day late can reduce the distribution costs.

To solve instances of this MPVRP variant, we propose a two-stage algorithm that combines iter-

ated local search (ILS; Lourenc¸o et al., 2010) with biased-randomization (BR) techniques (Grasas

et al., 2017). The algorithm will be shown to work well (i.e., producing near-optimal solutions) in

a variety of settings, from the most restricted setting, in which a customer can only be served on

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies