A decomposition approach for commodity pickup and delivery with time-windows under uncertainty

Lavanya Marla, Cynthia Barnhart, Varun Biyani

Research output: Contribution to journalArticle

Abstract

We consider a special class of large-scale, network-based, resource allocation problems under uncertainty, namely that of multi-commodity flows with time-windows under uncertainty. In this class, we focus on problems involving commodity pickup and delivery with time-windows. Our work examines methods of proactive planning, that is, robust plan generation to protect against future uncertainty. By a priori modeling uncertainties in data corresponding to service times, resource availability, supplies and demands, we generate solutions that are more robust operationally, that is, more likely to be executed or easier to repair when disrupted. We propose a novel modeling and solution framework involving a decomposition scheme that separates problems into a routing master problem and Scheduling Sub-Problems; and iterates to find the optimal solution. Uncertainty is captured in part by the master problem and in part by the Scheduling Sub-Problem. We present proof-of-concept for our approach using real data involving routing and scheduling for a large shipment carrier’s ground network, and demonstrate the improved robustness of solutions from our approach.

Original languageEnglish (US)
Pages (from-to)489-506
Number of pages18
JournalJournal of Scheduling
Volume17
Issue number5
DOIs
StatePublished - Sep 20 2014

Fingerprint

Pickups
Decomposition
Scheduling
Resource allocation
Repair
Uncertainty
Pickup and delivery
Time windows
Commodities
Availability
Planning
Routing

Keywords

  • Decomposition
  • Multi-commodity routing and scheduling
  • Robust routing and scheduling
  • Uncertainty

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Cite this

A decomposition approach for commodity pickup and delivery with time-windows under uncertainty. / Marla, Lavanya; Barnhart, Cynthia; Biyani, Varun.

In: Journal of Scheduling, Vol. 17, No. 5, 20.09.2014, p. 489-506.

Research output: Contribution to journalArticle

@article{1e288198f62f4e12b69455be82b8c137,
title = "A decomposition approach for commodity pickup and delivery with time-windows under uncertainty",
abstract = "We consider a special class of large-scale, network-based, resource allocation problems under uncertainty, namely that of multi-commodity flows with time-windows under uncertainty. In this class, we focus on problems involving commodity pickup and delivery with time-windows. Our work examines methods of proactive planning, that is, robust plan generation to protect against future uncertainty. By a priori modeling uncertainties in data corresponding to service times, resource availability, supplies and demands, we generate solutions that are more robust operationally, that is, more likely to be executed or easier to repair when disrupted. We propose a novel modeling and solution framework involving a decomposition scheme that separates problems into a routing master problem and Scheduling Sub-Problems; and iterates to find the optimal solution. Uncertainty is captured in part by the master problem and in part by the Scheduling Sub-Problem. We present proof-of-concept for our approach using real data involving routing and scheduling for a large shipment carrier’s ground network, and demonstrate the improved robustness of solutions from our approach.",
keywords = "Decomposition, Multi-commodity routing and scheduling, Robust routing and scheduling, Uncertainty",
author = "Lavanya Marla and Cynthia Barnhart and Varun Biyani",
year = "2014",
month = "9",
day = "20",
doi = "10.1007/s10951-013-0317-1",
language = "English (US)",
volume = "17",
pages = "489--506",
journal = "Journal of Scheduling",
issn = "1094-6136",
publisher = "Springer New York",
number = "5",

}

TY - JOUR

T1 - A decomposition approach for commodity pickup and delivery with time-windows under uncertainty

AU - Marla, Lavanya

AU - Barnhart, Cynthia

AU - Biyani, Varun

PY - 2014/9/20

Y1 - 2014/9/20

N2 - We consider a special class of large-scale, network-based, resource allocation problems under uncertainty, namely that of multi-commodity flows with time-windows under uncertainty. In this class, we focus on problems involving commodity pickup and delivery with time-windows. Our work examines methods of proactive planning, that is, robust plan generation to protect against future uncertainty. By a priori modeling uncertainties in data corresponding to service times, resource availability, supplies and demands, we generate solutions that are more robust operationally, that is, more likely to be executed or easier to repair when disrupted. We propose a novel modeling and solution framework involving a decomposition scheme that separates problems into a routing master problem and Scheduling Sub-Problems; and iterates to find the optimal solution. Uncertainty is captured in part by the master problem and in part by the Scheduling Sub-Problem. We present proof-of-concept for our approach using real data involving routing and scheduling for a large shipment carrier’s ground network, and demonstrate the improved robustness of solutions from our approach.

AB - We consider a special class of large-scale, network-based, resource allocation problems under uncertainty, namely that of multi-commodity flows with time-windows under uncertainty. In this class, we focus on problems involving commodity pickup and delivery with time-windows. Our work examines methods of proactive planning, that is, robust plan generation to protect against future uncertainty. By a priori modeling uncertainties in data corresponding to service times, resource availability, supplies and demands, we generate solutions that are more robust operationally, that is, more likely to be executed or easier to repair when disrupted. We propose a novel modeling and solution framework involving a decomposition scheme that separates problems into a routing master problem and Scheduling Sub-Problems; and iterates to find the optimal solution. Uncertainty is captured in part by the master problem and in part by the Scheduling Sub-Problem. We present proof-of-concept for our approach using real data involving routing and scheduling for a large shipment carrier’s ground network, and demonstrate the improved robustness of solutions from our approach.

KW - Decomposition

KW - Multi-commodity routing and scheduling

KW - Robust routing and scheduling

KW - Uncertainty

UR - http://www.scopus.com/inward/record.url?scp=84919386715&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84919386715&partnerID=8YFLogxK

U2 - 10.1007/s10951-013-0317-1

DO - 10.1007/s10951-013-0317-1

M3 - Article

AN - SCOPUS:84919386715

VL - 17

SP - 489

EP - 506

JO - Journal of Scheduling

JF - Journal of Scheduling

SN - 1094-6136

IS - 5

ER -