Reference Policies for Non-myopic Sequential Network Design and Timing Problems

Joseph Y. J. Chow () and Hamid R. Sayarshad
Additional contact information
Joseph Y. J. Chow: New York University
Hamid R. Sayarshad: Ryerson University

Networks and Spatial Economics, 2016, vol. 16, issue 4, No 9, 1183-1209

Abstract: Abstract Despite a growing number of studies in stochastic dynamic network optimization, the field remains less well defined and unified than other areas of network optimization. Due to the need for approximation methods like approximate dynamic programming, one of the most significant problems yet to be solved is the lack of adequate benchmarks. The values of the perfect information policy and static policy are not sensitive to information propagation while the myopic policy does not distinguish network effects in the value of flexibility. We propose a scalable reference policy value defined from theoretically consistent real option values based on sampled sequences, and estimate it using extreme value distributions. The reference policy is evaluated on an existing network instance with known sequences (Sioux Falls network from Chow and Regan 2011a): the Weibull distribution demonstrates good fit and sampling consistency with more than 200 samples. The reference policy is further applied in computational experiments with two other types of adaptive network design: a facility location and timing problem on the Simchi-Levi and Berman (1988) network, and Hyytiä et al.’s (2012) dynamic dial-a-ride problem. The former experiment represents an application of a new problem class and use of the reference policy as an upper bound for evaluating sampled policies, which can reach 3 % gap with 350 samples. The latter experiment demonstrates that sensitivity to parameters may be greater than expected, particularly when benchmarked against the proposed reference policy.

Keywords: Approximate dynamic programming; Sequential network design problems; Dynamic dial-a-ride problem; Facility location problem; Adapted stochastic process; Markov decision process (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s11067-015-9315-5 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:16:y:2016:i:4:d:10.1007_s11067-015-9315-5

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-015-9315-5

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().