We introduce the Destructive Object Handling (DOH) problem, which models aspects of many real-world allocation problems, such as shipping explosive munitions, scheduling processes in a cluster with fragile nodes, re-using passwords across multiple websites, and quarantining patients during a disease outbreak. In these problems, objects must be assigned to handlers, but each object has a probability of destroying itself and all the other objects allocated to the same handler. The goal is to maximize the expected value of the objects handled successfully. We show that finding the optimal allocation is @math - @math , even if all the handlers are identical. We present an FPTAS when the number of handlers is constant. We note in passing that the same technique also yields a first FPTAS for the weapons-target allocation problem manne_wta with a constant number of targets. We study the structure of DOH problems and find that they have a sort of phase transition -- in some instances it is better to spread risk evenly among the handlers, in others, one handler should be used as a sacrificial lamb''. We show that the problem is solvable in polynomial time if the destruction probabilities depend only on the handler to which an object is assigned; if all the handlers are identical and the objects all have the same value; or if each handler can be assigned at most one object. Finally, we empirically evaluate several heuristics based on a combination of greedy and genetic algorithms. The proposed heuristics return fairly high quality solutions to very large problem instances (upto 250 objects and 100 handlers) in tens of seconds.
The DOH problem has many applications in the domain of hazardous material processing and routing @cite_16 . These problems generally deal with the selection of minimum risk processing locations @cite_15 and transportation routes in networks @cite_8 , @cite_5 -- i.e., finding minimum cost facility locations and routes for which human and external material loss in the event of malfunction incidents is minimized.
@cite_5 @cite_15 @cite_16 @cite_8
2117638964 2033728116 2398179450 2898777864
We survey research on hazardous materials transportation in the areas of risk analysis, routing scheduling and facility location. Our focus is primarily on work done since 1980, and on research which is methodological rather than empirical. We also limit our focus to transport by land-based vehicles (truck and rail), excluding pipeline, air and maritime movements. The review traces the evolution of models from single-criterion optimizations to multiobjective analyses, and highlights the emerging direction of dealing explicitly with distributions of outcomes, rather than simply optimizing expected values. We also indicate examples of work which integrate risk analysis with routing, and routing with facility location. We conclude with a discussion of several aspects of hazardous materials transportation which offer important challenges for further research. Transportation of hazardous materials (hazmats) is a decision problem that has been attracted much attention due to the risk factor involved. A considerable amount of models have been developed that employ single or multiple objective shortest path algorithms minimising the risks for a given origin-destination pair. However in many real life applications (i.e. transportation of gas cylinders), transportation of hazmats calls for the determination of a set of routes used by a fleet of trucks to serve a set of customers, rather than determination of a single optimal route as shortest path algorithms produce. In this paper, we focus on population exposure risk mitigation via production of truck-routes by solving a variant of the Vehicle Routing Problem. For this purpose we employ a single parameter metaheuristic algorithm. A case study of this approach is also demonstrated. We consider the stochastic on-time arrival (SOTA) problem of finding the optimal routing strategy for reaching a given destination within a pre-specified time budget and provide the first results on using preprocessing techniques for speeding up the query time. We start by identifying some properties of the SOTA problem that limit the types of preprocessing techniques that can be used in this setting, and then define the stochastic variants of two deterministic shortest path preprocessing techniques that can be adapted to the SOTA problem, namely reach and arc-flags. We present the preprocessing and query algorithms for each technique, and also present an extension to the standard reach based preprocessing method that provides additional pruning. Finally, we explain the limitations of this approach due to the inefficiency of the preprocessing phase and present a fast heuristic preprocessing scheme. Numerical results for San Francisco, Luxembourg and a synthetic road network show up to an order of magnitude improvement in the query time for short queries, with even larger gains expected for longer queries. Abstract In this work we focus on an extension of the minimum cost flow problem in layered networks. Feasible arc flows must satisfy a specific compatibility restriction in addition to flow balance and capacity restrictions. Namely, at most one of the crossing arcs is allowed to have positive flow on it. This variant of the minimum cost flow problem, which we call the minimum cost noncrossing flow problem, can frequently be encountered in real life. The determination of optimal temporal quay crane allocations to berthed vessels in container terminals, and optimal train schedules through the stations on the same railroad line are two examples. We first analyze the complexity of the problem and show that the noncrossing flow problem is in fact N P -complete in a layered network. Then, we introduce mixed-integer linear programming formulations and discuss a polynomially solvable special case. Next we show a sufficient condition for the existence of a crossing in an optimal solution, which can be used for preprocessing the arcs in order to reduce the problem size. Our computational experiments on a large test set show that our preprocessing algorithm can significantly reduce the number of arcs.