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

Reductions of non-separable approximate linear programs for network revenue management

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第1期309卷 252-270页

作者： Laumer, Simon Barz, Christiane Univ Zurich Dept Business Adm CH-8032 Zurich Switzerland

We suggest a novel choice of non-separable basis functions for an approximate linear programming approach to the well-known network revenue management problem. Considering non-separability is particularly important when interdependencies between resources are large. Such a situation can be illustrated for example by a bus line, where different origin-destination pairs have many overlapping segments. Traditional separable approximation approaches tend to ignore the resulting interactions. We suggest to group resources into non-separable subnetworks. For each chosen subnetwork, basis functions either span the whole function space or consist of linear functions. Given this more general choice of basis functions, we extend existing reductions of approximate linear programs. If there is only one subnetwork, for which the basis functions span the whole function space, we prove the equivalence to a compact linear program of polynomial size. For the general case, we suggest an approximate reduction. Numerical examples illustrate our novel upper bounds for the maximum expected revenue and the corresponding competitive policies. In particular, we find that the added benefit of non-separability heavily depends on the network structure and the capacity. Our work helps to better understand the impact of assuming separability in network revenue management. The polynomial sized reductions make it possible to estimate the added average revenue resulting from incorporating interactions between resources. The theory we develop demonstrates how the interpretation of dual variables as state-action probabilities can be applied to reduce exponentially large approximate linear programs via variable aggregation.

关键词： Revenue management approximate dynamic programming Network revenue management Reductions Non-separability

来源：评论

学校读者我要写书评

暂无评论

dynamic migratory beekeeping route recommendation based on spatio-temporal distribution of nectar sources

引用

ANNALS OF OPERATIONS RESEARCH 2024年第2-3期341卷 1075-1105页

作者： Ma, Minghong Yang, Fei Chengdu Foreign Languages Sch Chengdu 611731 Peoples R China Southwest Jiaotong Univ Sch Econ & Management Chengdu 610031 Peoples R China

Due to the lack of scientific guidance, most migratory beekeepers currently arrange their migratory beekeeping routes by experience. The production mode is extensive, and the quality and efficiency need to be improved. Therefore, this study investigates a dynamic migratory route recommendation problem considering the stochastic yield of nectar sources and uncertain disastrous weather events, by which the beekeeper can dynamically follow the practical and effective recommended route to cope with production risk to reach a better revenue. To this end, the problem is first formulated as a Markov decision process considering various flowering durations of nectar sources, migration costs and time, the prices of bee products, and, most importantly, uncertain yields. Then, an approximate dynamic programming algorithm incorporated with offline and online learning procedures is proposed to deal with the curse of dimensionality. Several acceleration methods are also provided to solve the problem more efficiently. The conducted numerical study shows that the proposed model and algorithm perform well in approximation precise and computational efficiency. Finally, the computational results show that the proposed migratory beekeeping route recommendation method effectively deals with yield uncertainty and significantly improves the migratory beekeeping revenue.

关键词： Migratory beekeeping Route recommendation Yield uncertainty Markov decision process approximate dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Optimizing last-mile delivery: a dynamic compensation strategy for occasional drivers

引用

OR SPECTRUM 2024年 1-58页

作者： Schur, Rouven Winheller, Kai Univ Duisburg Essen Chair Prod & Logist Planning Mercator Sch Management Lotharstr 65 D-47057 Duisburg Germany

Amid the rapid growth of online retail, last-mile delivery faces significant challenges, including the cost-effective delivery of goods to all delivery locations. Our work contributes to this stream by applying dynamic pricing techniques to effectively model the possible involvement of the crowd in fulfilling delivery tasks. The use of occasional drivers (ODs) as a viable, cost-effective alternative to traditional dedicated drivers (DDs) prompts the necessity to focus on the inherent challenge posed by the uncertainty of ODs' arrival times and willingness to perform deliveries. We introduce a dynamic programming framework that offers individualized bundles of a delivery task and compensation to ODs as they arrive. This model, akin to a reversed form of dynamic pricing, accounts for ODs' decision-making by treating their acceptance thresholds as a random variable. Therefore, our model addresses the dynamic and stochastic nature of OD availability and decision-making. We analytically solve the stage-wise optimization problem, outline inherent challenges such as the curses of dimensionality, and present structural properties. Tailored to meet these challenges, our approximation methods aim to accurately determine avoided costs, which are a key factor in calculating optimal compensation. Our simulation study reveals that the savings generated by involving ODs in deliveries can be significantly increased through our individualized dynamic compensation policy. This approach not only excels in generating savings for the firm but also provides a utility surplus for ODs. Additionally, we demonstrate the applicability of our approach to scenarios with time windows and illustrate the trade-off that arises from time window partitioning.

