检索结果-内蒙古大学图书馆

A tutorial on value function approximation for stochastic and dynamic transportation

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2024年第1期22卷 145-173页

作者： Heinold, Arne Univ Kiel Sch Econ & Business Kiel Germany

This paper provides an introductory tutorial on value function approximation (VFA), a solution class from Approximate Dynamic Programming. VFA describes a heuristic way for solving sequential decision processes like a Markov Decision Process. Real-world problems in supply chain management (and beyond) containing dynamic and stochastic elements might be modeled as such processes, but large-scale instances are intractable to be solved to optimality by enumeration due to the curses of dimensionality. VFA can be a proper method for these cases and this tutorial is designed to ease its use in research, practice, and education. For this, the tutorial describes VFA in the context of stochastic and dynamic transportation and makes three main contributions. First, it gives a concise theoretical overview of VFA's fundamental concepts, outlines a generic VFA algorithm, and briefly discusses advanced topics of VFA. Second, the VFA algorithm is applied to the taxicab problem that describes an easy-to-understand transportation planning task. Detailed step-by-step results are presented for a small-scale instance, allowing readers to gain an intuition about VFA's main principles. Third, larger instances are solved by enhancing the basic VFA algorithm demonstrating its general capability to approach more complex problems. The experiments are done with artificial instances and the respective Python scripts are part of an electronic appendix. Overall, the tutorial provides the necessary knowledge to apply VFA to a wide range of stochastic and dynamic settings and addresses likewise researchers, lecturers, tutors, students, and practitioners.

关键词： Tutorial Markov decision process Approximate dynamic programming value function approximation Reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

High-Order Taylor Expansion-Based Nonlinear value function approximation for Stochastic Economic Dispatch of Active Distribution Network

引用

IEEE TRANSACTIONS ON SMART GRID 2024年第5期15卷 4511-4521页

作者： Luo, Yuhao Zhu, Jianquan Chen, Jiajun Wu, Ruibing Huang, Haojiang Liu, Wenhao Liu, Mingbo South China Univ Technol Sch Elect Power Engn Guangzhou 510640 Peoples R China

The stochastic economic dispatch (SED) problem of active distribution network (ADN) is computationally intractable for traditional algorithms due to the randomness, nonlinearity, and nonconvexity. To solve this problem, we decompose it into a sequence of tractable subproblems, and then employ the high-order Taylor expansion (HTE)-based value functions to estimate the interaction among these subproblems. Compared with traditional value function approximation (VFA) techniques, the proposed HTE-based VFA technique extends the approximate value function from the low-order form to the arbitrarily high-order form, which facilitates describing the nonlinear characteristics. Furthermore, different from commonly used Monte Carlo-based expectation calculation (EC) techniques, which require to re-execute calculation procedures in numerous scenarios, the proposed HTE-based EC technique leverages the nature of HTE to directly obtain the expectation of value function according to the distributions of random variables. Such that the computational burden can be reduced significantly. Finally, the aforementioned two techniques are combined to form an HTE-based economic dispatch algorithm, and then applied to several ADN systems. The numerical simulations fully demonstrate the effectiveness of the proposed algorithm.

关键词： value function approximation high-order Taylor expansion stochastic economic dispatch active distribution network value function approximation high-order Taylor expansion stochastic economic dispatch active distribution network

来源：评论

学校读者我要写书评

暂无评论

Local and soft feature selection for value function approximation in batch reinforcement learning for robot navigation

引用

JOURNAL OF SUPERCOMPUTING 2024年第8期80卷 10720-10745页

作者： Fathinezhad, Fatemeh Adibi, Peyman Shoushtarian, Bijan Chanussot, Jocelyn Univ Isfahan Fac Comp Engn Artificial Intelligence Dept Esfahan Iran Univ Grenoble Alpes Grenoble INP GIPSA Lab CNRS Grenoble France

This paper proposes a novel method for robot navigation in high-dimensional environments that reduce the dimension of the state space using local and soft feature selection. The algorithm selects relevant features based on local correlations between states, avoiding duplicate inappropriate information and adjusting sensor values accordingly. By optimizing the value function approximation based on the local weighted features of states in the reinforcement learning process, the method shows improvements in the robot's motion flexibility, learning time, the distance traveled to reach its goal, and the minimization of collisions with obstacles. This approach was tested on an E-puck robot using the Webots robot simulator in different test environments.

关键词： Reinforcement learning value function approximation Local relevance feature selection Robot navigation

来源：评论

学校读者我要写书评

暂无评论

A Periodic Review Service Control Problem in a City Network: A value function approximation Method

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2025年

作者： Mu, Zhikang Hu, Qiying Fudan Univ Sch Management 670 Guoquan Rd Shanghai 200433 Peoples R China Fudan Univ Sch Management 670 Guoquan Rd Shanghai 200433 Peoples R China

