A Stackelberg framework for disrupting coordinated,multi-asset routing and sequential servicing of demands

This research examines the problem of routing multiple assets of different types over a network to service demands, where the demands must be serviced by asset types in sequential order within a bounded amount of time, and minimizing the cumulative service time is of interest. Disrupting these decisions, an opponent seeks to identify effective network disruption strategies with limited resources to maximize the minimal cumulative service time. Within a bilevel programming structure for this Stackelberg game, the upper-level problem determines the disruption strategy, and the lower-level problem routes the assets. Seeking the identification of high-quality solutions with relatively low computational effort, this research identifies and tests three solution procedures: a greedy construction heuristic (GCH) that iteratively identifies each disruptive action, a customized implementation of simulated annealing (SA), and an enhanced variant thereof (eSA) that leverages a prioritized identification of candidate solutions along with a tabu list. Testing compares the solution methods on similar instances over a range of selected algorithmic and instance-specific parameters. Results showed the enhanced SA method performed best, and extended testing explored the effect of increasing selected problem sets on the relative improvement in eSA over GCH, as well as its effect on algorithmic runtimes.