Crowd-Sourced Delivery Services (CDS) use in-store customers, as crowd-shippers, to deliver online orders directly to other customers. As independent contractors, the crowd-shippers are free to decide whether to accept or reject the online orders assigned by the retailer. High order rejection rates can significantly influence the retailer’s delivery costs due to frequent reassignments and shifting the orders to more expensive professional fleet. To incentivize crowd-shippers to accept the matched orders, in this work, we propose a two-stage optimization framework that integrates bipartite matching with an individual compensation scheme. The first stage of the optimization framework computes the optimal matching between crowd-shippers and online orders to minimize the delivery detours and unassigned orders. Given the matching solutions as inputs, the second stage computes personal compensation for each crowd-shipper based on the characteristic of the matched order and his or her acceptance behavior uncertainty, with the goal of minimizing the expected total delivery cost of the retailer. Numerical experiments are conducted using the survey data to illustrate the performance of the proposed framework and compare it with existing matching and pricing strategies in the literature. Our results show that the proposed framework reduces the delivery cost by up to more than 15% and reduces the crowd-shippers’ rejection rate by an average of 55%.@en

Vehicle proactive guidance strategies are used by ride-hailing platforms to mitigate supply–demand imbalance across regions by directing idle vehicles to high-demand regions before the demands are realized. This article presents a data-driven stochastic optimization framework for computing idle vehicle guidance strategies. The objective is to minimize drivers’ idle travel distance, riders’ wait time, and the oversupply costs (OSCs) and undersupply costs (USCs) of the platform. Specifically, we design a novel neural network that integrates gated recurrent units (GRUs) with mixture density networks (MDNs) to capture the spatial-temporal features of the rider demand distribution.@en

The unprecedented growth of demand for charging electric vehicles (EVs) calls for novel expansion solutions to today’s charging networks. Riding on the wave of the proliferation of sharing economy, Airbnb-like charger sharing markets open the opportunity to expand the existing charging networks without requiring costly and time-consuming infrastructure investments, yet the successful design of such markets relies on innovations at the interface between game theory, mechanism design, and large scale optimization. In this paper, we propose a price-based iterative double auction for charger sharing markets where charger owners rent out their under-utilized chargers to the charge-needing EV drivers. Charger owners and EV drivers form a two-sided market which is cleared by a price-based double auction. Chargers’ locations, availabilities, and unit time service costs as well as drivers’ time and location preferences are considered in the allocation and scheduling process. The goal is to compute social welfare maximizing schedules which benefit both charger owners and EV drivers and, in turn, ensure the continuous growth of the market. We prove that the proposed double auction is budget balanced and individually rational. In addition, results from our computational study show that the proposed auction achieves on average 94% efficiency compared with that of the optimal solutions and is suitable for a larger day-ahead charger sharing market setting in terms of running time.@en

Providing high-quality matching between drivers and riders is imperative for sustaining the growth of ride-sharing platforms. A user-focused matching mechanism design plays a key role in terms of ensuring user satisfaction. In this paper, we consider the matching problem in the community ride-sharing setting, where drivers and riders have strong personal preferences over the matched counterparties. Obtaining high-quality solutions that accommodate drivers’ and riders’ preferences in such a setting is particularly challenging as drivers and riders maybe reluctant to share with the platform their personal preferences over their ride-sharing counterparties due to privacy and ethical concerns. To this end, we propose a VOting-based MAtching (VOMA) mechanism to compute near-optimal matching solutions for drivers and riders, while preserving their privacy. The mechanism is a distributed implementation of the simulated annealing meta-heuristic, which computes matching solutions by guiding drivers and riders in the distributed search process using an iterative voting protocol. We evaluate the performance of VOMA using test cases generated based on New York taxi data sets. The experiment results show that the proposed matching mechanism achieves on average 90.9% efficiency compared with optimal solutions. We also show that VOMA improves the vehicle miles traveled (VMT) savings by up to 35% compared to an alternative voting-based greedy matching mechanism. System scalability and other practical issues regarding the implementation of such a matching mechanism in community ride-sharing platforms are also discussed.@en

This paper proposes an integrated dispatching framework for matching drivers with riders in ride-hailing systems. The goal is to compute matching solutions that maximize social welfare and benefit both sides of the market, such that the sustainable growth of the ride-hailing system is ensured. The proposed framework integrates data-driven proactive guidance strategies with batched matching optimization to increase social welfare, improve matching rate and reduce rider wait time. Proactive guidance strategies are computed by leveraging short-term demand forecasts based on historical data. Taken the resulting guidance strategies as inputs, the batched matching algorithm computes optimal bipartite matching between drivers and riders in a batch. Using New York City taxi data from 2016 March 1st to March 31st as input, we conduct a numerical study to evaluate the performance of the proposed framework and compare it with existing approaches in the literature. Our results show that the proposed framework improves social welfare for up to 50%. It also increases the matching rate by an average of 20% and reduces the average rider wait time by over 15%. This implies a strong potential for the proposed dispatching framework to improve service quality in ride-hailing systems.@en

