Time aggregation for network design to meet time-constrained demand

N Boland, A Ernst, Thomas Kalinowski, M Rocha de Paula, M Savelsbergh, G Singh

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

We study a network design problem inspired by a strategic planning problem encountered in the Hunter Valley Coal Chain. Demand is given in the form of freight that is available from a specific date and has to be transported from multiple origins to a single destination before its deadline. It is possible to temporarily store freight at certain intermediate locations along the way from origins to destination. The objective is to determine minimum-cost capacity expansions required on the links and nodes of the network, if any, so as to be able to transport all freight within its given time windows.

A natural mixed integer programming formulation with a daily granularity quickly becomes computationally intractable. We investigate the potential of time aggregation to overcome the computational challenges. By aggregating consecutive time periods, a smaller instance is obtained, which can be solved more easily and provides a lower bound on the optimal value.

A carefully designed iterative disaggregation scheme identifies a time aggregation that yields an optimal solution to the original problem. An extensive computational study demonstrates the efficacy of the proposed approach.
Original languageEnglish
Title of host publicationMODSIM2013, 20th International Congress on Modelling and Simulation
EditorsJ Piantadosi, R S Anderssen, J Boland
Place of PublicationCanberra ACT Australia
PublisherModelling and Simulation Society of Australia and New Zealand
Pages3281-3287
Number of pages7
ISBN (Electronic)9780987214331
Publication statusPublished - 2013
Externally publishedYes
EventInternational Congress on Modelling and Simulation 2013: Adapting to Change: the multiple roles of modelling - Adelaide Convention Centre, Adelaide, Australia
Duration: 1 Dec 20136 Dec 2013
Conference number: 20
https://www.mssanz.org.au/modsim2013/

Conference

ConferenceInternational Congress on Modelling and Simulation 2013
Abbreviated titleMODSIM2013
CountryAustralia
CityAdelaide
Period1/12/136/12/13
Internet address

Keywords

  • Network design problem
  • integer programming
  • time indexed models
  • time aggregation

Cite this

Boland, N., Ernst, A., Kalinowski, T., Rocha de Paula, M., Savelsbergh, M., & Singh, G. (2013). Time aggregation for network design to meet time-constrained demand. In J. Piantadosi, R. S. Anderssen, & J. Boland (Eds.), MODSIM2013, 20th International Congress on Modelling and Simulation (pp. 3281-3287). Canberra ACT Australia: Modelling and Simulation Society of Australia and New Zealand.
Boland, N ; Ernst, A ; Kalinowski, Thomas ; Rocha de Paula, M ; Savelsbergh, M ; Singh, G. / Time aggregation for network design to meet time-constrained demand. MODSIM2013, 20th International Congress on Modelling and Simulation. editor / J Piantadosi ; R S Anderssen ; J Boland. Canberra ACT Australia : Modelling and Simulation Society of Australia and New Zealand, 2013. pp. 3281-3287
@inproceedings{8f143a3b478d4c3499250042fc49f26c,
title = "Time aggregation for network design to meet time-constrained demand",
abstract = "We study a network design problem inspired by a strategic planning problem encountered in the Hunter Valley Coal Chain. Demand is given in the form of freight that is available from a specific date and has to be transported from multiple origins to a single destination before its deadline. It is possible to temporarily store freight at certain intermediate locations along the way from origins to destination. The objective is to determine minimum-cost capacity expansions required on the links and nodes of the network, if any, so as to be able to transport all freight within its given time windows.A natural mixed integer programming formulation with a daily granularity quickly becomes computationally intractable. We investigate the potential of time aggregation to overcome the computational challenges. By aggregating consecutive time periods, a smaller instance is obtained, which can be solved more easily and provides a lower bound on the optimal value.A carefully designed iterative disaggregation scheme identifies a time aggregation that yields an optimal solution to the original problem. An extensive computational study demonstrates the efficacy of the proposed approach.",
keywords = "Network design problem, integer programming, time indexed models, time aggregation",
author = "N Boland and A Ernst and Thomas Kalinowski and {Rocha de Paula}, M and M Savelsbergh and G Singh",
year = "2013",
language = "English",
pages = "3281--3287",
editor = "J Piantadosi and Anderssen, {R S} and J Boland",
booktitle = "MODSIM2013, 20th International Congress on Modelling and Simulation",
publisher = "Modelling and Simulation Society of Australia and New Zealand",
address = "New Zealand",

}

