We consider assignment policies that allocate resources to requesting users, where everyone is located on a one-dimensional line. First, we consider a unidirectional problem where a resource can only be allocated to a user located to its leftas exemplified here. Imagine a one-way city street with traffic flowing from right to left; a ride-sharing company has distributed its vehicles along the street, which are ready to pick up users waiting at various locations. Users equipped with smartphone ride-hailing apps can register their requests on a ride allocation system. The latter then attempts to service each user by assigning a vehicle with spare capacity located to the user's right such that the average "pick up" distance is minimized. We propose the Move to Right (MTR) policy which assigns the nearest available resource located to the right , and contrast it with the Unidirectional Gale-Shapley (UGS) Matching policyknown in the literature . While both these policies are optimal  , we show that they are equivalent with respect to the expected distance traveled by a request (request distance), although MTR tends to be fairer, i. e., has low variance. Moreover, we show that when the locations of users and resources are modeled by statistical point processes,  the spatial system under unidirectional policies can be mapped to a temporal queuing system , thus allowing the application of a plethora of queuing theory results that yield closed form expressions.  We also consider the bidirectional problem where there are no directional restrictions on resource allocation and give an optimal policy that has lower expected time complexity than known algorithms in literature in resource rich regimes . Finally, numerical evaluation of performance of unidirectional and bidirectional allocation schemes yield design guidelines beneficial for resource placement.
We consider assignment policies that allocate resources to users, where both resources and users are located on a one-dimensional line. First, we consider unidirectional assignment policies that allocate resources only to users located to their left. We propose the Move to Right (MTR) policy , which scans from left to right assigning nearest rightmost available resource to a user , and contrast it to the Unidirectional Gale-Shapley (UGS) matching policy . While both these policies are optimal among all unidirectional policies , we show that they are equivalent with respect to the expected distance traveled by a request (request distance), although MTR is fairer. Moreover, we show that when user and resource locations are modeled by statistical point processes, and resources are allowed to satisfy more than one user, the spatial system under unidirectional policies can be mapped into bulk service queuing systems , thus allowing the application of a plethora of queuing theory results that yield closed form expressions. As we consider a case where different resources can satisfy different numbers of users, we also generate new results for bulk service queues. We also consider bidirectional policies where there are no directional restrictions on resource allocation and develop an algorithm for computing the optimal assignment which is more efficient than known algorithms in the literature when there are more resources than users . Finally, numerical evaluation of performance of unidirectional and bidirectional allocation schemes yields design guidelines beneficial for resource placement.
D
requesting
R
everyone is
both resources and users are
R
a unidirectional problem where a resource can only be allocated to a user located to its leftas exemplified here. Imagine a one-way city street with traffic flowing from right to left; a ride-sharing company has distributed its vehicles along the street, which are ready to pick up users waiting at various locations. Users equipped with smartphone ride-hailing apps can register their requests on a ride allocation system. The latter then attempts to service each user by assigning a vehicle with spare capacity located to the user's right such that the average "pick up" distance is minimized.
unidirectional assignment policies that allocate resources only to users located to their left.
R
which assigns the nearest available resource located to the right
, which scans from left to right assigning nearest rightmost available resource to a user
R
with
to
R
Matching policyknown in the literature
matching policy
A
among all unidirectional policies
R
tends to be fairer, i. e., has low variance.
is fairer.
R
the locations of users and resources
user and resource locations
A
and resources are allowed to satisfy more than one user,
R
to a temporal queuing system
into bulk service queuing systems
A
As we consider a case where different resources can satisfy different numbers of users, we also generate new results for bulk service queues.
R
the bidirectional problem
bidirectional policies
R
give an optimal policy that has lower expected time complexity
develop an algorithm for computing the optimal assignment which is more efficient
R
literature in resource rich regimes
the literature when there are more resources than users
R
yield
yields