To reduce the vehicle relocation rate considering relieving disequilibrium of the supply-demand ratios across regions for car-sharing systems, in this paper, we propose a data-driven optimization framework by integrating the non-parametric learning algorithm and two-stage stochastic programming modeling technique to address the one-way station-based car-sharing relocation problem. In contrast with the most existing work that deals with demand uncertainty using predefined probability distributions, the learning-based framework is capable of handling demand uncertainty by learning the intrinsic pattern from large-scale historical data and computing high quality solutions. To validate the performance of our proposed approach, we conduct a group of numerical experiments based on New York taxicab trip record data set. The experimental results show that our proposed data-driven approach outperforms the parametric approaches and deterministic model in terms of business profit, relocation rate, and value of stochastic solution (VSS). Most significantly, compared with the deterministic approach, the vehicle relocation rates are reduced by approximate 80%, 70% and 40% under small fleet size, medium fleet size and large fleet size, respectively. In addition, the VSS of our approach is more than 3 times higher than the one of Poisson distribution by average.

@en

Freelance drivers in ride-hailing systems may strategically accept or reject ride requests based on their projection of the profitability of the assigned rides. This driver acceptance uncertainty is mainly caused by the flat rate payment and the blind ride acceptance rule adopted by most ride-hailing platforms. As a result, a high driver rejection rate has been observed, causing a negative impact on the service quality and matching efficiency for the ride-hailing systems. In this paper, we propose a pricing mechanism to improve drivers’ average ride acceptance rate by offering personalized payments computed based on the characteristics of individual riders and the estimated acceptance rates of the drivers. Specifically, we model and predict the drivers’ ride acceptance rates through a binary choice model and incorporate it into the stochastic optimization problem for the ride-hailing system. This provides personalized payment for each driver in connection with the characteristics of the assigned ride and the preferences of the drivers. We then evaluate the performance of the proposed pricing mechanism through extensive numerical experiments based on RideAustin trip data from June 2016 to April 2017. The results suggest that our proposed pricing mechanism improves the drivers’ average acceptance rate by an average of 60% compared to some commonly used pricing schemes. It also significantly increases the platform’s expected profit and matching rate. This implies a strong potential for the proposed pricing mechanism to improve service reliability and quality in ride-hailing systems.@en

In ride-sharing services, travel time uncertainty significantly impacts the quality of matching solutions for both the drivers and the riders. This paper studies a one-to-many ride-sharing matching problem where travel time between locations is uncertain. The goal is to generate robust ride-sharing matching solutions that minimize the total driver detour cost and the number of unmatched riders. To this end, we formulate the ride-sharing matching problem as a robust vehicle routing problem with time window (RVRPTW). To effectively capture the travel time uncertainty, we propose a deep learning-based data-driven approach that can dynamically estimate the uncertainty sets of travel times. Given the NP-hard nature of the optimization problem, we design a hybrid meta-heuristic algorithm that can handle large-scale instances in a time-efficient manner. To evaluate the performance of the proposed method, we conduct a set of numeric experiments based on real traffic data. The results confirm that the proposed approach outperforms the non-data-driven one in several important performance metrics, including a proper balance between robustness and inclusiveness of the matching solution. Specifically, by applying the proposed data-driven approach, the matching solution violation rate can be reduced up to 85.8%, and the valid serving rate can be increased up to 42.3% compared to the non-data-driven benchmark.@en

We propose a data-driven optimization model to reduce riders' wait time for vehicle guidance and rebalancing operations, considering the rider demands are under uncertainty. Instead of assuming a pre-defined rider demand distribution, we propose a data-driven framework that integrates Mixture Density Networks (MDNs) and a two-stage stochastic programming model. The integrated framework can compute high-quality guidance and rebalancing solutions that benefit drivers and riders in the ride-hailing system by leveraging the time-series historical data from real data sets. To prove the performance and effectiveness of our approach, we conduct a group of simulations based on the New York High Volume For-Hire Vehicle (HVFHV) trip records. The validation results show that the proposed method outperforms the data-driven deterministic models using GRU and moving average methods. Most significantly, the riders' average wait time using our proposed approach can be reduced by 75.9% compared to the batched matching mechanism.

@en

As an alternative to traditional taxi services, Transportation Network Companies (TNCs) such as Uber and Lyft are playing an increasingly important role in the paradigm shifting from car ownership to mobility as a service. We consider an electric vehicle fleet charging scheduling problem in the TNC setting where taxi drivers, as freelancers, have their individual preferences regarding when and where to charge their vehicles. In this setting, obtaining social welfare maximizing schedules is particularly difficult as drivers may behave strategically in competing over shared charging resources to advance their own benefits rather than the system wide social welfare. We propose a negotiation mechanism which allows drivers to collectively evolve an incumbent schedule into a socially beneficial one through an iterative voting process. The proposed mechanism provides a platform which enables multilateral negotiation among a large number of drivers. We prove that, given the design of the proposed mechanism, drivers’ best response strategy is to truthfully vote their best valued candidate schedules according to the acceptance quota prescribed by the scheduler at each voting round. In addition, experiment results show that the mechanism achieves on average 93% efficiency compared with optimal solutions and scales well to larger problem instances.

