Wiley: Networks: Table of Contents

Consistent Collaborative Vehicle Utilization

Sahand Asgharieh Ahari, Ilke Bakir, Kees Jan Roodbergen — Tue, 14 Apr 2026 10:10:19 -0700

ABSTRACT

Carriers are often reluctant to collaborate with other carriers in delivering goods to customers despite potential cost reductions. A durable collaboration requires attention to more aspects. Carriers typically wish to remain competitive, unconstrained by the collaboration, increasing profits by attracting new customers and withholding information about their customers from the other carriers. They may also wish to provide good services, such as making all deliveries consistently at approximately the same time of the day. To facilitate this setting, we introduce a multi-period collaborative model, the “consistent collaborative vehicle utilization” framework. Carriers engage in collaboration by borrowing trucks from each other. A borrowed truck first departs from the lender's depot to the borrowing carrier's depot and then visits delivery locations based on optimal routing decisions. Customers are served exclusively by their designated carrier and in an assigned time window, selected from a set of options specified by the customers. We formulate an integer programming problem and develop a branch-and-price algorithm to solve it. Additionally, to address larger instances, we propose two heuristics employing column generation techniques. Our experiments demonstrate reductions of up to 43% in the number of utilized vehicles, accompanied by a profit increase of up to 15.2%.

Speeding‐Up Graph Algorithms via Clique Partitioning

Akshar Chavan, Sanaz Rabinia, Daniel Grosu, Marco Brocanelli — Mon, 13 Apr 2026 00:02:09 -0700

ABSTRACT

Reducing the running time of graph algorithms is vital for tackling real-world problems such as shortest paths and matching in large-scale graphs, where path information plays a crucial role. To address this critical challenge, this paper introduces a graph restructuring algorithm that identifies bipartite cliques and replaces them with tripartite graphs. This restructuring leads to fewer edges while preserving complete graph path information, enabling the direct application of algorithms like matching and all-pairs shortest paths to achieve significant runtime reductions, especially for large, dense graphs. The running time of the proposed algorithm for a graph G(V,E)$$ G\left(V,E\right) $$, with |V|=n$$ \mid V\mid =n $$ and |E|=m$$ \mid E\mid =m $$ is O(mnδ)$$ O\left(m{n}^{\delta}\right) $$, which is better than O(mnδlog2n)$$ O\left(m{n}^{\delta }{\log}^2n\right) $$, the running time of the best existing algorithm for speeding-up other graph algorithms (the Feder–Motwani (FM) algorithm), where 0≤δ≤1$$ 0\le \delta \le 1 $$. Both the FM algorithm and the proposed algorithm are originally formulated for bipartite graphs, but can also be applied to general directed or undirected graphs. Our extensive experimental analysis demonstrates that the proposed algorithm achieves up to 21.26% higher reduction in the number of edges and runs up to 105.18×$$ 105.18\times $$ faster than the FM algorithm. On large synthetic graphs with up to 1.05 billion edges, it attains a reduction in the number of edges of up to 74.36%. On real-world graphs, it achieves a reduction in the number of edges by up to 46.8%. Furthermore, when used as a preprocessing step, our approach yields up to a 2.07×$$ 2.07\times $$ speedup for the matching algorithms on large synthetic graphs, and up to a 1.74×$$ 1.74\times $$ speedup for the All-Pairs Shortest Path algorithms on real-world graphs, when compared to using the given graph as input.

Ordered Median Traveling Salesman Problem

Ivana Ljubić, Alfredo Marín, Justo Puerto, Francisco Temprano — Wed, 01 Apr 2026 00:23:53 -0700

ABSTRACT

This paper introduces a novel combinatorial optimization problem with ordering constraints, termed the Ordered Median Traveling Salesman Problem (OMTSP). The OMTSP integrates key elements from both the classic Traveling Salesman Problem (TSP) and the Ordered Median Location Problem. Specifically, the objective is to identify a tour that minimizes a weighted sum of the sorted arc lengths within the tour. This flexible framework enables the modeling of a wide range of combinatorial optimization problems related to the traditional TSP, like the bottleneck TSP, the balanced TSP, or other TSP variants in which fairness measures are applied to the arcs of the tour. In this work, we present new mathematical formulations for the OMTSP across different variable spaces, which are solved using a branch-and-cut approach. Leveraging several newly derived structural properties, we enhance these formulations through advanced preprocessing strategies, variable bounding and variable fixing techniques, as well as through the introduction of new valid inequalities. A comprehensive computational study is conducted to evaluate the effectiveness of the proposed formulations and their associated improvements.

