The classic Resource Constrained Shortest Path (RCSP) problem aims to find a cost optimal path between a pair of nodes in a network such that the resources used in the path are within a given limit. Having been studied for over a decade, RCSP has seen recent solutions that utilize heuristic-guided search to solve the constrained problem faster. Building upon the bidirectional A* search paradigm, this paper introduces a novel constrained search framework that uses efficient pruning strategies to allow for accelerated and effective RCSP search in large-scale networks. Results show that, compared to the state of the art, our enhanced framework can significantly reduce the constrained search time, achieving speed-ups of over to two orders of magnitude.

Constrained pathfinding is a classic yet challenging network optimization problem with broad applicability across many real-world domains. The Resource-Constrained Shortest Path (RCSP) problem focuses on finding cost-optimal paths that satisfy multiple resource constraints. In this paper, we propose a novel heuristic-guided search framework that accelerates constrained search in large-scale networks, including those with negative costs and resources, by leveraging efficient queuing and pruning strategies. Experimental results on real-world benchmark maps show that our framework achieves up to two orders of magnitude speedup over state-of-the-art methods, demonstrating its effectiveness in solving challenging RCSP instances within limited time.

The Multi-objective Shortest Path (MOSP) problem is a classic network optimization problem that aims to find all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies on multi-objective search with A* (MOA*) have demonstrated superior performance in solving difficult MOSP instances. This paper presents a novel search framework that allows efficient parallelization of MOA* with different objective orders. The framework incorporates a unique upper-bounding strategy that helps the search reduce the problem's dimensionality to one in certain cases. Experimental results demonstrate that the proposed framework can enhance the performance of recent A*-based solutions, with the speed-up proportional to the problem dimension.

Deep neural networks (DNNs) are increasingly deployed in real-time applications, yet their inference performance is often constrained by inefficient GPU utilization. While various inter-operator scheduling methods have been proposed to address this issue, many suffer from coarse-grained operator classifications, incomplete parallelism, unawareness of GPU resource contention, etc. To overcome these limitations, we propose HIOCS, a heuristic inter-operator co-scheduling framework that accelerates DNN inference on GPUs through fine-grained kernel-level scheduling. HIOCS employs a graph optimization technique at kernel granularity that reconstructs data dependencies based on memory access patterns, thereby uncovering latent parallelism. Building on this optimized graph, a heuristic co-scheduling algorithm is introduced to prioritize critical-path kernels and selectively co-locate non-critical kernels by jointly considering latency impact, resource contention, and kernel affinity to minimize makespan and maximize GPU utilization. Extensive experiments on popular DNN models across diverse domains demonstrate that HIOCS consistently achieves higher GPU utilization and better scalability. Compared to PyTorch default mode and the state-of-the-art method Opara, HIOCS achieves up to$21.19 \times$and$1.13 \times$speedup in inference latency, respectively, making it well-suited for latency-sensitive deployment scenarios.

Abstract This article reports on an approach for the VeRoLog Solver Challenge 2019: the fourth solver challenge facilitated by VeRoLog, the EURO Working Group on Vehicle Routing and Logistics Optimization. The authors were awarded third place in this challenge. The routing challenge involved solving two interlinked vehicle routing problems for equipment: one for distribution (using trucks) and one for installation (using technicians). We describe our solution method, based on a matheuristics approach in which the overall problem is heuristically decomposed into components that can then be solved by formulating them as set partitioning problems. To solve these set partitioning problems we introduce a novel method we call “columnwise neighborhood search,” which allows us to explore a large neighborhood of the current solution in an exact manner. By iteratively applying mixed‐integer programming methods, we obtain good quality solutions to our subproblems. We then use a simple local search “fusion” heuristic to further improve the solution to the overall problem. Besides introducing and discussing this solution method, we highlight the problem instances for which our approach was particularly successful in order to obtain general insights about our methodology.

We consider multi‐objective shortest path problems in which the edge lengths are uncertain. Different concepts for finding so‐called robust efficient solutions for multi‐objective robust optimization exist. In this article, we consider multi‐scenario efficiency, flimsily and highly robust efficiency, and point‐based and set‐based minmax robust efficiency. Labeling algorithms are an important class of algorithms for multi‐objective (deterministic) shortest path problems. We analyze why it is, for most of the considered concepts, not straightforward to use labeling algorithms to find robust efficient solutions. We then show two approaches to extend a generic multi‐objective label correcting algorithm for these cases. We finally present extensive numerical results on the performance of the proposed algorithms.