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.
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. Undesirable consequences of dangerous goods incidents can be mitigated by quick arrival of specialized response teams at the accident site. We present a novel methodology to determine the optimal design of a specialized team network so as to maximize its ability to respond to such incidents in a region. We show that this problem can be represented via a maximal arc-covering model. We discuss two formulations for the maximal arc-covering problem, a known one and a new one. Through computational experiments, we establish that the known formulation has excessive computational requirements for large-scale problems, whereas the alternative model constitutes a basis for an efficient heuristic. The methodology is applied to assess the emergency response capability to transport incidents, that involve gasoline, in Quebec and Ontario. We point out the possibility of a significant improvement via relocation of the existing specialized teams, which are currently stationed at the shipment origins. The transport of hazardous materials is an important strategic and tactical decision problem. Risks associated with this activity make transport planning difficult. Although most existing analytical approaches for hazardous materials transport account for risk, there is no agreement among researchers on how to model the associated risks. This paper provides an overview of the prevailing models, and addresses the question "Does it matter how we quantify transport risk?" Our empirical analysis on the U.S. road network suggests that different risk models usually select different "optimal" paths for a hazmat shipment between a given origin-destination pair. Furthermore, the optimal path for one model could perform very poorly under another model. This suggests that researchers and practitioners must pay considerable attention to the modeling of risks in hazardous materials transport. In this paper, we consider the problem of network design for hazardous material transportation where the government designates a network, and the carriers choose the routes on the network. We model the problem as a bilevel network flow formulation and analyze the bilevel design problem by comparing it to three other decision scenarios. The bilevel model is difficult to solve and may be ill-posed. We propose a heuristic solution method that always finds a stable solution. The heuristic exploits the network flow structure at both levels to overcome the difficulty and instability of the bilevel integer programming model. Testing on real data shows that the linearization of the bilevel model fails to find stable solutions and that the heuristic finds lower risk networks in less time. Further testing on random instances shows that the heuristically designed networks achieve significant risk reduction over single-level models. The risk is very close to the least risk possible. However, this reduction in risk comes with a significant increase in cost. We extend the bilevel model to account for the cost risk trade-off by including cost in the first-level objective. The biobjective-bilevel model is a rich decision-support tool that allows for the generation of many good solutions to the design problem.