Monge Properties, Optimal Greedy Policies, and Policy Improvement for the Dynamic Stochastic Transportation Problem
Alexander S. Estes () and
Michael O. Ball ()
Additional contact information
Alexander S. Estes: Institute for Mathematics and Its Applications, University of Minnesota, Minneapolis, Minnesota 55455
Michael O. Ball: Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742; Institute of Systems Research, University of Maryland, College Park, Maryland 20742
INFORMS Journal on Computing, 2021, vol. 33, issue 2, 785-807
Abstract:
We consider a dynamic, stochastic extension to the transportation problem. For the deterministic problem, there are known necessary and sufficient conditions under which a greedy algorithm achieves the optimal solution. We define a distribution-free type of optimality and provide analogous necessary and sufficient conditions under which a greedy policy achieves this type of optimality in the dynamic, stochastic setting. These results are used to prove that a greedy algorithm is optimal when planning a type of air-traffic management initiative. We also provide weaker conditions under which it is possible to strengthen an existing policy. These results can be applied to the problem of matching passengers with drivers in an on-demand taxi service. They specify conditions under which a passenger and driver should not be left unassigned.
Keywords: transportation problem; Monge properties; greedy algorithm; multi-period optimization; stochastic optimization (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:
Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0990 (application/pdf)
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:inm:orijoc:v:33:y:2021:i:2:p:785-807
Access Statistics for this article
More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().