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

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