PLANNING AND CONTROL OF TRANSPORTATION SYSTEMS: THE 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 a 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, the author has 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. The author extends 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 the author provides a number of motivations and formulations for the SKPRW. She also establishes several properties useful in solving it. She then suggests algorithmic approaches to exploit these properties, in some instances providing polynomial solution techniques. Finally, she concludes with a case study yielding empirical insights.
- Record URL:
-
-
Supplemental Notes:
- This research was supported by a grant from the U.S. Department of Transportation, University Transportation Centers Program.
-
Corporate Authors:
University of Massachusetts, Amherst
Transportation Center, 130 Natural Resources Road
Amherst, MA United States 01003 -
Authors:
- Barnhart, C
- Publication Date: 2000-5-10
Language
- English
Media Info
- Features: Figures; References; Tables;
- Pagination: 12 p.
Subject/Index Terms
- TRT Terms: Algorithms; Freight transportation; Optimization; Polynomials; Resource allocation; Stochastic processes; Transportation planning
- Uncontrolled Terms: Robust planning; Stochastic knapsack problem with random weights
- Subject Areas: Data and Information Technology; Freight Transportation; Highways; Planning and Forecasting; I72: Traffic and Transport Planning;
Filing Info
- Accession Number: 00795482
- Record Type: Publication
- Report/Paper Numbers: Final Report
- Files: UTC, NTL, TRIS, ATRI
- Created Date: Jul 11 2000 12:00AM