In this paper, we study a periodic review service control problem with backlogging in a city network (SCP-N), based on a third-party quality inspection platform in which products from suppliers need to be inspected before shipping them to the buyers. In each period, servers are assigned to cities for serving the tasks on their weekdays or go home on weekends. Tasks arrive randomly each day, each with its own difficulty level, and can only be served by a server with a matching or higher skill level. The platform's objective is to maximize the total profit in planning horizons. We construct a Markov decision process (MDP) model for it. But it is difficult to solve the MDP model due to the curse of dimensionality. For this, we reduce the state space by limiting the maximum number of tasks in each city and aggregating the cities into city clusters, and also propose a high-to-low assignment rule to reduce the action space. Then, we present our policy that draws on value function approximation (VFA) with bi-reduction that combines VFA with the above reduction techniques. Numerical example shows that our policy outperforms other benchmark policies in the literature.

关键词： Periodic review service control problem high-to-low assignment rule Markov decision process value function approximation

来源：评论

学校读者我要写书评

暂无评论

Optimized ensemble value function approximation for dynamic programming

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第2期309卷 719-730页

作者： Cervellera, Cristiano Natl Res Council Italy Inst Marine Engn Via Marini 6 I-16149 Genoa Italy

Approximate dynamic programming (ADP) is the standard tool for the solution of multistage dynamic optimization problems under general conditions, such as nonlinear state equation and cost, and continuous state and control spaces. In the typical ADP implementation, the value function is approximated by means of a single model trained over a suitable sampling of the state space. In this paper we investigate the ensemble learning paradigm in the ADP context, which consists in exploiting the outputs of many models trained for the value function approximation. To this purpose, we introduce an optimization scheme for the aggregation of the ensemble outputs, related to the supremum norm error on which the ADP accuracy depends. Furthermore, we show that the ensemble of value function approximations can be used to identify a-priori good state points used to train the approximating models, exploiting an ambiguity-like term tailored to the proposed ensemble optimization scheme. The advantages of ensembles in ADP are showcased both through error analysis and a simulation campaign involving various test problems. Our results show how ensembles obtained through the proposed output weights optimization scheme yield more accurate and robust value function approximations with respect to single elements. At the same time, we show how the ensembles can successfully be employed to select good state samples to be employed as training set for the value function approximations. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Dynamic programming Ensemble models value function approximation

来源：评论

学校读者我要写书评

暂无评论

Combining value function approximation and multiple scenario approach for the effective management of ride-hailing services

引用

EURO JOURNAL ON TRANSPORTATION AND LOGISTICS 2023年 12卷

作者： Heitmann, R. Julius O. Soeffker, Ninja Ulmer, Marlin W. Mattfeld, Dirk C. Tech Univ Carolo Wilhelmina Braunschweig Decis Support Grp Braunschweig Germany Univ Wien Dept Business Decis & Analyt Vienna Austria Otto von Guericke Univ Chair Management Sci Magdeburg Germany

The availability of various services for individual mobility is increasing, especially in urban areas. Dynamic ride-hailing services address these aspects and are gaining market share with providers such as MOIA, UberX Share, Sprinti or BerlKonig. To be able to offer competitive pricing for such a service and at the same time provide a high service quality (e.g. fast response times), effective capacity management is needed. In order to reach this goal, two challenges have to be met by the service provider. On the one hand, a proper demand control has to be installed, which optimizes the responses to transportation requests from customers. On the other hand, suitable fleet control needs to be set in place to optimize the route of the fleet so that the demand can be met. Papers in the literature do solve both but typically focus on one of these two challenges. As an example, value function approximation (VFA) can be used to learn a service offering decision while anticipating future incoming requests. A typical example of a routing-focused method is the multiple scenario approach (MSA) creating a routing which anticipates future requests using a sampling method. In this paper, we combine VFA and MSA to address the two challenges in an effective way. The resulting method is called anticipatory-routing-and-service-offering (ARS). We find that the combined method significantly outperforms the individual components, improving not only the total reward but also the accepted requests. It is found that this performance is particularly high with a heavy workload and thus resources are relatively scarce. We analyse how and under which conditions the components together or individually are particularly important.

关键词： Ride-sharing Dial-a-ride Dynamic vehicle routing value function approximation Multiple scenario approach

来源：评论

学校读者我要写书评

暂无评论

Meso-parametric value function approximation for dynamic customer acceptances in delivery routing

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第1期285卷 183-195页

作者： Ulmer, Marlin W. Thomas, Barrett W. Tech Univ Carolo Wilhelmina Braunschweig Carl Friedrich Gauss Fak Muhlenpfordtstr 23 D-38106 Braunschweig Germany Univ Iowa Tippie Coll Business 108 John Pappajohn Business Bldg Iowa City IA 52242 USA