Exact Solutions for the Moving Firefighter Problem on Trees

Sat, 28 Mar 2026 01:23:18 -0700

ABSTRACT

The moving firefighter problem (MFP) is a more realistic variant of the classic firefighter problem (FP), where firefighters require time for both travel and defense. Unfortunately, the only known exact solution for the MFP does not scale. In this paper, we establish that the MFP is NP-complete on trees of maximum degree three and present four alternative methods to find exact solutions for the case of arbitrary trees with a single initial fire and one firefighter. The first method is a dynamic programming algorithm, while the other three methods are based on mathematical programming: an integer quadratically constrained program (IQCP), and two distinct integer linear programs (ILP and E-ILP). Our mathematical programming formulations exploit the inherent properties of tree topologies to significantly improve scalability by reducing the number of decision variables and constraints relative to those for arbitrary graphs. We present a comprehensive experimental analysis of the performance and scalability of the proposed solutions.

A Lasso‐Alternative to Dijkstra's Algorithm for Identifying Short Paths in Networks

Anqi Dong, Amirhossein Taghvaei, Tryphon T. Georgiou — Tue, 17 Mar 2026 23:23:15 -0700

ABSTRACT

We revisit the problem of finding the shortest path between two selected vertices of a graph and formulate this as an ℓ1$$ {\ell}_1 $$-regularized regression—Least Absolute Shrinkage and Selection Operator (lasso). We draw connections between a numerical implementation of this lasso formulation, using the so-called LARS algorithm, and a more established algorithm known as the bi-directional Dijkstra. Appealing features of our formulation include the applicability of the Alternating Direction of Multiplier Method (ADMM) to the problem to identify short paths, and a relatively efficient update to topological changes.

Issue Information

Mon, 02 Mar 2026 21:54:45 -0800

Networks, Volume 87, Issue 3, Page 245-246, April 2026.

Compact Mixed Integer Programming Formulations for the Minimum Biclique Cover Problem

Bruno Burin, Hamidreza Validi, Bochuan Lyu, Illya V. Hicks — Mon, 02 Mar 2026 21:54:45 -0800

ABSTRACT

Given a simple graph G=(V,E)$$ G=\left(V,E\right) $$ with vertex set V$$ V $$ and edge set E$$ E $$, the minimum biclique cover problem seeks to cover all edges of the graph with a minimum number of bicliques (i.e., complete bipartite subgraphs). This paper proposes two compact mixed integer programming (MIP) formulations for solving the minimum biclique cover problem on general graphs: (i) A natural formulation in the edge space and (ii) an extended formulation in the edge and vertex spaces. While the natural MIP formulation of Cornaz and Fonlupt (Discrete Mathematics, 2006) has exponentially many constraints, our natural formulation enjoys only a polynomial number of their exponential “no-good” cuts, along with another set of polynomial valid inequalities. We also employ bounding and variable fixing procedures that help solve most of our social network instances, which are not solvable to optimality in a one-hour time limit without the bounding and fixing procedures. The instances that are not solved in the one-hour time limit are submitted to the 2024 Mixed Integer Programming Library (MIPLIB 2024).

Infinitely Many Counterexamples to Conjectures by Boesch and Ath‐Sobel

Pablo Romero — Mon, 02 Mar 2026 21:54:45 -0800

ABSTRACT

