An Asymptotically Optimal Greedy Heuristic for the Multiperiod Single-sourcing Problem: The Cyclic Case

H. Edwin Romeijn, Dolores Romero Morales

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single-sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end-of-study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems.
The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single-sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end-of-study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems.
LanguageEnglish
JournalNaval Research Logistics
Volume50
Issue number5
Pages412–437
ISSN0894-069X
DOIs
StatePublished - 2003
Externally publishedYes

Cite this

@article{ebd51880de424757afb761530e15a771,
title = "An Asymptotically Optimal Greedy Heuristic for the Multiperiod Single-sourcing Problem: The Cyclic Case",
abstract = "The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single-sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end-of-study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems.",
author = "Romeijn, {H. Edwin} and Morales, {Dolores Romero}",
year = "2003",
doi = "10.1002/nav.10068",
language = "English",
volume = "50",
pages = "412–437",
journal = "Naval Research Logistics",
issn = "0894-069X",
publisher = "Wiley-Blackwell",
number = "5",

}

An Asymptotically Optimal Greedy Heuristic for the Multiperiod Single-sourcing Problem : The Cyclic Case. / Romeijn, H. Edwin; Morales, Dolores Romero.

In: Naval Research Logistics, Vol. 50, No. 5, 2003, p. 412–437.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - An Asymptotically Optimal Greedy Heuristic for the Multiperiod Single-sourcing Problem

T2 - Naval Research Logistics

AU - Romeijn,H. Edwin

AU - Morales,Dolores Romero

PY - 2003

Y1 - 2003

N2 - The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single-sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end-of-study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems.

AB - The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single-sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end-of-study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems.

U2 - 10.1002/nav.10068

DO - 10.1002/nav.10068

M3 - Journal article

VL - 50

SP - 412

EP - 437

JO - Naval Research Logistics

JF - Naval Research Logistics

SN - 0894-069X

IS - 5

ER -