In the aftermath of a sudden catastrophe, first responders (FRs) strive to reach and rescue immobile victims. Simultaneously, civilians use the same roads to evacuate, access medical facilities and shelters, or reunite with their relatives via private vehicles. The escalated traffic congestion can significantly hinder critical FR operations. A proposal from the Türkiye Ministry of Transportation and Infrastructure is to allocate a lane on specific road segments exclusively for FR use, mark them clearly, and precommunicate them publicly. For a successful implementation of this proposal, an FR path should exist from designated entry points to each FR demand point in the network. The reserved FR lanes along these paths will be inaccessible to evacuees, potentially increasing evacuation times. Hence, in this study, we aim to determine a subset of links along which an FR lane should be reserved and analyze the resulting evacuation flow under evacuees’ selfish routing behavior. We introduce this problem as the first responder network design problem (FRNDP) and formulate it as a mixed-integer nonlinear program. To efficiently solve FRNDP, we introduce a novel bilevel nested heuristic, the Graver augmented multiseed algorithm (GAMA) within GAMA, called GAGA. We test GAGA on synthetic graph instances of various sizes as well as scenarios related to a potential Istanbul earthquake. Our comparisons with a state-of-the-art exact algorithm for network design problems demonstrate that GAGA offers a promising alternative approach and highlights the need for further exploration of quantum-inspired computing to tackle complex real-world problems. History: Accepted by Giacomo Nannicini, Area Editor for Quantum Computing and Operations Research. Accepted for Special Issue. Funding: S. Tayur and A. Tenneti acknowledge Raytheon BBN (RTX-BBN) for its support through a Carnegie Mellon University-BBN contract as part of a Defense Advanced Research Projects Agency project on quantum-inspired classical computing. A. Karahalios is supported by the National Science Foundation Graduate Research Fellowship Program [Grants DGE1745016, DGE2140739]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0574 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0574 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

ABSTRACT Less‐than‐truckload (LTL) transportation is a widely used shipping modality within the logistics industry, facilitating the movement of loads insufficient in size to occupy the entirety of a truck's capacity. Drawing on the real‐life problem of a third‐party logistics (3PL) carrier, which navigates an expansive transportation network and unpredictable demand patterns, we propose a centralized planning approach for LTL transportation, taking advantage of consolidation opportunities at cross‐dock hubs to minimize long‐term freight costs while ensuring on‐time delivery. We present an integer linear programming (ILP) formulation to generate a multi‐day plan with known demands and a daily planning problem (DPP) model to be solved daily, emulating the available order information in a real planning scenario. DPP optimizes truck routes and loading plans, incorporating a penalty cost for postponed transportation requests. We devise a novel multi‐stage matheuristic integrating geographical decomposition with tractable integer programming models and column generation‐based heuristics. With this approach, the DPP is solved in fewer than 2 h of run‐time for real problem instances with as high as 1400 transportation orders. We benchmark our results against a baseline heuristic that mirrors the firm's existing planning approach through a multi‐period simulation. Our comparative evaluations reveal a noteworthy 7.8% improvement in long‐term freight costs, concurrently maintaining adherence to the 98% on‐time delivery target.

We consider the route optimization problem of transporting valuables in cash‐in‐transit (CIT) operations. The problem arises as a rich variant of the capacitated vehicle routing problem (CVRP) with time windows and pickup and deliveries. Due to the high‐risk nature of this operation (e.g., robberies) we consider a bi‐objective function where we attempt to minimize the total transportation cost and the security risk of transporting valuables along the designed routes. For risk minimization, we propose a composite risk measure that is a weighted sum of two risk components: (i) following the same or very similar routes, and (ii) visiting neighborhoods with low socio‐economic status along the routes. We also consider vehicle capacities in terms of monetary value carried as per insurance regulations. We develop an adaptive randomized bi‐objective path selection algorithm that uses the composite risk measure in choosing alternative paths between origin‐destination pairs over a sequence of days. We solve the rich CVRP approximately for each day with updated costs. We test our solution approach on a data set from a CIT delivery service provider and provide insights on how the routes diversify daily. Our approach generates a spectrum of solutions with cost‐risk trade‐off to support decision making. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(3), 256–269 2017

We consider peer-to-peer video broadcasting using cooperation among peers in an ad hoc wireless network. As opposed to the traditional single hop broadcasting, multiple hops cause an increase in broadcast video quality while creating interference and increasing transmission delay. We develop heuristics for the NP-complete problem of finding the subset of cooperating peers and the number of hops to maximize the data rate and to minimize the maximum observed delay in the system. Simulations show that using the proposed heuristics, different video sequences can be viewed at high qualities with acceptable delay among all peers.

We propose an exact solution method for a routing and capacity installation problem in networks. Given an input graph, the problem is to route traffic from a set of source nodes to a sink node and to install transmission facilities on the edges of the graph to accommodate the flow at minimum cost. We give a branch-and-bound algorithm that solves relaxations obtained by approximating the noncontinuous cost function by its lower convex envelope. The approximations are refined by branching on the flow ranges on selected edges. Our computational experiments indicate that this method is effective in solving moderate-size problems and provides very good candidate solutions early in the branch-and-bound tree.

For hard optimization problems, it is difficult to design heuristic algorithms which exhibit uniformly superior performance for all problem instances. As a result it becomes necessary to tailor the algorithms based on the problem instance. In this paper, we introduce the use of a cooperative problem solving team of heuristics that evolves algorithms for a given problem instance. The efficacy of this method is examined by solving six difficult instances of a bicriteria sparse multiple knapsack problem. Results indicate that such tailored algorithms uniformly improve solutions as compared to using predesigned heuristic algorithms.