Let 𝒞n,m be the set of connected simple graphs on n$$ n $$ vertices and m$$ m $$ edges. Define the corank of 𝒞n,m as m−n+1$$ m-n+1 $$. Let G$$ G $$ be in 𝒞n,m and ρ∈[0,1]$$ \rho \in \left[0,1\right] $$. The reliability RG(ρ)$$ {R}_G\left(\rho \right) $$ is the probability of G$$ G $$ being connected after each of its edges is removed independently with probability ρ$$ \rho $$. The graph G$$ G $$ is a uniformly most reliable graph (UMRG) if RG(ρ)≥RH(ρ)$$ {R}_G\left(\rho \right)\ge {R}_H\left(\rho \right) $$ for every H$$ H $$ in 𝒞n,m and for all ρ∈[0,1]$$ \rho \in \left[0,1\right] $$. In 1986, Boesch conjectured that each nonempty class 𝒞n,m contains at least one UMRG. A few years later, Boesch et al. and Wang proved that each class 𝒞n,m having corank up to 4 includes one UMRG. However, infinitely many counterexamples to the Boesch conjecture appeared. Ath and Sobel conjectured that the Boesch conjecture holds when the corank c$$ c $$ is between 5 and 8, provided the number of vertices is at least 2c−2$$ 2c-2 $$. Recently, it was proved that there are only finitely many UMRGs having corank 5, in strong contrast with graph classes having corank up to 4. A natural question is the existence of UMRGs having corank 6. Here, it is proved that for each positive integer s$$ s $$ there is no UMRG on 15s+4$$ 15s+4 $$ vertices having corank 6. This result provides new families of counterexamples to the Boesch and Ath-Sobel conjectures proposed respectively in 1986 and 2000.

Tractable but Hard to Approximate: The Bi‐Objective Minimum s$$ s $$‐t$$ t $$‐Cut Problem With Binary Capacities

Mon, 02 Mar 2026 21:54:45 -0800

ABSTRACT

The minimum s$$ s $$-t$$ t $$-cut problem is one of the most-studied problems in discrete optimization and has a unique complexity status in multi-objective optimization. Even though the single-objective version of the problem can be solved in polynomial time, it has been shown in the seminal work of Papadimitriou and Yannakakis (2000) that there does not exist a multi-objective fully polynomial-time approximation scheme (MFPTAS) for the minimum s$$ s $$-t$$ t $$-cut problem unless 𝒫=𝒩𝒫. This holds both for the case of p≥3$$ p\ge 3 $$ objective functions with arc capacities in {0,1}$$ \left\{0,1\right\} $$ and for p=2$$ p=2 $$ objective functions with general capacities, and even for tractable instances where the number of non-dominated points is only quadratic in the input size. In this article, we strengthen these results by showing that, assuming 𝒫≠𝒩𝒫, there does not exist an MFPTAS for the minimum s$$ s $$-t$$ t $$-cut problem with two objectives and arc capacities in {(1,0),(0,1)}$$ \left\{\left(1,0\right),\left(0,1\right)\right\} $$, nor for the minimum s$$ s $$-t$$ t $$-cut problem with two objectives and arc capacities in {(0,1),(1,1)}$$ \left\{\left(0,1\right),\left(1,1\right)\right\} $$. This advancement is particularly interesting since the considered problem variants are the only known problems in multi-objective optimization that do not admit an MFPTAS even though their single-objective versions are solvable in polynomial time and the problems are tractable, that is, the numbers of non-dominated points are polynomial (even linear) in the input size. Furthermore, we complement this result by showing that, on graphs of bounded tree-width, the minimum s$$ s $$-t$$ t $$-cut problem with polynomially bounded arc capacities can be solved exactly in polynomial time for any constant number of objectives.

Partial‐Outsourcing Strategy for the Vehicle Routing Problem With Stochastic Demands

Lin Zhu, Yossiri Adulyasak, Louis‐Martin Rousseau — Mon, 02 Mar 2026 21:54:45 -0800

ABSTRACT

