This frontmatter introduces the proceedings of the Eighteenth International Symposium on Combinatorial Search (SoCS 2025), held from August 12–15, 2025, in Scotland, United Kingdom. It includes a preface by the conference co-chairs—Maxim Likhachev, Hana Rudová, and Enrico Scala—along with details on the Best Paper Awards, the organizing and program committees, and the sponsors of this edition.

In our paper, we aim to address common sources of uncertainty in real-world industrial vehicle routing problems. By extending traditional deterministic heuristic solvers with easy-to-integrate, reusable, and computationally efficient mechanisms, we introduce reasoning about uncertainty while retaining the capability of scaling to problems with up to 1,000 customers. We formulate four such mechanisms, including standard chance constraints, two data manipulation methods, and a novel penalty-based method. These mechanisms are evaluated on both standard benchmarks and real-world industrial vehicle routing instances, and their key search-related properties are discussed. This extended abstract presents results previously published at the European Conference on Artificial Intelligence 2024.

The motivation for our research arises from the limitations of traditional deterministic heuristic solvers for vehicle routing problems (VRP) observed in industrial practice. In general, the quantities provided to the solvers as inputs, e.g., loads or service times, are typically estimates or simplifying reflections of reality. While current state-of-the-art solvers are applicable to complex VRP variants at scale, their inability to reason about uncertainties limits their usefulness in real-world applications. Despite stochastic VRPs being a widely studied topic, related approaches are typically centered around the uncertainty in the problem rather than extending successful deterministic methods. Moreover, uncertainty-related methodologies and models are often strongly linked to computationally expensive sampling or exact algorithms making their scaling problematic. Thus, we aim for easy-to-integrate, reusable, and especially computationally efficient mechanisms, allowing us to naturally extend state-of-the-art heuristic solvers for a wide range of VRPs with reasoning about input uncertainties. We formulate four mechanisms fitting these criteria, including standard chance constraints, two data manipulation methods, and a novel penalty-based method. These four mechanisms are compared and analyzed for the most common sources of uncertainty in loads and times on both benchmark and complex real-world instances. Their favorable scaling properties are demonstrated on instances with up to 1,000 customers.

The pickup and delivery problem with transfers generalizes the classical pickup and delivery problem (PDP) by allowing the vehicles to exchange request loads at designated transfer points. Transfers often lead to substantial reductions in transportation costs, yet they come with a significant burden of additional computational complexity. Even meta-heuristic methods are thus limited to instances of at most lower hundreds of requests leaving the desirable benefits unreachable for larger instances. Our approach bypasses the complexities inherent to current methods by deciding about the transfers apriori and thus reducing the problem to a PDP instance. To make as informed decisions as possible, we analyze a broader set of characteristics that may be used to carry out the apriori decisions. We opt to derive and examine multiple such PDP instances to cover different transfer choices. Our analysis of the derived PDP instances then allows their efficient processing in parallel. The proposed framework addresses a large-scale freight transportation problem with real-world characteristics and transfers where typical instances count over 1,200 requests and 300 vehicles. We show the potential of the proposed framework on both real-world and synthetic instances with up to 1,500 requests. The experiments demonstrate that substantial savings may be achieved within favorable runtimes even for very large instances.

Our work addresses the scheduling of mobile robots for transportation and processing of operations on machines in a flexible manufacturing system. Both mobile robots and automated guided vehicles (AGVs) can transport components among machines in the working space. Nevertheless, the difference is that mobile robots considered in this work can process specific value-added operations, which is not possible for AGVs. This new feature increases complexity as well as computational demands. To summarize, we need to compute a sequence of operations on machines, the robot assignments for transportation, and the robot assignments for processing. The main contribution is the proposal of an adaptive large neighborhood search algorithm with the sets of exploration and exploitation heuristics to solve the problem considering makespan minimization. Experimental evaluation is presented on the existing benchmarks. The quality of our solutions is compared to a heuristic based on genetic algorithm and mixed-integer programming proposed recently. The comparison shows that our approach can achieve comparable results in real time which is in order of magnitude faster than the earlier heuristic.1

