Robust analysis of discounted Markov decision processes with uncertain transition probabilities

Optimal policies in Markov decision problems may be quite sensitive with regard to transition probabilities.In practice,some transition probabilities may be uncertain.The goals of the present study are to find the robust range for a certain optimal policy and to obtain value intervals of exact transition probabilities.Our research yields powerful contributions for Markov decision processes(MDPs)with uncertain transition probabilities.We first propose a method for estimating unknown transition probabilities based on maximum likelihood.Since the estimation may be far from accurate,and the highest expected total reward of the MDP may be sensitive to these transition probabilities,we analyze the robustness of an optimal policy and propose an approach for robust analysis.After giving the definition of a robust optimal policy with uncertain transition probabilities represented as sets of numbers,we formulate a model to obtain the optimal policy.Finally,we define the value intervals of the exact transition probabilities and construct models to determine the lower and upper bounds.Numerical examples are given to show the practicability of our methods.

Robust Optimization of Municipal Solid Waste Collection and Transportation with Uncertain Waste Output: A Case Study

Garbage collection is an important issue in urban environmental management.With the increased awareness of urban residents regarding safety,environmental protection,and health in recent years,it is necessary to logically organize municipal solid waste collection and transportation routes while also considering economic and social benefits.This article focuses on the optimization of the waste transportation routes of garbage trucks.With the objective of minimizing transportation costs and maximizing resident satisfaction,we establish a robust optimization model for the multi-trip collection and transportation of municipal solid waste in an uncertain environment.Resident satisfaction is defined as the penalty cost against a time window constraint.The Bertsimas robust optimization method is applied to characterize the uncertainty,and the decision-making scheme of the receiving route is used to adapt to waste volume changes.We conduct a case study based on real-world data for municipal solid waste collection and transportation in the Dongcheng District of Beijing,China.The solution is validated using the CPLEX program,and the validity of the model is verified.In addition,a sensitivity analysis of related parameters is conducted to study the impacts of variations in work hour limits and time windows on the total cost and service levels,as well as their relationships with the level of robustness.This could help decision-makers make reasonable choices based on actual conditions and to balance reductions in total cost with service level improvements.

Network design for local agriculture using robust optimization

For small farmers wishing to sell their products under the “local agriculture”marketing con-cept,connecting with consumers can be challenging.One approach to mitigating this discon-nect between where production occurs and where consumers reside is through a network of regional consolidation points.In this study,we utilize optimization models to assist the Mis-souri Coalition of Environment(MCE)in helping farmers from Missouri and Illinois route products from their farms to a central hub in St.Louis.The aim of this study was to minimize the ton-miles traveled by farmers and MCE vehicles in delivering agricultural products from farms to regional hubs to the central hub.Given historical data about variability of plant and animal production in the Greater Plains region,a robust optimization approach was incorpo-rated to increase the likelihood that the network can accommodate uncertainty in agricul-tural production.GAMS/CPLEX was used to solve the model under different configurations and identify potential locations for regional hubs.Computational testing determined that the capacity of hubs plays a key role in the optimal assignments:given the assumed model constraint that farmers can travel only to their nearest regional hub,solutions may sacrifice a better objective function value in order to accommodate farmers’travel requirements.