This paper studies a combined delivery strategy involving a private vehicle and external carriers under stochastic customer demands. The routing problem focuses on a single private vehicle, while external carriers are allowed to determine their own routes independently and are compensated with a fixed price per unit demand served. A strategy incorporating routing re-optimization is proposed, along with a new recourse mechanism that leverages outsourcing through external carriers. To enable routing re-optimization, a novel approximate linear programming (ALP) approach is introduced. This offers a new pathway for addressing vehicle routing problems (VRPs) under stochastic demand considerations. The ALP approach is adapted to the specific structure of routing under stochastic demands, leading to the development of a decomposition-based ALP solution framework. This adaptation arises from changes in the decision sequence of routing and restocking at each step of the Markov decision process (MDP), which differs from previous formulations of vehicle routing under stochastic demands. Additionally, further adaptations are made to facilitate the computation of the proposed strategy by exploring the relationships among variables and constraints specific to the problem context, as well as by developing a constraint sampling procedure designed to mimic the near-optimal heuristic policy. Our numerical results show that the proposed outsourcing-based policy yields notable operating-cost savings, with an average improvement of 4.06% over the traditional recourse strategy in midpoint-depot instances. Moreover, in small instances where the optimal policy within the traditional partial re-optimization framework can be computed, the proposed price-directed (PD) policy still provides cost advantages over this re-optimization scheme, demonstrating the value of our ALP-based framework.

On the Multi‐Commodity Flow With Convex Objective Function: Column‐Generation Approaches

Beraud‐Sudreau Guillaume, Létocart Lucas, Magnouche Youcef, Martin Sébastien — Mon, 02 Mar 2026 21:54:45 -0800

ABSTRACT

The purpose of this work is to develop an algorithmic optimization approach for a capacitated multi-commodity flow problem, where the objective is to minimize the total link costs, where the cost of each arc increases convexly with its utilization. This objective is particularly relevant in telecommunication networks, where device performance can deteriorate significantly as the available bandwidth on a link becomes limited. By optimizing this convex function, traffic is efficiently distributed across the network, ensuring optimal use of available resources and preserving capacity for future demands. This paper describes the convex multi-commodity flow problem and presents methodologies to solve both its Splittable and Unsplittable variants. In the Splittable version, flows can be fractionally distributed across multiple paths, while in the Unsplittable version, each commodity must be routed through a single path. Our approach employs Column-Generation techniques to address the convexly increasing cost functions associated with arc utilization, effectively accommodating various forms of convex increasing cost functions, including non-differentiable or black-box convex increasing functions. The proposed methods demonstrate strong computational efficiency, offering a robust framework for managing network flows in complex telecommunication environments.

Extending the Inventory Routing Problem to Support Integrated Decision‐Making in an Urban Distribution Network

Titi Iswari, An Caris, Kris Braekers — Mon, 02 Mar 2026 21:54:45 -0800

ABSTRACT

Two-echelon distribution systems with an intermediate urban consolidation centre are one of the key innovations proposed in city logistics. We focus on a business-to-business context in which urban retailers are delivered by suppliers via such a city hub. Specifically, we investigate the benefits of simultaneously optimising routing decisions from the Urban Consolidation Center and inventory decisions at the retailers. For this, we extend the classical Inventory Routing Problem (IRP) to an urban setting, considering complexities like time windows, heterogeneous vehicles, and multiple trips per vehicle per day. We propose a two-phase matheuristic solution algorithm, and compare its results to a baseline approach in which inventory and routing decisions are made sequentially. Computational results demonstrate that the integrated approach consistently outperforms the traditional sequential approach. A detailed analysis of instance characteristics influencing the outcome of these scenarios highlights the impact of variables such as the number of retailers and suppliers, and holding costs. A sensitivity analysis identifies critical factors affecting the implementation of the integrated scenario, emphasising the importance of retailer storage capacity, order costs, and retailer participation. The findings highlight the overall potential benefits of integration, including cost savings, improved resource utilisation, and positive impacts on all stakeholders involved.

Large‐Scale Mobility On‐Demand System With Shared Autonomous Electric Vehicles

Chijia Liu, Alain Quilliot, Hélène Toussaint, Dominique Feillet — Mon, 16 Feb 2026 01:22:58 -0800

ABSTRACT

