A Probabilistic Analysis of the Multi-period Single-sourcing Problem

H. Edwin Romeijn, Dolores Romero Morales

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The multi-period single-sourcing problem (MPSSP) is the problem of finding an assignment, over time, of customers to warehouses such that each customer is assigned to exactly one warehouse in each period, subject to capacity constraints, such that the total transportation and inventory costs are minimized. We propose a general stochastic model for the MPSSP, and derive a tight condition on this stochastic model under which the MPSSP is feasible with probability 1 when the number of customers goes to infinity. This result can be used to generate suitable experimental data. Moreover, we show that the normalized optimal value of the problem converges almost surely to a constant, for which we provide an explicit expression; this property can be useful in constructing asymptotically optimal heuristics for the problem. The rate of convergence to the limiting value is illustrated empirically.
The multi-period single-sourcing problem (MPSSP) is the problem of finding an assignment, over time, of customers to warehouses such that each customer is assigned to exactly one warehouse in each period, subject to capacity constraints, such that the total transportation and inventory costs are minimized. We propose a general stochastic model for the MPSSP, and derive a tight condition on this stochastic model under which the MPSSP is feasible with probability 1 when the number of customers goes to infinity. This result can be used to generate suitable experimental data. Moreover, we show that the normalized optimal value of the problem converges almost surely to a constant, for which we provide an explicit expression; this property can be useful in constructing asymptotically optimal heuristics for the problem. The rate of convergence to the limiting value is illustrated empirically.
LanguageEnglish
JournalDiscrete Applied Mathematics
Volume112
Issue number1-3
Pages301–328
ISSN0166-218X
DOIs
StatePublished - 2001
Externally publishedYes

Keywords

    Cite this

    @article{b0f2c39785dd47beaa1ed181ebd03b55,
    title = "A Probabilistic Analysis of the Multi-period Single-sourcing Problem",
    abstract = "The multi-period single-sourcing problem (MPSSP) is the problem of finding an assignment, over time, of customers to warehouses such that each customer is assigned to exactly one warehouse in each period, subject to capacity constraints, such that the total transportation and inventory costs are minimized. We propose a general stochastic model for the MPSSP, and derive a tight condition on this stochastic model under which the MPSSP is feasible with probability 1 when the number of customers goes to infinity. This result can be used to generate suitable experimental data. Moreover, we show that the normalized optimal value of the problem converges almost surely to a constant, for which we provide an explicit expression; this property can be useful in constructing asymptotically optimal heuristics for the problem. The rate of convergence to the limiting value is illustrated empirically.",
    keywords = "Probabilistic analysis, Generalized Assignment Problem, Dynamic assignments",
    author = "Romeijn, {H. Edwin} and Morales, {Dolores Romero}",
    year = "2001",
    doi = "10.1016/S0166-218X(00)00320-6",
    language = "English",
    volume = "112",
    pages = "301–328",
    journal = "Discrete Applied Mathematics",
    issn = "0166-218X",
    publisher = "Elsevier BV North-Holland",
    number = "1-3",

    }

    A Probabilistic Analysis of the Multi-period Single-sourcing Problem. / Romeijn, H. Edwin; Morales, Dolores Romero.

    In: Discrete Applied Mathematics, Vol. 112, No. 1-3, 2001, p. 301–328.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - A Probabilistic Analysis of the Multi-period Single-sourcing Problem

    AU - Romeijn,H. Edwin

    AU - Morales,Dolores Romero

    PY - 2001

    Y1 - 2001

    N2 - The multi-period single-sourcing problem (MPSSP) is the problem of finding an assignment, over time, of customers to warehouses such that each customer is assigned to exactly one warehouse in each period, subject to capacity constraints, such that the total transportation and inventory costs are minimized. We propose a general stochastic model for the MPSSP, and derive a tight condition on this stochastic model under which the MPSSP is feasible with probability 1 when the number of customers goes to infinity. This result can be used to generate suitable experimental data. Moreover, we show that the normalized optimal value of the problem converges almost surely to a constant, for which we provide an explicit expression; this property can be useful in constructing asymptotically optimal heuristics for the problem. The rate of convergence to the limiting value is illustrated empirically.

    AB - The multi-period single-sourcing problem (MPSSP) is the problem of finding an assignment, over time, of customers to warehouses such that each customer is assigned to exactly one warehouse in each period, subject to capacity constraints, such that the total transportation and inventory costs are minimized. We propose a general stochastic model for the MPSSP, and derive a tight condition on this stochastic model under which the MPSSP is feasible with probability 1 when the number of customers goes to infinity. This result can be used to generate suitable experimental data. Moreover, we show that the normalized optimal value of the problem converges almost surely to a constant, for which we provide an explicit expression; this property can be useful in constructing asymptotically optimal heuristics for the problem. The rate of convergence to the limiting value is illustrated empirically.

    KW - Probabilistic analysis

    KW - Generalized Assignment Problem

    KW - Dynamic assignments

    U2 - 10.1016/S0166-218X(00)00320-6

    DO - 10.1016/S0166-218X(00)00320-6

    M3 - Journal article

    VL - 112

    SP - 301

    EP - 328

    JO - Discrete Applied Mathematics

    T2 - Discrete Applied Mathematics

    JF - Discrete Applied Mathematics

    SN - 0166-218X

    IS - 1-3

    ER -