@en

In this paper, we propose a data-driven robust optimization model to reduce total travel cost in ride-sharing systems under travel time uncertainty. Instead of using a pre-defined uncertainty set, we study a data-driven robust optimization approach that integrates gated recurrent units (GRUs) predictions with a one-stage robust optimization model. The proposed approach has the ability to compute high quality solutions by leveraging the large-scale historical data to derive the uncertainty set for the designed robust optimization model. To evaluate the proposed approach, we conduct a group of simulations based on the New York taxi trip record data sets. The validation results show that our data-driven robust optimization approach outperforms the robust optimization approach with a pre-defined uncertainty set in terms of travellers' total travel cost. Most importantly, the total travel cost under the proposed approach is reduced by up to 31.7%, and by 26.7% on average compared with the robust model with a pre-defined uncertainty set.

@en

In this paper, we study a one-to-one matching ride-sharing problem to save the travellers' total travel time considering travel time uncertainty. Unlike the existing work where the uncertainty set is assumed to be known or roughly estimated, in this work, we propose a learning-based robust optimization framework to handle the issue properly. Specifically, we assume the travel time varies in an uncertainty set which is predicted by a machine learning approach- ARIMA using travel time historical data, the predicted uncertainty set then serves as the input parameter for the robust optimization model. To evaluate the proposed approach, we conduct a group of numerical experiments based on New York taxi trip record data sets. The results show that our proposed data-driven robust optimization approach outperforms the robust optimization model with a given uncertainty set in terms of total travel time savings. Further, the proposed approach can improve the travel time savings up to 112.8%, and 34% by average. Most importantly, our proposed approach is capable of handling the uncertainty in a more effective way when the uncertainty degrees become high.

@en

We propose a learning-based approach for open driver guidance and rebalancing in ride-hailing platforms. The objective is to further enhance the wait time reduction benefit of batched matching by incorporating learning-based open driver guidance and rebalancing. By leveraging the rider demand data, the guidance solutions are computed through the integration of machine learning techniques with a two-stage stochastic programming model. To validate the performance of the proposed approach, we conduct numerical experiments using the New York taxi trip data sets. Our results show that the proposed approach outperforms the single value estimation model and the parametric model using Poisson distribution in terms of average wait time. When assuming the open drivers are randomly located before the batching time window, the proposed approach reduces more than 70% of average wait time compared to batched matching without guidance.

@en

Consider a decentralized electric vehicle (EV) charging scheduling problem where the chargers and vehicles are modeled as utility maximizing agents. To schedule chargers to vehicles in a day-ahead market, we propose a double auction mechanism, where chargers report their time availabilities and charging costs and vehicles report their preferences on different chargers. This auction is conducted in an iterative manner which enables the computation of effective schedules through multilateral negotiation between agents. We evaluate the efficiency performance of the mechanism through a computational study. The result generated from the iterative double auction mechanism is on average 35% better than the first come first serve (FCFS) allocation policy.

@en

This paper presents a multiagent systems model for patient diagnostic services scheduling. We assume a decentralized environment in which patients are modeled as self-interested agents who behave strategically to advance their own benefits rather than the system wide performance. The objective is to improve the utilization of diagnostic imaging resources by coordinating patient individual preferences through automated negotiation. The negotiation process consists of two stages, namely patient selection and preference scheduling. The contract-net protocol and simulated annealing based meta-heuristics are used to design negotiation protocols at the two stages respectively. In terms of game theoretic properties, we show that the proposed protocols are individually rational and incentive compatible. The performance of the preference scheduling protocol is evaluated by a computational study. The average percentage gap analysis of various configurations of the protocol shows that the results obtained from the protocol are close to the optimal ones. In addition, we present the algorithmic properties of the preference scheduling protocol through the validation of a set of eight hypotheses.

@en

This paper proposes a negotiation protocol for outpatient diagnostic services scheduling in a collaborative setting where each patient has private preference values over available service time slots and the overall schedule is achieved through negotiation among patients. With the objective of maximizing the social welfare of patients, the key challenge is how to integrate patients' private preference values in time slot allocation decisions such that high-quality solutions which benefit all the patients can be obtained. We use simulated annealing as the optimization meta-heuristic for designing our automated negotiation protocol through which patients collaboratively improve the overall preference value of the solution. The results from our computational study show that the proposed negotiation protocol achieves on average 95% efficiency compared with optimal solutions.

@en