{'fraction_non_alphanumeric': 0.025430067314884067, 'fraction_numerical': 0.008476689104961356, 'mean_word_length': 4.926144756277695, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Stochastic Knapsack Problem with Random Weights : A Heuristic Approach to Robust Transportation Planning

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. However, incorporating stochasticity into problems that are already large-scale and difficult to solve 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, 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 paper we provide a number of motivations and formulations for 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. INTRODUCTION Our study of the stochastic knapsack problem was initially motivated by a search for robust planning heuristics for a variant of the vehicle routing problem. In our routing problem, a home heating fuel delivery company selects a subset of its regular customers for delivery each day, then assigns customers to drivers and designs driver routes. The customers' demands are not known exactly but instead are based on limited forecasts. There is a significant body of literature on the vehicle routing problem with stochastic demands (VRPSD). In particular, Bertsimas et al. (1995), Bertsimas and Simchi-Levi (1986), Bertsimas and Van Ryzin (1993), Gendreau et al. (1996 [1]), Gendreau et al. (1996 [2]), Bertsimas (1992), Dror et al. (1989), and Gendreau et al. (1995) provide a number of algorithmic approaches to these problems. In most of this VRPSD literature, it is assumed that all customers must be serviced. If capacity is exceeded, the driver returns to the depot to gain additional capacity in order to service any remaining customers. The problem therefore includes the decision of when to return to the depot and how to order the customers. Our problem was slightly different in that there is the option of selecting only