详情

原文传递 Planning and Control of Transportation Systems: The Stochastic Knapsack Problem with Random Weights

题名：	Planning and Control of Transportation Systems: The Stochastic Knapsack Problem with Random Weights
作者：	Prof. Cynthia Barnhart
关键词：	stochastic optimization, robust planning, stochastic knapsack problem with random weights
摘要：	When transportation plans are developed, problem parameters are often not known with certainty. In addition, the parameters may vary throughout the time period during which the plan is implemented. Thus, improvements can often be made in the quality of such plans by accounting for this variability. Incorporating stochasticity into problems that are already large-scale and difficult to solve, however, is significant challenge. Heuristic methods are often helpful, as is de-coupling a large problem into a series of smaller problems for which solution techniques may already exist. To contribute to the building of a toolkit for tackling such complex planning problems in a robust manner, we have chosen to focus on solving the stochastic knapsack problem with random weights (SKPRW) The deterministic knapsack problem is a classical problem with a wide range of transportation applications and a substantial body of literature. In this problem, there are a collection of objects, each with a given weight and value. The objective is to choose the set of objects with maximum collective value without exceeding an upper bound on their combined weight. We extend this deterministic knapsack problem literature by allowing the weights of each object to be random. We can view the SKPRW as a resource allocation problem. A planner is choosing amongst a series of business opportunities (for example, possible shipping customers). Each customer requires some quantity of a resource such as time, labor, physical materials, or space on a transportation link. The planner has a known, fixed, and finite supply of this resource. The problem is to select the set of customers that best utilize this capacity. This is further complicated by the fact that each customer’s demand for the limited resource is not known fully at the time of the decision. For example, a freight transportation company may be choosing to commit to a customer without knowing exactly how much freight that customer will need to ship on any given day. Thus we can view this problem as a knapsack problem, where each object (here, the business opportunities) has a weight and a value and the knapsack has a fixed capacity. We are seeking to select the optimal set of objects, given the complicating factor that the weights are random variables. In this report we provide a number of motivations and formulations tor the SKPRW. We also establish several properties useful in solving it. We then suggest algorithmic approaches to exploit these properties, in some instances providing polynomial solution techniques. Finally, we conclude with a case study yielding basic empirical insights.
报告类型：	科技报告