Multidepot pickup and delivery problems in multiple regions: a typology and integrated model

• Author: Margaretha Gansterer,Alina G. Dragomir,Daniel Nicola,Adria Soriano
• Published date: 01 March 2018
• DOI: http://doi.org/10.1111/itor.12473
• Date: 01 March 2018

Intl. Trans. in Op. Res. 25 (2018) 569–597

DOI: 10.1111/itor.12473

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Multidepot pickup and delivery problems in multiple regions:

a typology and integrated model

Alina G. Dragomir, Daniel Nicola, Adria Soriano and Margaretha Gansterer

Faculty of Business, Economics and Statistics,Department of Business Administration, University of Vienna,

Oskar-Morgenstern-Platz 1, Vienna, 1090, Austria

E-mail: alina-gabriela.dragomir@univie.ac.at [Dragomir];daniel.nicola.naranjo@univie.ac.at [Nicola];

adria.soriano@univie.ac.at [Soriano]; margaretha.gansterer@univie.ac.at [Gansterer]

Received 7 June2017; received in revised form 4 September 2017; accepted 14 September 2017

Abstract

The rapid development experienced by the transportation industry in the past decades has led to many

configurations of networks and therefore to an explosion of variants in transportation problems, motivating

researchers to look at broader logistic problems, beyond the basic vehicle routing problems. This work

introduces a new type of problem scenario combining various attributes: a pickup and delivery problem

with multiple regions,multiple depots, and multiple transportation modes. We providedefinitions, a literature

review, and a step-by-step construction of the mathematicalmodels from a simple and well-known scenario to

the multiregion multidepot pickup and delivery problem (MR-MDPDP). For each step therelevant literature

is examined. Furthermore, we suggest possible extensions for prospective research.

Keywords:multidepot; pickup and delivery problem; multiregion; multimodal

1. Motivation

When thinking about realistic transportation networks, four main features come to mind: multiple

depots, multiple regions, paired pickup and deliveries,and multimodality. The first three arethe core

pillars of the problems we are examining. The literature so far has mostly looked at transportation

problems within one single region, although in reality transportation between different regions is

common practice since the beginning of modern globalization. Also, the so often made assumption

that the routingproblem can be simplified to a vehicle routing problem (VRP) might be justified from

an academic point of view, but is rather oversimplified for practical applications. Moreover, almost

all companies operating on a somewhat larger scale will have a network structure that contains

at least two depots, especially if transportation takes place between two geographically separated

regions. The multimodality aspect usually occurs by default by operating in different regions and

by the need for a switch of transportation modes for the last-mile delivery.

The copyright line for this article was changed on October 11, 2019 after original online publication.

C

2017 The Authors.

International Transactions in Operational Researchpublished by John Wiley & Sons Ltd on behalf of International Federation

of Operational Research Societies

This is an open access article under the terms of the Creative Commons Attribution License,which permits use, distribution and

reproduction in any medium, provided the original work is properlycited.

570 A. G. Dragomiret al. / Intl. Trans. in Op. Res. 25 (2018) 569–597

The great advancesin infrastructures, computation power, and solution algorithms haveincreased

the possibilities for all carriers, especially when facing long distance services. Therefore, we believe

that research in the transportation field should start to look at more complex problem structures,

like the ones described in this work. This paper is aimed to serve as an introduction to this new

kind of problems that have been hardly studied in their entirety in the literature. Furthermore, we

want to ascertain which works consider at least part of the main building blocks. We are therefore

specifically looking at multidepot pickup and delivery problems (PDPs) in multiple regions to

provide a foundation for further research in this field.

This research will not only benefit large transportation companies, but also small carriers who

are willing to form a collaborative network system to be able to compete with those big companies

in the long distance transportation market. The paper presents the transition from single-region

multidepot problems to multiregion PDPs, going through all the basic mathematical models and

existing literature in each field. This aims to provide a better understanding of the underlying

multiregion transportation problem. Our goal is to gradually introduce the building blocks of our

problem to allow the reader a deeper understanding of it. They are based on multidepot PDPs.

The paper is structured as follows: in Section 2, we will give a short problem introduction

including all necessary definitions. Section 3 gives an overview of the relevant literature. Sections 4

and 5 introduce in detail different variations of multidepot PDPs in one or several regions. We will

present mathematical models for each problem variation and give a literature review over work

already done in these areas including information about already used instances. In Section 6, we

conclude our work and in Section 7, we examine possible extensions to the basic problem presented

before.

2. Problem introduction

Before going into detail we need to provide some definitions:

We assume a two-dimensional plane. All nodes within this plane are represented by a complete

graph G(V,E),whereVrepresents a set of nodes and Arepresents a set of arcs connecting them.

A single arc connects a node ito a node j, with a transportation cost of dij. This cost is usually

represented by the distance between both end points of the arc.

Our definitions are based on the nomenclature provided by Parragh et al. (2008b). We define a

region as a group of nodes. The nodes in different regions are geographically separated. A pickup

node is a customer,located at some specific location, where goods haveto be collected by a vehicle. A

delivery node is a customer where goods have to be dropped off. In unpaired problems, the goods are

homogeneous and some quantity is collected and dropped off. There is no need to deliver specific

goods. We are either looking at unpaired or at paired pickup and delivery nodes. For unpaired

nodes the goods collected or dropped off are either transported between customers or have the

depot as their origin or destination. Paired nodes are called a request. A request can have its pickup

and delivery node within the same region or in different regions. A request therefore consists of

exactly one pickup and one delivery node with a specific quantity. The pickup node has to be served

before the delivery node. Since the goods are considered heterogeneous, the delivery node expects

exactly these goods and not any goods just like it. Two modes of transportation are considered.

Short-haul vehicles are used within a region. They are of small capacity and are mainly used for the

C

2017 The Authors.

International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation

of Operational Research Societies