Agile optimization of a two‐echelon vehicle routing problem with pickup and delivery

• Author: Leandro do C. Martins,Angel A. Juan,Patrick Hirsch
• Published date: 01 January 2021
• Date: 01 January 2021
• DOI: http://doi.org/10.1111/itor.12796

Intl. Trans. in Op. Res. 28 (2021) 201–221

DOI: 10.1111/itor.12796

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Agile optimization of a two-echelon vehicle routing problem

with pickup and delivery

Leandro do C. Martinsa,∗, Patrick Hirschband Angel A. Juana,c

aIN3 – Computer Science Department, Universitat Oberta deCatalunya, Barcelona, Spain

bInstitute of Production and Logistics, University of Natural Resources and Life Sciences, Vienna, Austria

cEuncet Business School, Terrassa,Spain

E-mail: leandrocm@uoc.edu [do C. Martins];patrick.hirsch@boku.ac.at [Hirsch]; ajuanp@uoc.edu [Juan]

Received 28 May2019; received in revised form 8 January 2020; accepted 10 March 2020

Abstract

In this paper, we consider a vehicle routing problem in which a fleet of homogeneous vehicles, initially lo-

cated at a depot, has to satisfy customers’ demands in a two-echelon network: first, the vehicles have to

visit intermediate nodes (e.g., a retail center or a consolidation center), where they deliver raw materials

or bulk products and collect a number of processed items requested by the customers in their route; then,

the vehicles proceed to complete their assigned routes, thus delivering the processed items to the final cus-

tomers before returning to the depot. During this stage, vehicles might visit other intermediate nodes for

reloading new items. In some real-life scenarios, this problem needs to be solved in just a few seconds or

even milliseconds, which leads to the concept of “agile optimization.” This might be the case in some res-

cue operations using drones in humanitarian logistics, where every second can be decisive to save lives. In

order to deal with this real-time two-echelon vehicle routing problem with pickup and delivery, an original

constructive heuristic is proposed. This heuristic is able to provide a feasible and reasonably good solution

in just a few milliseconds. The constructive heuristic is extended into a biased-randomized algorithm using

a skewed probability distribution to modify its greedy behavior. This way, parallel runs of the algorithm are

able to generate evenbetter results without violating the real-time constraint. Results show that the proposed

methodology generates competitive results in milliseconds, being able to outperform other heuristics from

the literature.

Keywords:agile optimization; disaster management; two-echelon vehicle routing problem;biased-randomized algorithms

1. Introduction

Real-time optimization, where decisions need to be made in just a few seconds or even milliseconds,

has many applicationareas in logistics. For example, in the event of disasters,real-time optimization

∗Corresponding author.

C

2020 The Authors.

International Transactionsin Operational Research C

2020 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.

202 L. do C. Martins et al. / Intl. Trans.in Op. Res. 28 (2021) 201–221

can be a life-savingdifferential. In this context, last-mile distribution logistics is relatedto the delivery

of urgently needed goods to areas where roads are blocked by extreme weather events, disasters, or

traffic congestion.

A motivational example is the distribution of drugs with drones in disaster situations. When

disasters occur, an effective system of drug management should be establishedby health agencies in

order to (a) ensure the efficient, cost-effective, and rational use of the drugs; (b) prevent and reduce

excess mortality and morbidity; and (c) promote a return to normalcy (McConnan, 2004). This

distribution process is based on selection, procurement, distribution, and use of pharmaceuticals

in primary health care (Quick et al., 1997). We focus on the distribution stage in which urgently

needed items (e.g., drugs) must be delivered to an affected area after a disaster occurred. These items

should be delivered from a near pharmacy or laboratory (intermediate node) as fast as possible. On

the other hand, these intermediate facilities should be served from a central warehouse or depot,

which holds raw material used to fabricate the processed items requested by the final users.

Due to the resulting poor transportation infrastructure after a disaster event, the affected areas

might become no longer accessible by conventional cargo vehicles. Therefore, the use of drones

can be seen as an effective way of delivering life-saving treatments directly to disaster locations.

Examples of drone delivery applications can be found in health care delivery, which includes the

safe delivery of medicines, vaccines, defibrillators, blood samples, disease test samples, and test kits

in remote areas out of reach (Balasingam, 2017; Scott and Scott, 2017).

In city logistics, a variant of the classical and well-known vehicle routing problem (VRP) is the

two-echelon VRP (2E-VRP), which can be found in several transportation systems. This multilevel

distribution system combines two delivery levels, in which the first level addresses the delivery

from the depot to intermediate facilities, while the second level regards the delivery from these

intermediate facilities to final customers. In the presented problem, a set of intermediate facilities

(e.g., pharmaceutical laboratories, PLs) holds a limited inventory of drugs needed in the disaster

areas and must be served with raw material from a single distribution center or depot. On the other

hand, these intermediate facilities must serve as fast as possible a set of final delivery points in the

affected area. The same fleet of dronesis employed in both delivery levels. Although the motivational

example for this paper is the drug distribution in disaster circumstances, similar problems can be

found in other situations, too.

To solve this problem in “real time” (i.e., a few seconds or even milliseconds), we propose a

fast constructive heuristic. This heuristic is then extended to a biased-randomized (BR) algorithm

as described, for example, in Grasas et al. (2017). Hence, we introduce the concept of “agile

optimization,” whichrefers to the massive parallelization of a BR version of a constructive heuristics.

Using parallel computing to solve real-life VRPs, the resulting methodology is able to provide in

milliseconds “good” solutions to medium- and large-sized instances (Juan et al., 2013b). The use of

BR techniques facilitates the design of powerful algorithms that can effectively be used to provide

real-time solutions in a range of situations that arise in dynamic and emergency contexts (Ghiani

et al., 2003).

The paper is arranged as follows. Section 2 presents a literaturereview on related topics; Section 3

describes the addressed problem; Section 4 introduces the proposed solution method; Section 5

presents an analysis of the results and a comparison between the proposed heuristic and other

solving methods; finally, Section 6 highlights the main conclusions of this work and proposes some

lines for future research.

C

2020 The Authors.

International Transactionsin Operational Research C

2020 International Federation ofOperational Research Societies