We study the Service-Aware Multi-Commodity Flow (SAMCF) problem, in which demand is elastic and governed by a logit choice model while routing is subject to hard capacity constraints. In a centralized, system-optimal setting, the network operator jointly determines how much demand to serve and how to route it. We formulate the SAMCF as a nonlinear program and propose an iterative fixed-point heuristic that alternates between solving an inelastic MCF via column generation and updating demand from the resulting service levels. Two linear approximations based on piecewise-linear demand functions and McCormick envelopes serve as benchmarks, while a piecewise-linear outer-approximation of the demand function is used to provide valid lower bounds. Computational experiments on public transport instances show that the heuristic finds near-optimal solutions in under two seconds - orders of magnitude faster than the benchmark methods - while matching their solution quality on all instances they can solve within a ten-minute time limit.
This paper investigates the scalability of a multi-criteria optimization for the Service Team Transport Scheduling (STTS) problem, minimizing total travel time, maximum vehicle worktime, and total vehicle engagement time. The mathematical model of the problem is provided. A simplified problem representation and two graph-based representations along with problem properties are formulated. Using these properties, we propose two complementary frameworks: a declarative Constraint Optimization Problem (COP) solved via Gurobi, and a metaheuristic Tabu Search (TS) incorporating a Constraint Satisfaction Problem (CSP) and an auxiliary greedy method for obtaining initial feasible solutions. Additionally, the population-based NSGA-II algorithm is implemented as an evolutionary baseline. The solving methods are evaluated under a strict 300-second operational limit using 280 realistic instances. The results reveal clear tractability thresholds. The COP solver obtains high-quality Pareto fronts but experiences a combinatorial collapse beyond 8 customer locations, hitting a 0% success rate for instances with size 15 or more. Conversely, the proposed hybrid CSP-TS framework demonstrate high robustness, maintaining a 90–100% operational success rate up to 50 locations. Specifically, the expansive large-neighborhood TS variant excels at medium scales (14–40 locations), while the compact small-neighborhood TS variant achieves the highest Hypervolume Indicator (HVI) at large scales (45 or more locations). Pure population-based approaches like NSGA-II are consistently outperformed by the specialized local search neighborhood structures. These quantitative findings define scale-aware algorithmic boundaries essential for real-time decision support systems.
Jarosław Rudy, G. Radzki· IEEE Access· 0 citations
The integration of fixed-route public transit and on-demand mobility services presents both a modeling challenge and a computational opportunity for large-scale network design. We propose a flow-based mixed-integer programming formulation that jointly optimizes transit line planning and service frequencies while explicitly capturing first- and last-mile connectivity via on-demand services, under a fixed operating budget. To achieve tractability at urban scale, we develop a novel column generation heuristic scheme with tailored pricing subproblems. Applied to networks and demand in Boston and Chicago, the framework yields operationally feasible designs that substantially increase demand served. Relative to transit-only and on-demand-only baselines, ridership increases by up to 20.99% and 93.58% in Boston, and by up to 10.63% and 149.84% in Chicago. Compared to a multi-modal benchmark, our approach improves ridership by 5.42% and 5.80% in Boston and Chicago, respectively. These results demonstrate that (i) joint co-design of transit routes, frequencies, and on-demand legs within a unified optimization framework yields substantially greater ridership than single-mode or decoupled approaches under equivalent budget constraints; and (ii) the proposed formulation and column generation pricing scheme admit tractable, operationally feasible, high-performing solutions relative to tested baselines.
This work investigates the uncertainty-aware joint pricing and matching problem for dynamic high-capacity ride-sharing services, where passengers are assumed to be price-elastic and decide whether to accept a ride-sharing offer based on the upfront prices provided by the platform. We formulate the studied problem as a two-stage stochastic program, where the first stage optimizes upfront price decisions for passengers, and the second-stage recourse problem captures passenger-vehicle assignment based on passengers'uncertain choices. To enhance computational efficiency, we introduce a novel relaxation-based gradient descent-guided search algorithm that leverages the problem's structural properties. Initially, the algorithm generates a feasible solution for the first-stage problem via relaxation. It then iteratively improves the solution via a search process guided by the derived gradient information. In particular, scenario reduction is applied to eliminate unnecessary scenarios when calculating the gradient, thereby reducing the overall computational burden. Numerical experiments demonstrate that, compared to solving the stochastic program directly, the proposed algorithm can accelerate computation speed by thousands of times while achieving optimality gaps of no more than 1.1%. Finally, we validate the benefits of considering passengers'choice uncertainty through large-scale simulation using real-world datasets and road networks over two large cities. The results demonstrate that, on average, the proposed method can increase the revenue by 5.2% and the service rate by 8.2% compared to the baseline approaches. This study provides a valuable reference for transportation network companies to design pricing strategies for ride-sharing to enhance service efficiency and improve revenue.
Wang Chen, Xinglu Liu, Kaihang Zhang et al.· 0 citations
Finding a routing path that satisfies two independent additive constraints (e.g., delay and cost) is a critical requirement in quality of service (QoS) routing. While this two-constraint path problem is NP-Hard, it is prevalent in practical network applications. Existing solutions typically face a trade-off: heuristics lack feasibility guarantees, while exact algorithms suffer from exponential computational complexity. In this paper, we propose a dual-guided exact algorithm that effectively bridges the gap between the computational efficiency of Lagrangian relaxation and the optimality guarantees of combinatorial search. Our method first solves the Lagrangian dual problem to derive the optimal multiplier, which subsequently serves as the optimal aggregate coefficient to guide a heuristic A*-prune search. This hybrid mechanism allows the algorithm to efficiently prune the search space while guaranteeing the identification of a cost-efficient feasible solution. Numerical experiments on random network topologies demonstrate that the proposed algorithm significantly outperforms the standard A*-prune algorithm while maintaining exactness. Specifically, in networks with up to 500 nodes, our method reduces the execution time by orders of magnitude compared to traditional exact methods.
Kaixiang Hu, Xiankai Li, Caixia Kou· International Journal of Fou...· 0 citations
This paper studies a multi-tenant resource allocation problem in a satellite open radio access network (O-RAN) wholesale setting, where heterogeneous traffic classes share a time-varying limited satellite capacity over a finite planning horizon. We formulate a joint pricing and reserve allocation problem from a service provider perspective, where tenant-specific demand exhibits price elasticity and stochastic service requirements subject to strict service-level agreement (SLA) constraints, leading to a coupled economic and reliability-driven bottleneck. A deterministic reformulation is adopted to approximate probabilistic SLA requirements through tractable margin constraints, enabling coordinated control of horizon-wide contract prices and time-varying reserves. The resulting problem is non-convex due to interdependent decisions across tenants, time windows, and service classes. To address this, an alternating optimization (AO) scheme is developed separating pricing and allocation decisions while preserving feasibility and SLA guarantees. Numerical results show that the proposed method achieves near-optimal profit within approximately $1\%$ of a global benchmark, while reducing runtime by up to $22\times$. In contrast, considered baseline schemes incur profit losses exceeding $15\%$ or fail to satisfy SLA constraints. The proposed approach consistently maintains non-positive empirical SLA gaps and achieves up to $30\%$ higher resource utilization than a price-optimization baseline without adaptive reserve control. These results demonstrate that joint economic and resource control enables the provider to efficiently exploit scarce satellite network capacity with reliable service delivery and scalable computation.
We study an inventory routing problem with time windows (IRPTW). A single supplier serves a set of customers to fulfill their demand throughout a planning horizon. Each customer can be visited only within designated time windows, assuming each customer provides a single delivery time window valid for all periods. We propose a two‐commodity flow formulation for this problem and develop a branch‐price‐and‐cut algorithm to solve it. We test our algorithm on a rich set of benchmark instances with fixed and time‐varying demands and with up to 100 customers. Computational experiments demonstrate the effectiveness of this approach. Within a 2‐hour time limit, it can provide a lower bound for all 492 tested instances. Furthermore, 211 of them are solved to optimality, achieving an average optimality gap of 4.07% for large instances and closing the gap for 11 instances for the first time in the literature.
Sara Charaf, Guy Desaulniers, F. Quesnel et al.· International Transactions i...· 0 citations