We presents a unique advanced job scheduler for the widely used TORQUE Resource Manager. Unlike common schedulers that are using queuing approach and heuristics, our solution uses planning (job schedule construction) and schedule optimization by a local search-inspired metaheuristic, achieving better predictability, performance and fairness with respect to common queue-based approaches. The suitability and good performance of our solution is demonstrated both by "synthetic" experiments as well as by our real-life performance results that are coming from the deployment of our scheduler in the production infrastructure of the Czech Centre for Education, Reasearch and Innovation in ICT (CERIT Scientific Cloud).

Recent advances in processing capabilities of commodity hardware enabled deployment of high-performance collaborative environments in various application fields, where maximum image quality and interactivity are critical. In this paper, we focus on user-empowered collaborative environments that rely on information available to the users and that can be obtained from the end-nodes connected to the network. We build upon our previous work on scheduling strategies for multi-point data distribution, while utilizing media transcoding during the distribution and partial network topology knowledge that may be provided by the users. The novelty introduced by this paper focuses on improving scheduling scalability by employing local search metaheuristics, allowing us to maintain systems comprising more than twice as many applications compared to the previous approaches.

Interactive collaborative environments built upon high quality video applications require minimum capture-to-display latency to maintain feeling of natural communication. In practice, end users often encounter interruptions due to network congestion, which they could not avoid without knowledge of physical network infrastructure. We solve the problem of application level multipoint routing without assuming accurate knowledge of network link capacities, but rather relying on their estimates by network inference and bandwidth measurement tools. Our approach can handle uncertainties caused by both unreliable bandwidth measurements and unexpected capacity sharing. Support for on-the-fly transcoding of data streams on multicast agents allows per-recipient adaptation of video quality and bandwidth. We have implemented an ant colony optimization algorithm in the Co Universe middleware for orchestration of collaborative environments. Experiments show very good quality of results on most practical use cases and ability to solve significantly larger instances than optimal approaches based on mixed integer programming.

High-quality video-mediated communication uses data streams with high bitrates, often comparable to capacity of network links, it also demands latency to be as low as possible. The problem of finding the optimal solution to multi-point data distribution on application level while minimizing distribution latency is NP-complete. This paper presents a novel approach to solving the problem using local search methods. Experimental evaluation within the Co Universe framework shows that the proposed algorithm is capable of solving problems an order of magnitude larger than previously available approaches, while maintaining high quality of the solutions. The proposed approach also makes initial attempts toward handling of system dynamics and minimizing the impact on already participating users.

High-quality video, both uncompressed and compressed with relatively low compression ratio, is used in interactive environments, where minimum end-to-end latency is required. The media streams planning solves multi-point data routing for such applications even when bit rate of streams is comparable to capacity of network links. Recent advances in acceleration of high-throughput low-latency video processing enable on-the-fly video transcoding even for 4K and 8K video streams, thus allowing individual adaptation of data stream for each recipient without affecting the others. Stimulated by these advances, we present a novel media streams planning with transcoding on network nodes, and a mixed integer programming approach to solve the problem optimally. Our approach also enhances traditional end-to-end network model of the whole system with known topology of certain network regions. Our solution was implemented in the Co Universe, which is middleware for orchestration of collaborative environments. Measurements show that performance of the new solver is sufficient for interactive solving of most practical use-cases, thus enabling self-organization of high-performance collaborative environments.

Although Grid users demand good performance for their jobs, this requirement is often not satisfied by the widely used queue‐based scheduling approaches. This article concentrates on the application of schedule‐based methods that improve on both the service delivered to the user and the traditional objective of machine usage. Importantly, the interaction between the incremental application of these methods and the dynamic character of the problem allows reasonable runtimes to be achieved. Two new schedule‐based methods that are designed to schedule dynamically arriving jobs on machines in a computational Grid are formally described in the article. The Earliest Gap — Earlier Deadline First (EG‐EDF) policy fills the earliest gap in the known schedule with newly arriving jobs, incrementally building a new schedule. If the gap is not suitable for an incoming job, the EDF policy is used to modify the existing schedule. A Tabu search algorithm is used to further optimize the schedule by moving selected jobs into the earliest suitable gaps. The proposed incremental schedule‐based methods are compared with some of the most common queue‐based scheduling algorithms such as FCFS (First Come First Served), EASY backfilling (Extensible Argonne Scheduler sYstem), Flexible backfilling as well as with the nonincremental version of the EG‐EDF schedule‐based policy.