关键词： dynamic pricing Last-mile delivery Occasional drivers approximate dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Lateral Motion Control of a Maneuverable Aircraft Using Reinforcement Learning

引用

OPTICAL MEMORY AND NEURAL NETWORKS 2024年第1期33卷 1-12页

作者： Tiumentsev, Yu. V. Zarubin, R. A. Natl Res Univ Moscow Aviat Inst Moscow 125080 Russia

Machine learning is currently one of the most actively developing research areas. Considerable attention in the ongoing research is paid to problems related to dynamical systems. One of the areas in which the application of machine learning technologies is being actively explored is aircraft of various types and purposes. This state of the art is due to the complexity and variety of tasks that are assigned to aircraft. The complicating factor in this case is incomplete and inaccurate knowledge of the properties of the object under study and the conditions in which it operates. In particular, a variety of abnormal situations may occur during flight, such as equipment failures and structural damage, which must be counteracted by reconfiguring the aircraft's control system and controls. The aircraft control system must be able to operate effectively under these conditions by promptly changing the parameters and/or structure of the control laws used. Adaptive control methods allow to satisfy this requirement. One of the ways to synthesize control laws for dynamic systems, widely used nowadays, is LQR approach. A significant limitation of this approach is the lack of adaptability of the resulting control law, which prevents its use in conditions of incomplete and inaccurate knowledge of the properties of the control object and the environment in which it operates. To overcome this limitation, it was proposed to modify the standard variant of LQR (Linear Quadratic Regulator) based on approximate dynamic programming, a special case of which is the adaptive critic design (ACD) method. For the ACD-LQR combination, the problem of controlling the lateral motion of a maneuvering aircraft is solved. The results obtained demonstrate the promising potential of this approach to controlling the airplane motion under uncertainty conditions.

关键词： airplane motion control linear-quadratic regulator reinforcement learning approximate dynamic programming adaptive critic design

来源：评论

学校读者我要写书评

暂无评论

Efficient compact linear programs for network revenue management

引用

OPTIMIZATION LETTERS 2023年第2期17卷 437-451页

作者： Laumer, Simon Univ Zurich Dept Business Adm Plattenstr 14 CH-8032 Zurich Switzerland

We are concerned with computing bid prices in network revenue management using approximate linear programming. It is well-known that affine value function approximations yield bid prices which are not sensitive to remaining capacity. The analytic reduction to compact linear programs allows the efficient computation of such bid prices. On the other hand, capacity-dependent bid prices can be obtained using separable piecewise linear value function approximations. Even though compact linear programs have been derived for this case also, they are still computationally much more expensive compared to using affine functions. We propose compact linear programs requiring substantially smaller computing times while, simultaneously, significantly improving the performance of capacity-independent bid prices. This simplification is achieved by taking into account remaining capacity only if it becomes scarce. Although our proposed linear programs are relaxations of the unreduced approximate linear programs, we conjecture equivalence and provide according numerical support. We measure the quality of an approximation by the difference between the expected performance of an induced policy and the corresponding theoretical upper bound. Using this paradigm in numerical experiments, we demonstrate the competitiveness of our proposed linear programs.

关键词： Network revenue management approximate dynamic programming approximate linear programming Reductions

来源：评论

学校读者我要写书评

暂无评论

Understanding the Value of Fulfillment Flexibility in an Online Retailing Environment

引用

M&SOM-MANUFACTURING & SERVICE OPERATIONS MANAGEMENT 2023年第2期25卷 391-408页

