Transcript 07_June01_2016x - University of Minnesota

Ephemeral Network Broker to Facilitate
Future Mobility Business
Models/Transactions
A collaboration between Ford University Research Program and
University of Minnesota
University PI:
Shashi Shekhar
Ford PI:
Shounak Athavale
Outline
•
•
•
•
•
•
•
•
•
Motivation
Problem Definition
Toy Example
Challenges
Related Work
Proposed Approach
Contributions
Validation Methodology
Sharing Economy Workshop Updates
Motivation
•
Increasing proliferation of mobile technologies (e.g., smart phones)
– Rise of on-demand sharing economy
•
Additional opportunities:
•
•
Ephemeral networks: groups of people, goods and services encounter each other
in the physical world during routine activities (e.g. commute).
Need to investigate ephemeral network broker that can identify novel
opportunities for commerce among mobile consumers and producers in
ephemeral networks.
Problem Definition: On-demand Service Propositions
•
•
•
•
Input:
– A set of service providers. Each provider is defined using:
• Location coordinates and service types (e.g. grocery shopping, clothing)
• Service rate over the day (e.g. 5/hr in rush hours, 10/hr in non-rush hours)
– A set R of consumer requests arriving dynamically
R = {ri = (time, current location li, destination, service type (with learned preferences), max.
distance detour, max. time before service, max waiting time)}
– k: maximum number of required propositions
– ttimeout : timeout interval length
Output:
– k service provider(s) propositions and estimated service/pick-up time(s) for each ri ϵ R
Objective:
– Maximize number of matched requests (completed transactions?)
Constraints:
– Recommended service provider should meet max. waiting time, max time before service
and max. distance detour constraints for each request
– Real-time scalability/computational efficiency
Toy Example
Input:
Customer 1:
• Max time before
service = 20 mins
• Max detour = 20%
• No waiting time
Customer 2:
• Max time before
service = 20 mins
• Max detour = 20%
•no waiting time
C1
C2
Output:
ttimeout = 1 min
K=1
Provider 1:
service time =
10min
P1
P2
Provider 2:
service time =
10min
Assuming travelling to P1 requires extra 1 mile by both C1 and
C2 while P2 requires 2 miles
Possible Outputs
#matched
requests
#consumers
served
#producers Total travel
assigned
distance
(C1,P1) and (C2,P1)
2
2
1
2
(C1,P2) and (C2,P2)
2
2
1
4
(C1,P1) and (C2,P2)
2
2
2
3
Challenges
• Maximizing the number of matched requests when the requests (i.e.
demand) is unknown in advance.
• Conflicting requirements of broker, producers and consumers
• Scaling to Big Spatio-temporal Data
– Real-time response for megacities
– Providing K propositions for a large number of consumers arriving at time t while
maximizing the number of matched consumers is an NP-hard problem [GeoTruCrowd]
Consumer
Candidate Propositions
C1
(C1, <P1,P2>) (C1, <P1,P3>) (C1, <P2,P3>)
C2
(C2, <P1,P2>) (C2, <P1,P3>) (C2, <P2,P3>)
C3
(C3, <P1,P2>) (C3, <P1,P3>) (C3, <P2,P3>)
Related Work: Spatial Crowdsourcing (1/3)
–
–
Match dynamic spatial tasks to available workers
ACM GIS 2012: GeoCrowd:
•
Constraints: travel region, max task number
(task to only one worker)
•
Algorithms:
–
Greedy
–
least entropy
–
Nearest Neighbor (NN)
Problem is reduced to a minimum cost max. flow:
–
•
•
a) An example of Wi and Ti
Step 1: Ford-Fulkerson algorithm to calc. max flow
t1
t2
Step 2: An optimization problem defined where
1
W1
goal is to minimize total cost of the max flow and
2
(using linear programming.)
–
src
3 W2
t3
1
1
1
t5
1
1
1
1
1
1
t4
t6
1
1
1
t7
1
1
4
Limitations:
1
1
1
t8
W3
•
Workers (i.e. service providers) load may not be
t9
1
balanced. Some workers might starve.
t10
•
Workers are not allowed to reject or choose
b) corresponding flow network
between assigned tasks.
dest
Related Work: Spatial Crowdsourcing (2/3)
–
ACM GIS 2013: GeoTruCrowd: Trustworthy Query Answering With
Crowdsourcing
•
•
•
Each worker has reputation score, each task has confidence level (assign more workers,
analogous to top-K propositions)
Maximize number of assigned tasks such that worker and task confidence level
constraints are satisfied.
Correct match (Task, a subset of workers): a set of workers that satisfies task
(confidence) and worker constraints (region)
–
Problem: select a subset of correct matches such that a task is assigned to at
most one correct match and matching is maximized (NP-hard)
Related Work: Spatial Crowdsourcing (3/3)
•
Algorithms for selecting a subset of the correct matches:
–
Greedy: iteratively assign task to one of its correct matches until no
more possible assignment
–
Local Optimization: Improve initial assignment by local searches
(i.e. replace each correct match if it can be replaced by more than
one other match until no more possible replacements)
–
Heuristic-based Greedy Approach:
»
Remove dominated correct matches (larger worker subsets)
(N/A for ours)
»
Least worker assigned heuristic (LWA): prioritize matches with
less number of workers (N/A for ours)
»
Nearest Neighbor heuristic (Least aggregate distance)
•
Limitations:
–
Workers (i.e. service providers) load may not be balanced. Some
workers might starve.
–
Workers are not allowed to reject assigned tasks.
Limitations of Related Work
GeoCrowd
(Acm GIS 2012)
GeoTruCrowd
(Acm GIS 2013)
Our Work
Fairness
For Tasks-only (i.e.
consumers)
(minimizing task
starvation)
For Tasks-only (i.e.
consumers)
(minimizing task
starvation)
For Consumers and
service providers
(minimizing
starvation of both)
Modeling Autonomy
of entities
Broker-only
Broker-only
Broker and
consumers (models
effect of consumers
autonomy on the
matching algorithm)
Distance Queries
(shortest path)
Point-based (NN
heuristic)
Point-based (NN
heuristic)
Trajectory-based
(detour distance)
Agent-based Simulation Framework
Event types: Consumer arrival, Proposition acceptance, Proposition timeout
Arrival events E
at time t
Other events
(acceptance/timeout)
Find all candidate propositions
for consumers of events E
Update availability of
producers accordingly
Match consumers with
candidate propositions
Heuristics
Update availability of matched
producers & generate
acceptance/timeout events
Output
Simulation
Statistics
Simulation Statistics
• Broker centric:
– % of completed transactions
– % of matched requests
– Throughput (i.e. scalability with number of producers & consumers)
• Consumer centric:
–
–
–
–
Average query response time (until propositions are displayed)
Average waiting time per request
Average distance detour per request
Average time before service per request
• Producer centric:
–
–
–
–
% of producers with completed transactions
% of matched producers
Avg. number of assigned consumers per producer
Standard deviation of the number of assigned consumers per producer
Design Decision: Group of customers vs.
one customer at a time
•
Compare two alternatives in terms of real-time response and matching
size
– Alternative 1: Handling one customer at a time as soon as it arrives
• Smaller response time, may lead to smaller matching size
– Alternative 2: Handling a group of customer arriving every T time instants
(e.g. 30 seconds)
• Larger response time, may lead to better matching
• Experimentally evaluate best T
Proposed Approach: A Greedy Heuristic-based
Algorithm
•
•
Consider 3 consumer requests at time t and 3 providers satisfying their ST constraints
where K=2:
Consumer
Candidate Propositions
C1
(C1, <P1,P2>) (C1, <P1,P3>) (C1, <P2,P3>)
C2
(C2, <P1,P2>) (C2, <P1,P3>) (C2, <P2,P3>)
C3
(C3, <P1,P2>) (C3, <P1,P3>) (C3, <P2,P3>)
Find subset of candidate propositions that maximizes # of matches while satisfying
service time/waiting time constraints
– NP hard [GeoTruCrowd] (by reduction from Maximum 3-dimensional Matching problem)
– Brute Force approach: exponential in the number of candidate propositions
– Heuristics can be used to reduce computational cost
Proposed Heuristics (1/2)
• Least_Accepted_First: Prioritize producers with least number of completed
transactions so far
– for fairness among producers
• Least_Service_Time_First: Prioritize producers with less service time (i.e.
more available capacity)
– to maximize matching in future requests
• Least_Appearance_As_Candidate: Prioritize producers with least number of
occurrences in all candidate lists (route and service time dependent)
– favors producers newly entering the system
• Least_Traversed_First: Prioritize producers in trajectory-sparser areas (only
route dependent)
– analogous to least-location-entropy heuristic [GeoCrowd]) but with route vs.
grid cell location dependency (30m x 30m)
•
May also use second then third heuristics as tie-breakers.
Proposed Heuristics (2/2): Accounting for
daily rhythm of supply and demand
•
•
Given: supply rates over the day, population data and probabilities of trip start
times based on time of day (rush vs. non-rush hour)
Triangles: Producers, Squares: consumers
t=0 (rush)
t=1 (non-rush)
Smaller supply rate
P1 day
model:
t=2 (rush)
Larger supply rate
S
5
10
5
D
10
5
10
D/S
2
0.5
2
P1
P2
Smaller supply rate
C1
C2
Prioritize producers
with least D/S
Input:
Execution Trace (1/3)
Customer 1:
• Max time before
service = 20 mins
• Max detour = 20%
• No waiting time
Customer 2:
• Max time before
service = 20 mins
• Max detour = 20%
•no waiting time
Output:
C1
ttimeout = 1 min
K=1
Provider 1:
service time =
10min
C2
P1
Provider 2:
service time =
10min
P2
Assuming travelling to P1 requires extra 1 mile by both C1 and
C2 while P2 requires 2 miles
C1
Least_Accepted_First: (C1,P1) and (C2, P2)
1
1
2
GeoCrowd (ACM GIS 2012): (C1,P1) (C2,P1)
(NN: Minimizes travel cost of max flow)
(Least Entropy: enp1 = enp2 = 0.3 (tie))
1
P1
src
dest
1
2
P2
1
C2
1
Execution Trace (2/3)
Input:
Customer 1:
• Max time before
service = 20 mins
• Max detour = 20%
• No waiting time
Customer 2:
• Max time before
service = 20 mins
• Max detour = 20%
•no waiting time
C1
ttimeout = 1 min
K=1
Provider 1:
service time =
10min
C2
P1
P2
Provider 2:
service time =
10min
Assuming travelling to P1 requires extra 1 mile by both C1 and
C2 while P2 requires 2 miles
Output:
GeoTruCrowd (ACM GIS 2013): (C1,P1) (C2,P1)
C1
(C1,P1)
dist = 1
(C2,P2)
dist = 2
C2
(C2,P1)
dist = 1
(C2,P2)
dist = 2
Execution Trace (3/3)
Input:
Customer 1:
• Max time before
service = 20 mins
• Max detour = 20%
• No waiting time
Customer 2:
• Max time before
service = 20 mins
• Max detour = 20%
•no waiting time
Output:
ttimeout = 1 min
K=1
Provider 1:
service time =
10min
C1
C2
P1
P2
Provider 2:
service time =
10min
Assuming travelling to P1 requires extra 1 mile by both C1 and
C2 while P2 requires 2 miles
Approach
#matched
requests
#consumer
s served
#producers
assigned
Total travel
distance
GeoCrowd (ACM GIS 2012)
2
2
1
2
GeoTruCrowd (ACM GIS 2013)
2
2
1
2
Proposed Approach
2
2
2
3
Proposed Heuristics: Balancing Broker, Consumer
and Producer Requirements
Considering the order of applying the different heuristics:
• Approach 1:
–
–
•
First: Use broker heuristics
Tie-breaker: producer then consumer-friendly heuristics (e.g. favor triples of (detour,
waiting time, time before service) that dominate a larger number of triples)
Approach 2:
– First: use broker-friendly heuristics
– Tie-breaker: combination of producer and consumer preferences
• Let α: weight application places on consumer satisfaction, β: be weight
application places on provider satisfaction
• Assign each (consumer, producer) edge a weight equal to the amount of
contribution to both: e.g. α (change in avg. waiting time + change in avg. detour )
+ β (number of additional assigned producers) (normalized)
• Prioritize edges with higher weights
Bottleneck: Efficiently Finding Candidate
Propositions (1/3)
Step 1: Find all candidate
propositions for consumers of
events E
•
To find candidate propositions P from
satisfying constraints of consumer c:
For each producer pi in ProducersList
find shortest path between c and
pi (Dijkstra’s)
If pi satisfies max detour
constraint then check waiting
time constraints
Computational Refinement:
– One Dijkstra’s for every consumer
– May further reduce number of destination nodes (producers) considered in
Dijkstra’s through spatial indexing
– Considering providers reachable along a path vs. providers reachable only
from current location
Bottleneck: Efficiently Finding Candidate
Propositions (1/3)
500m
cur loc
dst
Max Detour
= 10%
(50m)
Bottleneck: Efficiently Finding Candidate
Propositions (2/3)
Brute
Force:
500m
cur loc
dst
Max Detour
= 10%
(50m)
Bottleneck: Efficiently Finding Candidate
Propositions (3/3)
Instead:
1) Spatially index
providers
2) buffer around
network edges
500m
cur loc
dst
Max Detour
= 10%
(50m)
Contributions
•
Formulated the problem of On-demand Service Propositions.
•
Proposed an agent-based simulation framework for modeling a complete
transaction per consumer.
•
Proposed novel heuristics for maximizing the number of matches while
achieving fairness between service providers and satisfying consumer
constraints
•
Evaluated the proposed approach using synthetic and real datasets?
Future work: accounting for producer ratings and each consumer’s
historical transactions (i.e. past choices, preferences), moving producers
Validation Methodology (1/2)
• Synthetic Data generation using traffic generation with real data
characteristics.
– Service Providers:
• 943 (Minneapolis, Saint Paul)
• 25 service types (shopping mall, bookstore, electronics, grocery, laundry, ATM,
library, movie rental. Post office, restaurants, etc)
• Estimated supply: Poisson (Exponential) distribution with different rates for rush vs.
non-rush hours
Validation Methodology (2/2)
– Demand:
• Generating GPS traces based on OD matrix (population-based) in the twincities
• Modeling speed changes, and stops
• Not modeled: edge capacities and congestion
• Evaluation on real datasets (e.g. taxi trajectories) (sparse)
Sharing Economy Workshop at U of M
May 16–17, 2016
Commons Hotel, Minneapolis MN
A two-day symposium brought together leaders from academia, industry, nonprofits, and
government to shed light on the emerging area of the sharing economy and stimulate
interdisciplinary research and collaboration
Agenda:
Session I: Labor in the Sharing Economy
• An Analysis of the Labor Market for Uber’s Drivers in the United States
Jonathan Hall, Head of Economic Research, Policy and Legal, Uber
• Can You Gig It? An Empirical Examination of the Gig-Economy and Entrepreneurship
Brad Greenwood, Assistant Professor, Management Information Systems,Temple University
• Labor Welfare in the Sharing Economy
Crystal Kong, Assistant Professor, Department of Industrial & Systems Engineering, University
of Minnesota
Session II: Shared Mobility
• Cloud Commuting and Mobility-as-a-Service (MaaS) Transport
David Levinson, Professor, Department of Civil, Environmental, and Geo- Engineering,
University of Minnesota
•
•
•
Service Region Design for Urban Electric Vehicle Sharing Systems
Ho-Yin Mak, Associate Professor, Management Science, Saïd Business School, University
of Oxford
Peer-to-Peer Carsharing Market Analysis and Potential Growth
Robert Hampshire, Assistant Research Professor, Human Factors Group, University of
Michigan Transportation Research Institute
How Should Planners Prepare for Autonomous Cars?
David King, Assistant Professor, Urban Planning, Graduate School of Architecture,
Planning and Preservation, Columbia University
Session III: Ownership and Consumption in the Sharing Economy
• Peer-to-Peer Product Sharing: Implications for Ownership, Usage, and Social Welfare
Saif Benjaafar, Distinguished McKnight University Professor, Department of Industrial &
Systems Engineering, University of Minnesota, and Director, Initiative on the Sharing
Economy
• Owning, Using, and Renting: Some Simple Economics of the “Sharing Economy”
John Horton, Assistant Professor of Information, Operations and Management Sciences,
New York University
• Incentives and Equilibria for a Heterogeneous Population Interacting in the Sharing
Economy
Harald Bernhard, Ph.D. Candidate, Singapore University of Technology and Design
Session IV: On-Demand Platforms and Social Media
• On-Demand Service Platforms
Terry Taylor, Milton W. Terrill Chair in Business Administration and Associate Professor,
Haas Operations and Information Technology Management Group,University of California,
Berkeley
• Leveraging Socially Networked Mobile ICT Platforms for the Last Mile Delivery Problem
Tim Smith, Director, NorthStar Initiative for Sustainable Enterprise, Institute on the
Environment, University of Minnesota
• Repeated Interactions vs. Social Ties: Quantifying the Economic Value of Trust,
Forgiveness, and Reputation Using a Field Experiment
Ravi Bapna, Curtis L. Carlson Chair, Business Analytics and Information Systems, School
of Management, University of Minnesota
• Dynamic Type Matching
Ming Hu, Associate Professor, Operations Management, Rotman School of Management,
University of Toronto
Thank you.