Multi-day, multi-person, and multi-modal trip planning system
A multi-day and multi-person trip planning system comprises a planning graph of nodes interconnected by transit arcs which both have associated time-variable costs and time. A user specifies user objectives within trip destinations and customizes a plurality of user preferences for a multi-day, multi-person, multi-modal trip. An optimizer compiles a plurality of permutations of visiting plans within the planning graph which satisfy the specified user objectives including routing to a plurality of trip destinations. The optimizer compares the permutations using mixed integer programming or constraint programming to identify at least one optimized visiting plan having a lowest aggregate associated cost or shortest travel time that also satisfies a plurality of constraints determined by the customizable user preferences or environment condition. Then the user interface presents at least one optimized visiting plan to a user or route related coupons.
1. A multi-modal trip planning system, comprising:
a planning graph representing a plurality of nodes interconnected by a plurality of transit arcs, wherein the nodes include waypoints and trip destinations, wherein the transit arcs include alternate transportation modes, wherein the nodes and arcs have associated time-variable costs;
a user interface configured to specify a plurality of user objectives within the trip destinations and to customize a plurality of user preferences for a multi-modal trip, wherein the user objectives include a trip starting location, a trip ending location, and an attraction to be visited between the starting and ending locations, wherein the attraction to be visited is included in the nodes and has an associated constraint for optimization;
an optimizer coupled to the planning graph and the user interface configured to 1) modify the planning graph according to the user objectives and the customized user preferences, 2) compile a plurality of permutations of visiting plans within the modified planning graph which satisfy the specified user objectives including routing to a plurality of trip destinations including the attraction to be visited, and 3) comparing the permutations using an optimization programming to identify at least one optimized visiting plan having a lowest aggregate associated cost that also satisfies a plurality of constraints determined by the customizable user preferences and including the constraint associated with the attraction to be visited;
wherein the user interface presents at least one optimized visiting plan to a user.
2. The planning system of claim 1 wherein the optimization programming is comprised of mixed integer programming.
3. The planning system of claim 1 wherein the optimization programming is comprised of constraint programming.
4. The planning system of claim 1 wherein the lowest aggregated associated cost is comprised of a shortest travel time.
5. The planning system of claim 1 wherein the trip destinations in the planning graph include lodging, services, recreation attractions, business sites, and places to visit.
6. The planning system of claim 1 wherein the optimizer modifies the planning graph by adjusting associated time variable costs of the nodes and arcs.
7. The planning system of claim 1 wherein the optimizer modifies the planning graph by culling nodes and arcs unrelated to the specified user objectives.
8. The planning system of claim 1 wherein the specified user objectives include a date range, and wherein the attraction to be visited is comprised of at least one specific recreational attraction as a trip destination.
9. The planning system of claim 1 wherein the specified user objectives include a date range, and wherein the attraction to be visited is comprised of at least one type of recreational attraction as a trip destination.
10. The planning system of claim 1 wherein the user preferences include mode of transportation, services to be used, travel time, number of companions, type of accommodations, and monetary spending.
11. The planning system of claim 1 wherein the user preferences include air quality index, weather conditions, and crowding.
12. The planning system of claim 1 wherein at least some of the user preferences have a default value unless customized by the user.
13. The planning system of claim 1 wherein the optimizer compares the visiting plans according to:
{
h
,
v
,
τ
}
*
=
Min
{
h
,
v
,
τ
}
{
∑
t
=
t
0
+
1
t
0
+
D
[
a
v
,
h
trip
(
t
,
τ
t
)
]
}
subject
to
{
∑
t
=
t
0
+
1
t
0
+
I
[
c
v
visit
(
t
)
+
c
v
,
h
trip
(
t
)
]
≤
C
0
,
trip
cost
constaint
AQI
v
visit
(
t
)
≥
AQI
v
0
,
AQI
constraint
a
i
visit
,
0
≤
a
v
visit
(
t
,
τ
t
,
i
)
≤
a
i
visit
,
1
,
visiting
time
constraint
a
wait
(
t
,
τ
t
)
≤
a
wait
,
0
,
waiting
time
constraint
τ
t
,
0
≥
τ
0
,
starting
time
constraint
τ
t
,
n
t
≤
τ
1
,
ending
time
constraint
τ
t
,
0
≤
τ
t
,
1
≤
τ
t
,
2
…
≤
τ
t
,
n
t
where
the location list is h={h 1 , h 2 , . . . , h J },
the visiting dates are t={t 0 +1, t 0 +2, . . . , t 1 +D},
the daily number of places visited are n={n t 0 +1 , n t 0 +2 , . . . , n t 0 +D },
the visiting routes are v={v t 0 +1 , v t 0 +2 , . . . , v t 0 +D }={v t 0 +1,1 , v t 0 +1,2 , . . . , v t 0 +D,nt 0 +D },
all possible visiting plans are V=Permutation (v)={v 1 , v 2 , . . . , v 1! },
the daily trip time is τ={τ t 0 +1 , τ t 0 +2 , τ t 0 +3 , . . . , τ t 0 +D },
the daily AQI for visiting route v is AQI v visit (t),
the daily trip distance for visiting route v and location h:
d
v
,
h
trip
(
t
)
=
d
h
,
v
t
,
1
trip
+
∑
i
=
1
n
t
-
1
d
v
t
,
i
,
v
t
,
i
+
1
trip
+
d
v
t
,
n
t
,
h
trip
,
the daily visiting cost for visiting route v is
c
v
visit
(
t
)
=
∑
i
=
1
n
t
c
v
t
,
i
visit
,
the daily trip cost for visiting route v and location h are
c
v
,
h
trip
(
t
)
=
c
h
,
v
t
,
1
trip
+
∑
i
=
1
n
t
-
1
c
v
t
,
i
,
v
t
,
i
+
1
trip
+
c
v
t
,
n
t
,
h
trip
,
the visiting time of ith attraction for visiting route v is a v visit (t,τ t ,i)=τ t,i −τ t,i-1 ,
the daily waiting time for visiting route v is
a
v
wait
(
t
,
τ
t
)
=
∑
i
=
1
n
t
-
1
a
v
t
,
i
wait
(
t
,
τ
t
,
i
)
,
the daily trip time for visiting route v and location h is
a
v
,
h
trip
(
t
,
τ
t
)
=
a
h
,
v
t
,
1
trip
(
t
,
τ
t
,
0
)
+
∑
i
=
1
n
t
-
1
a
v
t
,
i
,
v
t
,
i
+
1
trip
(
t
,
τ
t
,
i
)
+
a
v
t
,
n
t
,
h
trip
(
t
,
τ
t
,
n
t
)
and h∈h, v∈V.
14. The planning system of claim 1 wherein the associated time-variable costs include future costs forecasted for different transportation modes using historical and current cost information.
15. The planning system of claim 1 wherein the planning graph and optimizer are comprised of a controller network including cloud-based computing resources.
16. The planning system of claim 15 wherein the user interface includes a mobile electronic controller wirelessly coupled to the controller network.
17. A method of planning a multi-modal trip, comprising the steps of:
representing a planning graph as a plurality of nodes interconnected by a plurality of transit arcs, wherein the nodes include waypoints and trip destinations, wherein the transit arcs include alternate transportation modes, wherein the nodes and arcs have associated time-variable costs;
specifying a plurality of user objectives within the trip destinations, wherein the user objectives include a trip starting location, a trip ending location, and an attraction to be visited between the starting and ending locations, wherein the attraction to be visited is included in the nodes and has an associated constraint for optimization;
customizing a plurality of user preferences for a multi-modal trip;
modifying the planning graph according to the user objectives and the customized user preferences;
compiling a plurality of permutations of visiting plans within the modified planning graph which satisfy the specified user objectives including routing to a plurality of trip destinations including the attraction to be visited;
comparing the permutations using optimization programming to identify at least one optimized visiting plan having a lowest aggregate associated cost that also satisfies a plurality of constraints determined by the customizable user preferences and including the constraint associated with the attraction to be visited; and
presenting at least one optimized visiting plan to a user.
18. The method of claim 17 wherein the trip destinations in the planning graph include lodging, services, and recreation attractions, and wherein the specified user objectives include a date range, and wherein the attraction to be visited is comprised of at least one specific recreational attraction as a trip destination.
19. The method of claim 17 wherein the step of modifying the planning graph is comprised of adjusting associated time variable costs of the nodes and arcs.
20. The method of claim 17 wherein the step of modifying the planning graph is comprised of culling nodes and arcs unrelated to the specified user objectives.
21. The method of claim 17 wherein the user preferences include mode of transportation, services to be used, travel time, type of accommodations, and monetary spending.
22. The method of claim 17 wherein at least some of the user preferences have a default value unless customized by the user.
23. The method of claim 17 wherein the comparing step uses optimization programming to identify an optimized visiting plan according to:
{
h
,
v
,
τ
}
*
=
Min
{
h
,
v
,
τ
}
{
∑
t
=
t
0
+
1
t
0
+
D
[
a
v
,
h
trip
(
t
,
τ
t
)
]
}
subject
to
{
∑
t
=
t
0
+
1
t
0
+
I
[
c
v
visit
(
t
)
+
c
v
,
h
trip
(
t
)
]
≤
C
0
,
trip
cost
constaint
AQI
v
visit
(
t
)
≥
AQI
v
0
,
AQI
constraint
a
i
visit
,
0
≤
a
v
visit
(
t
,
τ
t
,
i
)
≤
a
i
visit
,
1
,
visiting
time
constraint
a
wait
(
t
,
τ
t
)
≤
a
wait
,
0
,
waiting
time
constraint
τ
t
,
0
≥
τ
0
,
starting
time
constraint
τ
t
,
n
t
≤
τ
1
,
ending
time
constraint
τ
t
,
0
≤
τ
t
,
1
≤
τ
t
,
2
…
≤
τ
t
,
n
t
where
the location list is h={h 1 , h 2 , . . . , h J },
the visiting dates are t={t 0 +1, t 0 +2, . . . , t 1 +D},
the daily number of places visited are n={n t 0 +1 , n t 0 +2 , . . . , n t 0 +D },
the visiting routes are v={v t 0 +1 , v t 0 +2 , . . . , v t 0 +D }={v t 0 +1,1 , v t 0 +1,2 , . . . , v t 0 +D,nt 0 +D },
all possible visiting plans are V=Permutation (v)={v 1 , v 2 , . . . , v 1! },
the daily trip time is τ={τ t 0 +1 , τ t 0 +2 , τ t 0 +3 , . . . , τ t 0 +D },
the daily AQI for visiting route v is AQI v visit (t),
the daily trip distance for visiting route v and location h:
d
v
,
h
trip
(
t
)
=
d
h
,
v
t
,
1
trip
+
∑
i
=
1
n
t
-
1
d
v
t
,
i
,
v
t
,
i
+
1
trip
+
d
v
t
,
n
t
,
h
trip
,
the daily visiting cost for visiting route v is
c
v
visit
(
t
)
=
∑
i
=
1
n
t
c
v
t
,
i
visit
,
the daily trip cost for visiting route v and location h are
c
v
,
h
trip
(
t
)
=
c
h
,
v
t
,
1
trip
+
∑
i
=
1
n
t
-
1
c
v
t
,
i
,
v
t
,
i
+
1
trip
+
c
v
t
,
n
t
,
h
trip
,
the visiting time of ith attraction for visiting route v is a v visit (t,τ t ,i)=τ t,i −τ t,i-1 ,
the daily waiting time for visiting route v is
a
v
wait
(
t
,
τ
t
)
=
∑
i
=
1
n
t
a
v
t
,
i
wait
(
t
,
τ
t
,
i
)
,
the daily trip time for visiting route v and location h is
a
v
,
h
trip
(
t
,
τ
t
)
=
a
h
,
v
t
,
1
trip
(
t
,
τ
t
,
0
)
+
∑
i
=
1
n
t
-
1
a
v
t
,
i
,
v
t
,
i
+
1
trip
(
t
,
τ
t
,
i
)
+
a
v
t
,
n
t
,
h
trip
(
t
,
τ
t
,
n
t
)
and h∈h, v∈V.