We investigate a prospective Ride-Sharing Mobility-on-Demand system designed to replace a significant portion of private car usage in European cities within a few years with affordable services operated by Shared Autonomous Electric Vehicles. A key feature of such a system is its ability to handle a very large number of transportation requests. We address both vehicle routing and energy management from a strategic perspective. Our goals are to estimate the fleet size, design prototype routes, and manage energy costs, while accounting for statistical demand patterns, various charging modes, and time-dependent electricity prices. To achieve this, we introduce a decomposition scheme, DECO, which separates routing from recharge scheduling but allows their interaction via an aggregated fleet activity profile. This approach helps maintain energy feasibility under daily demand variations. We conduct numerical experiments on the urban network of Clermont–Ferrand, France, using 1400 designated pickup and drop-off nodes. The simulated system serves up to 300 000 passenger requests with 10-seat SAEVs having a range of 200 km. Results show that over 1700 vehicles are needed to serve all requests while accounting for energy constraints, under an average occupancy of around five passengers during peak hours. Analysis of charging behavior highlights off-peak recharging preferences and cost-sensitive mode selection. We further validate our heuristic DECO by comparing it with a baseline heuristic and with exact Mixed Integer Linear Program (MILP) solutions on small instances, demonstrating its ability to produce high-quality results.

Scenario‐Based Platoon Lane Network Design

Anirudh Kishore Bhoopalam, Niels Agatz, Martin Savelsbergh — Thu, 12 Feb 2026 23:35:54 -0800

ABSTRACT

A truck platoon is a set of trucks that drive behind one another at short headways to save fuel, reduce emissions, and improve traffic throughput. Despite the potential benefits of platooning, road operators have raised concerns about the impact of platoons on surrounding traffic. The use of dedicated platoon lanes helps prevent potentially dangerous situations when interacting with regular traffic. Furthermore, dedicated platooning lanes can help increase platooning benefits and prolong the life of infrastructure. Such types of infrastructure design decisions typically have to be made when the demand that the infrastructure needs to support is uncertain. One way to represent uncertain demand in optimization models is by means of possible realizations or scenarios. Using many scenarios is likely to produce better solutions, but it also creates computational challenges. We propose an approach that blends solutions, each obtained using an optimization model with relatively few scenarios. We use this approach in the context of locating dedicated truck platoon lanes. Computational experiments show that blending designs obtained with a few scenarios is as effective, but much more efficient, as creating a design using many scenarios.

A Dynamic Capacitated Facility Location Problem With Modular Capacities and Best Service Assignment: A Comparison of Formulations

Bernardetta Addis, Giuliana Carello, Gaël Reynal — Wed, 04 Feb 2026 04:25:51 -0800

ABSTRACT

This paper introduces a variant of the dynamic Facility Location Problem with modular capacities. Inspired by the challenges faced by cellular telecommunication networks, the problem seeks to optimize the placement and equipment of facilities to meet the fluctuating demand of clients while minimizing installation and operational costs. Selected facilities must provide coverage to the whole considered area. In addition, clients must be served by the active facility that provides the best quality of service. We propose two integer linear programming formulations and analyze their theoretical properties in terms of lower bound. Furthermore, we propose a reinforcement for one formulation and valid inequalities. To evaluate the performance of the proposed formulations, we performed computational experiments with a commercial solver on instances with up to 20 candidate sites and 60 clients. The formulations proved to be very sensitive to the size of the instances. The analysis, both theoretical and numerical, provides meaningful insights on the formulations performance, and it constitutes a key starting point for developing further approaches, either exact methods or heuristics.

Finding Maximum Weight 2‐Packing Sets on Arbitrary Graphs

Jannick Borowitz, Ernestine Großmann, Christian Schulz — Wed, 28 Jan 2026 02:02:38 -0800

ABSTRACT

A 2-packing set for an undirected, weighted graph G=(V,E,w)$$ G=\left(V,\kern0.3em E,\kern0.3em w\right) $$ is a subset 𝒮⊆V such that any two vertices v1,v2∈𝒮 are not adjacent and have no common neighbors. The Maximum Weight 2-Packing Set problem that asks for a 2-packing set of maximum weight is NP$$ \mathbf{NP} $$-hard. Next to 13 novel data reduction rules for this problem, we develop two new approaches to solve this problem on arbitrary graphs. First, we introduce a preprocessing routine that exploits the close relation of 2-packing sets to independent sets. This makes well-studied independent set solvers usable for the Maximum Weight 2-Packing Set problem. Second, we propose an iterative reduce-and-peel approach that utilizes the new data reductions. Our experiments show that our preprocessing routine gives speedups of multiple orders of magnitude, while also improving solution quality and memory consumption compared to a naive transformation to independent set instances. Furthermore, it solves 44% of the instances tested to optimality. Our heuristic can keep up with the best-performing maximum weight independent set solvers combined with our preprocessing routine. Additionally, our heuristic can find the best solution quality on the biggest instances in our data set, outperforming all other approaches. When using our data reduction rules for exact solvers, we can solve more instances to optimality and are overall multiple orders of magnitude faster.