Boland, N, Ernst, A, Kalinowski, T, Rocha de Paula, M, Savelsbergh, M & Singh, G 2013, Time aggregation for network design to meet time-constrained demand. in J Piantadosi, RS Anderssen & J Boland (eds), MODSIM2013, 20th International Congress on Modelling and Simulation. Modelling and Simulation Society of Australia and New Zealand, Canberra ACT Australia, pp. 3281-3287, International Congress on Modelling and Simulation 2013, Adelaide, Australia, 1/12/13.

Time aggregation for network design to meet time-constrained demand. / Boland, N; Ernst, A; Kalinowski, Thomas; Rocha de Paula, M; Savelsbergh, M; Singh, G.

MODSIM2013, 20th International Congress on Modelling and Simulation. ed. / J Piantadosi; R S Anderssen; J Boland. Canberra ACT Australia : Modelling and Simulation Society of Australia and New Zealand, 2013. p. 3281-3287.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Time aggregation for network design to meet time-constrained demand

AU - Boland, N

AU - Ernst, A

AU - Kalinowski, Thomas

AU - Rocha de Paula, M

AU - Savelsbergh, M

AU - Singh, G

PY - 2013

Y1 - 2013

N2 - We study a network design problem inspired by a strategic planning problem encountered in the Hunter Valley Coal Chain. Demand is given in the form of freight that is available from a specific date and has to be transported from multiple origins to a single destination before its deadline. It is possible to temporarily store freight at certain intermediate locations along the way from origins to destination. The objective is to determine minimum-cost capacity expansions required on the links and nodes of the network, if any, so as to be able to transport all freight within its given time windows.A natural mixed integer programming formulation with a daily granularity quickly becomes computationally intractable. We investigate the potential of time aggregation to overcome the computational challenges. By aggregating consecutive time periods, a smaller instance is obtained, which can be solved more easily and provides a lower bound on the optimal value.A carefully designed iterative disaggregation scheme identifies a time aggregation that yields an optimal solution to the original problem. An extensive computational study demonstrates the efficacy of the proposed approach.

AB - We study a network design problem inspired by a strategic planning problem encountered in the Hunter Valley Coal Chain. Demand is given in the form of freight that is available from a specific date and has to be transported from multiple origins to a single destination before its deadline. It is possible to temporarily store freight at certain intermediate locations along the way from origins to destination. The objective is to determine minimum-cost capacity expansions required on the links and nodes of the network, if any, so as to be able to transport all freight within its given time windows.A natural mixed integer programming formulation with a daily granularity quickly becomes computationally intractable. We investigate the potential of time aggregation to overcome the computational challenges. By aggregating consecutive time periods, a smaller instance is obtained, which can be solved more easily and provides a lower bound on the optimal value.A carefully designed iterative disaggregation scheme identifies a time aggregation that yields an optimal solution to the original problem. An extensive computational study demonstrates the efficacy of the proposed approach.

KW - Network design problem

KW - integer programming

KW - time indexed models

KW - time aggregation

UR - http://www.mssanz.org.au/modsim2013/A1/boland4.pdf

M3 - Conference Paper

SP - 3281

EP - 3287

BT - MODSIM2013, 20th International Congress on Modelling and Simulation

A2 - Piantadosi, J

A2 - Anderssen, R S

A2 - Boland, J

PB - Modelling and Simulation Society of Australia and New Zealand

CY - Canberra ACT Australia

ER -

Boland N, Ernst A, Kalinowski T, Rocha de Paula M, Savelsbergh M, Singh G. Time aggregation for network design to meet time-constrained demand. In Piantadosi J, Anderssen RS, Boland J, editors, MODSIM2013, 20th International Congress on Modelling and Simulation. Canberra ACT Australia: Modelling and Simulation Society of Australia and New Zealand. 2013. p. 3281-3287