The rise of mobile communication, ample computing power, and Amazon's training of customers has led to last-mile delivery challenges and created struggles for companies seeking to budget their limited delivery resources efficiently to generate enough revenue. In this paper, we examine the capacitated customer acceptance problem with stochastic requests (CAPSR), a problem in which a company seeks to maximize expected revenue by accepting or rejecting requests. Each accepted request generates revenue and must be routed, consuming driver time and vehicle capacity. To solve the problem, we introduce a novel method of value function approximation (VFA). Conventionally, VFAs are either parametric (P-VFAs) or non-parametric (N-VFAs). Both VFAs have advantages and shortcomings and their performances rely significantly on the structure of the underlying problem. To combine the advantages and to alleviate the shortcomings of P-VFA and N-VFA used individually, we present a novel method, meso-parametric value function approximation (M-VFA). The results of computational experiments show that the M-VFA outperforms benchmarks for the CAPSR and show M-VFA offers the advantages of the individual VFAs while alleviating their shortcomings. Most importantly, we demonstrate that simultaneous approximations lead to better outcomes than either N- and P-VFA individually or some ex-post combination. (C) 2019 Published by Elsevier B.V.

关键词： Dynamic customer acceptances Dynamic vehicle routing Dynamic multi-dimensional knapsack problem Approximate dynamic programming value function approximation

来源：评论

学校读者我要写书评

暂无评论

value function approximation for dynamic multi-period vehicle routing

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第3期269卷 883-899页

作者： Ulmer, Marlin W. Soeffker, Ninja Mattfeld, Dirk C. Tech Univ Carolo Wilhelmina Braunschweig Inst Wirtschaftsinformat Carl Friedrich Gauss Fak Muhlenpfordtstr 23 D-38106 Braunschweig Germany

In practical applications like parcel or technician services, customers request service during the day. Service providers decide whether to accept a customer for same-day service or to defer a customer due to resource limitations. Some requests are therefore postponed to the following day. To satisfy customer expectations, service providers aim on a high number of same-day services. Still, acceptance decisions not only affect the performance on the current, but also on the following day. Suitable acceptance, postponement, and routing decisions therefore should anticipate future routing and requests in both the current and the next day(s). The resulting decision problem is a dynamic multi-period vehicle routing problem with stochastic service requests. To approximately solve the Markov decision process of the presented problem, we present an anticipatory dynamic policy based on approximate dynamic programming. This policy estimates the potential of problem states with respect to future same-period services within and over the periods. Our policy draws on value function approximation, state space aggregation, and on a classification of the periods. We compare our policy to several policies from the literature. We analyze how and when multi-period anticipation improves the solution quality significantly and how the newly developed state space classification is essential to achieve anticipation. We finally show how multi-period anticipation changes the acceptance behavior to less discrimination of rural customers and to a fairer geographical distribution of same-day services in comparison to single-period anticipation. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Routing Dynamic vehicle routing Multi-periodicity Stochastic requests value function approximation

来源：评论

学校读者我要写书评

暂无评论

Leveraging Statistical Multi-Agent Online Planning with Emergent value function approximation 17

Leveraging Statistical Multi-Agent Online Planning with Emer...

引用

17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

作者： Phan, Thomy Belzner, Lenz Gabor, Thomas Schmid, Kyrill Ludwig Maximilians Univ Munchen Inst Informat Munich Germany

ISBN: (纸本)9781450356497

Making decisions is a great challenge in distributed autonomous environments due to enormous state spaces and uncertainty. Many online planning algorithms rely on statistical sampling to avoid searching the whole state space, while still being able to make acceptable decisions. However, planning often has to be performed under strict computational constraints making online planning in multi-agent systems highly limited, which could lead to poor system performance, especially in stochastic domains. In this paper, we propose Emergent value function approximation for Distributed Environments (EVADE), an approach to integrate global experience into multi-agent online planning in stochastic domains to consider global effects during local planning. For this purpose, a value function is approximated online based on the emergent system behaviour by using methods of reinforcement learning. We empirically evaluated EVADE with two statistical multi-agent online planning algorithms in a highly complex and stochastic smart factory environment, where multiple agents need to process various items at a shared set of machines. Our experiments show that EVADE can effectively improve the performance of multi-agent online planning while offering efficiency w.r.t. the breadth and depth of the planning process.

关键词： multi-agent planning online planning value function approximation

来源：评论

学校读者我要写书评

暂无评论

Leveraging Statistical Multi-Agent Online Planning with Emergent value function approximation 18

Leveraging Statistical Multi-Agent Online Planning with Emer...

引用

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems

作者： Thomy Phan Lenz Belzner Thomas Gabor Kyrill Schmid LMU Munich Munich Germany

关键词： multi-agent planning online planning value function approximation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：