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.
In this paper, we propose an integrated matching and pricing algorithm for multi-passenger ride-sharing systems. While ride-sharing is a promising solution for reducing traffic congestion and CO2 emissions, existing mechanisms, particularly the Vickrey-Clarke-Groves (VCG) mechanism, often fail to ensure budget feasibility (i.e., they may result in a budget deficit), which poses a significant challenge to sustainable operation. To address this issue, we formulate the matching and pricing problem as a single optimization problem incorporating a novel budget-feasibility constraint that explicitly prevents system deficits. We prove that the proposed mechanism simultaneously satisfies three critical economic properties: strategy-proofness, individual rationality, and budget feasibility. Furthermore, numerical simulations in the Yokohama area demonstrate that the proposed method maintains a nonnegative system balance even in scenarios where the standard VCG mechanism incurs a deficit, with only a marginal loss in overall social efficiency.
Rino Someya, Toru Namerikawa· Conference on Control Techno...· 0 citations
Overnight rebalancing in dock-based bike-sharing systems requires routing a limited fleet of trucks before user activity begins. This article formulates static rebalancing problem under stochastic demand uncertainty as a bi-objective combinatorial optimization problem that selects truck routes and visited stations. The first objective minimizes total travel distance. The second objective minimizes scenario-weighted unmet demand under a finite set of demand scenarios derived from historical station-status data. A deterministic recourse evaluation simulates truck loads and station inventories along each route and computes unmet demand for visited and unvisited stations. The article applies two multi-objective evolutionary algorithms, NSGA-II and MOEA/D, using a permutation–partition encoding and relocate-based operators that implement a 1–0 relocate neighborhood between routes. A roulette-wheel-based relocation operator (BB2) biases move selection by the induced change in route distance. Experiments on the Barcelona Bicing network with 518 stations and on clustered subinstances show that NSGA-II attains higher hypervolume and larger non-dominated sets, whereas MOEA/D attains lower runtime; an ablation analysis shows that BB2 improves coverage and proximity indicators.
D. Pedroza-Perez, Gabriel Luque, S. Nesmachnow et al.· Journal of combinatorial opt...· 0 citations
This paper considers a crowdsourced delivery platform that integrates both a professional fleet and occasional drivers (ODs) to fulfill customer orders. The delivery willingness of ODs is measured by their maximum tolerable detour time, which is influenced by the compensation price they receive by a compensation-willingness function. Our objective is to minimize total delivery cost by developing an integrated order matching, routing and compensation pricing optimization model for crowdsourced pickup and delivery, in which the compensation price is treated as a decision variable and the compensation-willingness function is incorporated as a behavioral constraint for ODs. To solve this problem, we propose a hybrid algorithm combining an adaptive golden-section search method with adaptive large neighborhood search. Numerical experiments demonstrate that the proposed algorithm is competitive in both solution quality and computation time compared with CPLEX and a multi-start heuristic combining variable neighborhood search and tabu search. A case study indicates that the optimized compensation price scheme maintains ODs’ willingness to perform deliveries and reduces the total delivery cost by approximately 23.5% compared with a constant low compensation price scheme and by about 9.0% compared with a constant high compensation price scheme, thereby effectively preventing resource waste and insufficient incentives
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.
Manobendu Sarker, Günes Karabulut-Kurt, W. Jaafar· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
