The Gateway Location Problem: Assessing the impact of candidate site selection policies

The Gateway Location Problem (GLP) is a new combinatorial optimization problem arising in the framework of rule-based risk mitigation policies for hazmat vehicle routing. GLP consists of locating a fixed number of check points (so called gateways) selected out of a set of candidate sites and routing each vehicle through one assigned gateway in such a way that the sum of the risks of vehicle itineraries is minimized. This paper addresses a GLP preparatory step, that is, how to select candidate sites, and it investigates the impact of different information guided policies for determining such a set. Indeed, previous results pointed out that this stage of the process can impact not only the efficacy of the method, i.e., the risk level associated with the solution itineraries, but also the efficiency of the method with regard to the number of sites to be considered. All policies consist of selecting a ground set and sampling it according to a probability distribution law. A few criteria are proposed for generating ground sets as well as a few probability distribution laws. A deterministic variant based on a cardinality constrained covering model is also proposed for generating candidate site sets. All policies have been tested and compared against plain random generation through extensive testing on a set of realistic instances characterized by three different risk measures. Results confirm that a careful choice of the candidate site set is a critical step of the whole GLP based risk reduction process. A complexity proof of NP-hardness of GLP is also provided.