Optimizing Carpool Scheduling Algorithm through Partition Merging Yubin Duan, Turash Mosharraf, Jie Wu, and Huanyang Zheng Center for Networked Computing, Temple University, USA
C Find a Hamilton
B
tour shorter than
S
(1+ ")|SS’|
S'
Motivation A’
B 1
1 2
A/D
2
1 1
1 2
1 C
D - D’
C - C’
C’/D’
• Another user can re-carpool with drivers after previous user got off • A 4-people carpool D – A –A’ –B – B’ –C – C’ –D’ with ! = 2, " = 20% • The minimum number of carpools needed is 1
• Full permutation (PMA): O(n!) D - A - B - C - A’ -B' - C' - D'
• Each component is a local sequence of s and d. d always appears after corresponding s.
• Driver-alone insertion (PMAD): O(n2.5) A – B – B’ – A’ A – B – B’ – A’ seat +1
C – D – D’ – C’ C – D – D’ – C’
properly nested • Merge: Two components can be merged if all elements can be • General insertion (PMAG): O(n2.5) combined that satisfies capacity A – B – B’ – A’ A – B – B’ – A’ constraint ! and detour constraint ". seat +2 seat +2 C – D – D’ – C’ C – D – D’ – C’ • Construct a component matching properly nested graph,
merge A - A’
B - B’
D - D’
C - C’
D - A - A’ - D’
B - B’
• Real-world dataset: s and d are extracted from traces of NYC cabs
not properly nested
seat +1
D - A - A’ - B - B' - C - C' - D'
• vertex: component • edge: two mergeable components.
B’
1
B - B’
• Synthetic dataset: s and d locations are individual and range from 0-30 miles in 2-D space.
O(n2.5)
C - C’
• Maximum matching on the component graph to generate new graph • Repeat maximum matching on the new graph until convergence.
+1 +2 +1 S: A – B – B’ – A’ (a) S’ inserted to S
Uniform Distribution
5%
10%
Improvement
A
15%
d2 A’
20
80 60
20
80 60
20 10
50 40
20 100
40 60 80 Number of users
100
SPA PMAD PMAG PMA
30 20 10 0 20 60
40
SPA PMAD PMAG PMA
30
0 20
100
SPA PMAD PMAG PMA
40 60 80 Number of users
40
60
SPA PMAD PMAG PMA
40 60 80 Number of users
50
100
40
20
feasible area: d1+d2 = (1+α)|AA’|
40 60 80 Number of users
Norm Distribution 60
SPA PMAD PMAG PMA
40
20
• In Euclidean space, matching eligibility via geometry properties d1
60
20
+1 +2 +1 S’: C – D – D’ – C’ (b) S inserted to S’
80
Number of carpools
A
A - A’
• Simple merging
(SPA) 1:
Number of carpools
• NP-hard problem: a special case can be reduced to Hamilton tour
• Initialization, each component contains only one element
S’: C- D- D’- C’
Number of carpools
• Capacity constraint ), vehicle has capacity limitation, e.g. ! = 2
• E.g. S: A- B- B’- A’;
• Based on component merge
Number of carpools
• Detour constraint (, e.g. no more than " = 20% of the shortest path
Simulation Results
Number of carpools
• Target: minimizing carpools needed, each user has distinct src s and dest d
Merge Methods
A Greedy Solution
Number of carpools
Carpool scheduling problem
50 40
40 60 80 Number of users
100
SPA PMAD PMAG PMA
30 20 10 0 20
40 60 80 Number of users
• 1. F. Buchholz, “The carpool problem,” 1997.
100