作者： DeValve, Levi Wei, Yehua Wu, Di Yuan, Rong Univ Chicago Booth Sch Business Chicago IL 60637 USA Duke Univ Fuqua Sch Business Durham NC 27708 USA JD Com Amer Technol Corp Mountain View CA 94043 USA Stitch Fix San Francisco CA 94104 USA

Problem definition: Fulfillment flexibility, the ability of distribution centers (DCs) to fulfill demand originating from other DCs, can help e-retailers reduce lost sales and improve service quality. Because the cost of full flexibility is prohibitive, we seek to understand the value of partially flexible fulfillment networks under simple and effective fulfillment policies. Academic/practical relevance: We propose a general method for understanding the practical value of (partial) fulfillment flexibility using a data-driven model, theoretical analysis, and numerical simulations. Our method applies to settings with local fulfillment (i.e., order fulfillment from the originating DC) prioritization and possible customer abandonment, two features that are new to the fulfillment literature. We then apply this method for a large e-retailer. We also introduce a new class of spillover limit fulfillment policies with attractive theoretical and practical features. Methodology: Our analysis uses dynamic and stochastic optimization, applied probability, and numerical simulations. Results: We derive optimal fulfillment policies in stylized settings, as well as bounds on the performance under an optimal policy using theoretical analysis, to provide guidelines on which policies to test in numerical simulations. We then use simulations to estimate for our industrial partner that a proposed fulfillment network with additional flexibility equates to a profit improvement on the order of tens of millions of U.S. dollars. Managerial implications: We provide an approach for e-retailers to understand when fulfillment flexibility is most valuable. We find that fulfillment flexibility provides the most benefit for our collaborator when gross profits are high relative to fulfillment costs or centrally held inventory is low. Also, we identify the risks of myopic fulfillment with additional flexibility and demonstrate that an effective spillover limit policy mitigates these risks.

关键词： supply chain management e-commerce OM practice asymptotic analysis approximate dynamic programming

来源：评论

学校读者我要写书评

暂无评论

dynamic resource levelling in projects under uncertainty

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2023年第1期61卷 198-218页

作者： Li, Hongbo Zhang, Xianchao Sun, Jinshuai Dong, Xuebing Shanghai Univ Sch Management Shangda Rd 99 Shanghai 200114 Peoples R China China Acad Elect & Informat Technol Beijing Peoples R China Tianjin Univ Commerce Sch Accountancy Tianjin Peoples R China

In the resource levelling problem (RLP) under uncertainty, existing studies focus on obtaining an open-loop Bellman activity list that is not updated during project execution. In project management practice, it is also necessary to address more situations, such as activity overlaps and resource breakdowns. In this paper, we extend the uncertain RLP by proposing a resource levelling problem with multiple uncertainties (RLP-MU) that simultaneously considers uncertainties in activity durations, activity overlaps and resource availabilities. We formulate the RLP-MU as a Markov decision process model. Aimed at levelling resource usage by dynamically scheduling activities at each decision point based on the observed information, we develop a hybrid open-closed-loop approximate dynamic programming algorithm (HOC-ADP). In the HOC-ADP, we devise a closed-loop rollout policy to approximate the cost-to-go function and use the concept of the average project to avoid time-consuming simulation. A greedy-decoding-based estimation of distributed algorithm is also devised to construct an open-loop policy that is embedded in the HOC-ADP to further improve it. We additionally develop a simulation algorithm to evaluate the resource levelling performance of the HOC-ADP. Computational experiments on a benchmark dataset consisting of 540 problem instances are conducted to analyze the performance of the HOC-ADP, and the impact of various factors on resource levelling are investigated. The comparison experimental results indicate that our HOC-ADP outperforms the state-of-the-art meta-heuristics.

关键词： approximate dynamic programming uncertain project scheduling resource levelling activity overlaps resource breakdowns

来源：评论

学校读者我要写书评

暂无评论

dynamic demand management and online tour planning for same-day delivery

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第2期307卷 860-886页

作者： Klein, Vienna Steinhardt, Claudius Univ Bundeswehr Munich Chair Business Analyt & Management Sci Munich Germany

