اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMatching Impatient and Heterogeneous Demand and Supply
207
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Service platforms must determine rules for matching heterogeneous demand (customers) and supply (workers) that arrive randomly over time and may be lost if forced to wait too long for a match. We show how to balance the trade-off between making a less good match quickly and waiting for a better match, at the risk of losing impatient customers and/or workers. When the objective is to maximize the cumulative value of matches over a finite-time horizon, we propose discrete-review matching policies, both for the case in which the platform has access to arrival rate parameter information and the case in which the platform does not. We show that both the blind and nonblind policies are asymptotically optimal in a high-volume setting. However, the blind policy requires frequent re-solving of a linear program. For that reason, we also investigate a blind policy that makes decisions in a greedy manner, and we are able to establish an asymptotic lower bound for the greedy, blind policy that depends on the matching values and is always higher than half of the value of an optimal policy. Next, we develop a fluid model that approximates the evolution of the stochastic model and captures explicitly the nonlinear dependence between the amount of demand and supply waiting and the distribution of their patience times. We use the fluid model to propose a policy for a more general objective that additionally penalizes queue build-up. We run numerous simulations to investigate the performance of the aforementioned proposed matching policies.
قيم البحث
اقرأ أيضاً
In this paper, to optimize the Wireless Charging Lane (WCL) deployment in urban areas, we focus on installation cost reduction while achieving regional balance of energy supply and demand, as well as vehicle continuous operability issues. In order to
explore the characteristics of energy demand in various regions of the city, we first analyze the daily driving trajectory of taxis in different regions and find that the daily energy demand fluctuates to different degrees in different regions. Then, we establish the WCL power supply model to obtain the wireless charging supply situation in line with the real urban traffic condition, which is the first work considering the influence of traffic lights on charging situation. To ensure minimum deployment cost and to coordinate the contradiction between regional energy supply-demand balance and overall supply-demand matching, we formulate optimization problems ensuring the charge-energy consumption ratio of vehicles. In addition, we rank the priority of WCL efficiency to reduce the complexity of solution and solve the Mixed Integer NonLinear Programming (MINLP) problem to determine deployment plan. Compared with the baseline, the proposed method in this paper has significantly improved the effect.
Performance and energy are the two most important objectives for optimisation on modern parallel platforms. Latest research demonstrated the importance of workload distribution as a decision variable in the bi-objective optimisation for performance a
nd energy on homogeneous multicore clusters. We show in this work that bi-objective optimisation for performance and energy on heterogeneous processors results in a large number of Pareto-optimal optimal solutions (workload distributions) even in the simple case of linear performance and energy profiles. We then study performance and energy profiles of real-life data-parallel applications and find that their shapes are non-linear, complex and non-smooth. We, therefore, propose an efficient and exact global optimisation algorithm, which takes as an input most general discrete performance and dynamic energy profiles of the heterogeneous processors and solves the bi-objective optimisation problem. The algorithm is also used as a building block to solve the bi-objective optimisation problem for performance and total energy. We also propose a novel methodology to build discrete dynamic energy profiles of individual computing devices, which are input to the algorithm. The methodology is based purely on system-level measurements and addresses the fundamental challenge of accurate component-level energy modelling of a hybrid data-parallel application running on a heterogeneous platform integrating CPUs and accelerators. We experimentally validate the proposed method using two data-parallel applications, matrix multiplication and 2D fast Fourier transform (2D-FFT).
We consider a setting with an evolving set of requests for transportation from an origin to a destination before a deadline and a set of agents capable of servicing the requests. In this setting, an assignment authority is to assign agents to request
s such that the average idle time of the agents is minimized. An example is the scheduling of taxis (agents) to meet incoming requests for trips while ensuring that the taxis are empty as little as possible. In this paper, we study the problem of spatial-temporal demand forecasting and competitive supply (SOUP). We address the problem in two steps. First, we build a granular model that provides spatial-temporal predictions of requests. Specifically, we propose a Spatial-Temporal Graph Convolutional Sequential Learning (ST-GCSL) algorithm that predicts the service requests across locations and time slots. Second, we provide means of routing agents to request origins while avoiding competition among the agents. In particular, we develop a demand-aware route planning (DROP) algorithm that considers both the spatial-temporal predictions and the supplydemand state. We report on extensive experiments with realworld and synthetic data that offer insight into the performance of the solution and show that it is capable of outperforming the state-of-the-art proposals.
How to dynamically measure the local-to-global spatio-temporal coherence between demand and supply networks is a fundamental task for ride-sourcing platforms, such as DiDi. Such coherence measurement is critically important for the quantification of
the market efficiency and the comparison of different platform policies, such as dispatching. The aim of this paper is to introduce a graph-based equilibrium metric (GEM) to quantify the distance between demand and supply networks based on a weighted graph structure. We formulate GEM as the optimal objective value of an unbalanced transport problem, which can be efficiently solved by optimizing an equivalent linear programming. We examine how the GEM can help solve three operational tasks of ride-sourcing platforms. The first one is that GEM achieves up to 70.6% reduction in root-mean-square error over the second-best distance measurement for the prediction accuracy. The second one is that the use of GEM for designing order dispatching policy increases answer rate and drivers revenue for more than 1%, representing a huge improvement in number. The third one is that GEM is to serve as an endpoint for comparing different platform policies in AB test.
We consider a distribution grid used to charge electric vehicles such that voltage drops stay bounded. We model this as a class of resource-sharing networks, known as bandwidth-sharing networks in the communication network literature. We focus on res
ource-sharing networks that are driven by a class of greedy control rules that can be implemented in a decentralized fashion. For a large number of such control rules, we can characterize the performance of the system by a fluid approximation. This leads to a set of dynamic equations that take into account the stochastic behavior of EVs. We show that the invariant point of these equations is unique and can be computed by solving a specific ACOPF problem, which admits an exact convex relaxation. We illustrate our findings with a case study using the SCE 47-bus network and several special cases that allow for explicit computations.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
