不确定性条件下的设备替换优化的 随机动态规划方法

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (3): 76-84.

不确定性条件下的设备替换优化的随机动态规划方法

FAN (David) Wei ^*1, MACHEMEHL Randy ², GEMAR Mason², BROWN Leonard 3

1. 北卡罗来纳大学夏洛特分校土木与环境工程系，夏洛特 28223，美国； 2.德克萨斯大学奥斯汀分校交通研究中心，奥斯汀 78712，美国； 3.德克萨斯大学泰勒分校计算机学院，泰勒 75799，美国

收稿日期:2012-10-10 修回日期:2013-10-23 出版日期:2014-06-25 发布日期:2014-07-10
作者简介:FAN (David) Wei(1974–)，男,副教授.

A Stochastic Dynamic Programming Approach for the Equipment Replacement Optimization under Uncertainty

FAN (David) Wei¹, MACHEMEHL Randy ², GEMAR Mason ², BROWN Leonard ³

1 Department of Civil and Environmental Engineering, University of North Carolina at Charlotte, Charlotte 28223, U.S.A； 2 Center for Transportation Research, University of Texas at Austin, Austin 78712, U.S.A； 3 Department of Computer Science, University of Texas at Tyler, Tyler 75799, U.S.A.

Received:2012-10-10 Revised:2013-10-23 Online:2014-06-25 Published:2014-07-10

摘要/Abstract

摘要：

本文提出了一种解决设备更新换代优化（ERO）问题的随机动态规划（SDP）模型，用以明确地解释在车辆利用中的不确定性，并采用 Bellman 算法解决 ERO SDP 问题. 针对 SDP 状态空间的增长，提出了特殊简化算法，以解决动态规划方法中固有的“维数灾”问题，确保所需的内存和计算时间不会随着时间范围的增加而成倍增长.并对 SDP 软件的实现技术、功能和图形用户界面（GUI）进行了讨论，开发了基于 SDP 的 ERO 软件，并使用美国得克萨斯交通局（TxDOT）现有车辆数据进行验证.对统计结果、软件计算时间和求解效果进行综合分析，结果显示，使用该 ERO 软件，估计大量成本可以节省.

关键词: 系统工程, 动态规划, 设备更换, 交通运输

Abstract:

In this paper, a stochastic dynamic programming (SDP) based optimization model is formulated for the equipment replacement optimization (ERO) problem that can explicitly account for the uncertainty in vehicle utilization. The Bellman approach is developed and implemented to solving the ERO SDP problem. Particular attention is paid to the SDP state-space growth and special scenario reduction techniques are devel- oped to resolve the“curse of dimensionality”issue that is inherent to the dynamic programming method to ensure that the computer memory and solution computational time required will not increase exponentially with the increase in time horizon. SDP software computer implementation techniques, functionalities and the Graphical User Interfaces (GUI) are discussed. The developed SDP-based ERO software is tested and validat- ed using the current Texas Department of Transportation (TxDOT) vehicle fleet data. Comprehensive numeri- cal results, such as statistical analyses, the software computational time and solution quality, are described and substantial cost-savings have been estimated by using this ERO software.

Key words: systems engineering, dynamic programming, equipment replacement, transportation

中图分类号:

FAN (David) Wei,MACHEMEHL Randy,GEMAR Mason,BROWN Leonard . 不确定性条件下的设备替换优化的随机动态规划方法[J]. 交通运输系统工程与信息, 2014, 14(3): 76-84.

FAN (David) Wei, MACHEMEHL Randy,GEMAR Mason,BROWN Leonard . A Stochastic Dynamic Programming Approach for the Equipment Replacement Optimization under Uncertainty[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(3): 76-84.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18785.shtml

http://www.tseit.org.cn/CN/Y2014/V14/I3/76

参考文献

[1] Fan W, Machemehl R, Kortum K. Equipment replacement optimization: Part I. solution methodology, statistical data analysis, and cost forecasting[C]//Transportation Research Record-Journal of Transportation Research Board and Proceedings of the 90 th Annual Transportation Research Board Meeting,2011:88-98.

[2] TxDOT equipment replacement model–TERM, 2004[R/OL]. Accessed on January 20, 2009, ftp://ftp.dot.state.tx. us/pub/txdot-info/gsd/pdf/txdoterm.pdf
[3] Fan W, Machemehl R, Gemar M. Equipment replace-ment optimization: Part II. dynamic programming-based optimization[C]. //Submitted for Publication in 2012 Transportation Research Record and Presentation at the 91st Annual Meeting of the Transportation Research Board, 2012.
[4] Bellman R E. Equipment replacement policy[J]. Journal of the Society for the Industrial Applications of Mathematics, 1995, 3:133-136.
[5] Bellman R E. Dynamic programming[M], Dover Publications, 2003.
[6] Wagner H M. Principles of operations research[M]. Prentice-Hall, Englewood Cliffs, NJ, 1975.
[7] Waddell R. A model for equipment replacement decisions and policies [J]. Interfaces, 1983, 13(4):1-7.
[8] Hartman J C. A note on‘a strategy for optimal equipment replacement’[J]. Production Planning & Control, 2005,16(7):733-739.
[9] Hartman J C, Murphy A. Finite- horizon equipment re? placement analysis[J]. IIE Transactions, 2006, 38(5):
409-419.
[10] Meyer R A. Equipment replacement under uncertainty [J]. Management Science, 1971, 17(11):750-758.
[11] Hartman J C, Rogers J L. Dynamic programming ap? proaches for equipment replacement problems with continuous and discontinuous technological change[J]. IMA Journal of Management Mathematics, 2006, 17(2):143-158.
[12] Fan W, Machemehl R, Gemar M, et al. A stochastic dynamic programming approach for the equipment replacement optimization with probabilistic vehicle utilization [C]. // the Transportation Research Board, National Research Council, Washington DC, 2012.
[13] Hillier F, Lieberman G. Introduction to operations research, 8th Edition [M]., Tata McGraw- Hill Education, 2005.
[14] Wolsey L A. Integer programming[M]. New York: Wiley, 1998.
[15] Nemhauser G L, Wolsey L A. Integer and combinatorial optimization[M]. New York: Wiley, 1999.
[16] Bertsekas D P. Dynamic programming and optimal control, 2nd edition [M]. Belmont, MA: Athena Scientific, 2001.