For providers to stay competitive in a context of continued growth in e-retail sales and increasing cus-tomer expectations, same-day delivery options have become very important. Typically, with same-day delivery, customers purchase online and expect to receive their ordered goods within a narrow deliv-ery time span. Providers thus experience substantial operational challenges to run profitable tours and generate sufficiently high contribution margins to cover overhead costs. We address these challenges by combining a demand-management approach with an online tour-planning approach for same-day deliv-ery. More precisely, in order to reserve capacity for high-value customer orders and to guide customer choices toward efficient delivery operations, we propose a demand-management approach that explicitly optimizes the combination of delivery spans and prices which are presented to each incoming customer request. The approach includes an anticipatory sample-scenario based value approximation, which in-corporates a direct online tour-planning heuristic. It does not require extensive offline learning and is scalable to realistically sized instances with multiple vehicles. In a comprehensive computational study, we show that our anticipatory approach can improve the contribution margin by up to 50% compared to a myopic benchmark approach. We also show that solving an explicit pricing optimization problem is a beneficial component of our approach. More precisely, it outperforms both a pure availability control and a simple pricing rule based on opportunity costs. The latter idea is one used in other approaches for related dynamic pricing problems dealt with in the literature. (c) 2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://***/licenses/by-nc-nd/4.0/ )

关键词： Logistics Same -day delivery Last -Mile logistics Demand management approximate dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Scheduling EV Charging Having Demand With Different Reliability Constraints

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2023年第10期24卷 11018-11029页

作者： Shao, Shiping Sartipizadeh, Hossein Gupta, Abhishek Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Ford Motor Co Dearborn MI 48126 USA

We develop a new algorithm, based on approximate dynamic programming, to efficiently schedule the charging processes of a large number of electric vehicles (EVs) with flexibility, which allows the EV charging service provider to charge the EVs between their minimum and target state of charge (SoC) within a time window. We assume that the charging demands have known distributions and the charging process of EVs can be scheduled preemptively. We model the scheduling problem as a dynamic program with state-dependent constraints and solve it utilizing the fitted value iteration. We propose a multi-stage decoupled algorithm to reduce the dimensions in the fitted value iteration to reduce the computation complexity, and provide sufficient conditions for achieving optimality.

关键词： dynamic scheduling Electric vehicle charging Heuristic algorithms Costs Schedules Approximation algorithms Reliability EV charging approximate dynamic programming fitted value iteration

来源：评论

学校读者我要写书评

暂无评论

Solving large-scale dynamic vehicle routing problems with stochastic requests

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第2期306卷 596-614页

作者： Zhang, Jian Luo, Kelin Florio, Alexandre M. Van Woensel, Tom South China Univ Technol Dept Elect Business Guangzhou 510006 Peoples R China Eindhoven Univ Technol Dept Ind Engn & Innovat Sci NL-5600 MB Eindhoven Netherlands Univ Bonn Inst Comp Sci D-53115 Bonn Germany Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

dynamic vehicle routing problems (DVRPs) arise in several applications such as technician routing, meal delivery, and parcel shipping. We consider the DVRP with stochastic customer requests (DVRPSR), in which vehicles must be routed dynamically with the goal of maximizing the number of served requests. We model the DVRPSR as a multi-stage optimization problem, where the first-stage decision defines route plans for serving scheduled requests. Our main contributions are knapsack-based linear models to ap-proximate accurately the expected reward-to-go, measured as the number of accepted requests, at any state of the stochastic system. These approximations are based on representing each vehicle as a knap-sack with a capacity given by the remaining service time available along the vehicle's route. We combine these approximations with optimal acceptance and assignment decision rules and derive efficient and high-performing online scheduling policies. We further leverage good predictions of the expected reward-to-go to design initial route plans that facilitate serving dynamic requests. Computational experiments on very large instances based on a real street network demonstrate the effectiveness of the proposed meth-ods in prescribing high-quality offline route plans and online scheduling decisions. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://***/licenses/by/4.0/ )

关键词： Routing Markov decision processes Column generation Stochastic requests approximate dynamic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：