Assessing the Impact of Driver Overtime in the Distribution Network of a Flower Retail Chain

Christian Braathen, Mario Guajardo — Fri, 23 Jan 2026 05:15:23 -0800

ABSTRACT

This article studies the impact of social constraints on the vehicle routing problem, with a particular focus on allowing overtimes for the drivers. Working overtime is common in practice, as it may improve driver utilization, but it also requires a more detailed cost structure in the routing problem. Motivated by an application at a florist company performing daily routes in a network of stores in Norway, we address a problem characterized by deliveries and split pickups, a heterogeneous fleet of capacitated trucks and a heterogeneous workforce of drivers. We tackle the problem by a route-based mixed integer linear programming model. The objective of the model is to minimize a cost function, which includes route-driving costs for ordinary working hours, overtime costs, plus the additional time picking up carts at pickup locations. The time workload of the drivers is also captured in several social constraints. The results outperform manually produced solutions and a commercial software, with cost reductions totaling 17.4%–36.4% and 9.7%–25.5%, respectively. The results also show how the routes and costs differ when different allowances of overtime are used in the model. Notably, the results illustrate that overtimes are beneficial for cost savings and they are most valuable to serve locations far away from the headquarters. We also compute results for when the cost minimization objective function is replaced by a distance minimization function. A comparison reveals that the distance minimization results may deviate significantly from the cost minimization results.

An Exact Method for Reliable Shortest Path Problems With Correlation

Esteban Leiva, Santiago Morales, Daniel Yamín, Andrés L. Medaglia — Sun, 18 Jan 2026 12:42:08 -0800

ABSTRACT

Shortest path problems often arise in contexts where travel times are uncertain. In these settings, reliable paths are often valued more than paths with lower expected travel times. This has led to several variants of reliable shortest path problems (RSPP) that handle travel time reliability differently. We propose an algorithmic framework for solving RSPPs with non-negatively correlated travel times and resource constraints. By building upon the flexibility of the pulse algorithm, our unified and exact algorithmic framework solves multiple variants of the RSPP: the α$$ \alpha $$-reliable shortest path (α$$ \alpha $$-RSP), the maximum probability of on-time arrival (MPOAP) problem, and the shortest α$$ \alpha $$-reliable path (S-αRP$$ \alpha \mathrm{RP} $$). We derive a bound on the reliability of path travel times and incorporate three pruning strategies: bounds, infeasibility, and dominance, leveraging properties of the normal distribution and non-negative correlation structures. Computational experiments on large-scale transportation networks (with up to 33 113 nodes and 75 379 arcs) demonstrate that the framework achieves a ten-fold speed improvement over state-of-the-art methods, highlighting its potential real-world applications and extensions to related problems.

Robustness Assessment of Public Transport Networks in Various Graph Representations: Systematic Review, Decision Support, and Case Study

Michael Palk, Stefan Voß, Raka Jovanovic — Thu, 15 Jan 2026 14:20:26 -0800

ABSTRACT

The analysis of certain properties of the underlying graph of a public transport network generates insights about the network's structure. Hereby, the choice of the graph representation depends on a trade-off between complexity reduction and information preservation to adequately model a public transport network. The structure of the graph determines the robustness of the network and how resilient it is to disturbances like the breakdowns of stations. In this article, local and global properties of a graph are examined, which can be utilized as robustness indicators for long-term infrastructure planning, as well as the interplay with the choice of the graph representation, data availability, and assessment method. Furthermore, decision support is provided to guide the evaluation of the robustness of real-world public transport networks from multiple perspectives using open data sources. These concepts are illustrated in a case study for the rapid transit and subway system in Hamburg, Germany.