Trip Planning: hardest of the hard problem

A good trip requires a significant amount of time in planning and that can be incredibly frustrating for all of us. If it’s not a weekend trip, you may end up spending 20–25 days on an average on planning. And even if you have a plan in hand, you can't be sure if this is what you are looking for. Why? Can the current technology solve it?

To help you understand the problem better, let's begin with how I plan my holidays. I believe most of us do it the same way and face these questions:

• Where should I go?
• What would I do and what places should I visit?
• How much time should I spend at each of the places?
• Where should I go first and should I travel by train or by flight?
• Where would I stay?

All in all, it’s a good problem to solve. In this blog, I will focus on the multi-destination route planning problem which is just a part of the Trip Planning. Read it more on what goes under the hood at Tripigator.

Multi-Destination Route Planning

Finding an optimal route from place A to place B is a function of many things e.g. price, duration, departure time, mode of transport etc. And if there’s no direct route from place A to place B, many more criteria like transit timings, changing of transport at various places etc come in play which decide the optimality of the route. If there are more than one destinations to visit in a trip then what destination should be taken first, followed by another and so on; can alter the whole holiday experience. So finding the best holiday experience considering all these factors makes Trip Planning theoretically unsolvable due to computational challenges.

Why NP-hard and not NP (NP-complete) ?

A route planning problem to cover a set of destinations can be reduced to TSP (Travelling Salesman Problem) which makes it an NP-hard problem.

Let’s assume Trip Planning to be an NP-complete which means

Given a set of destinations and a plan, we can validate it to be the optimal plan (or not) in polynomial time

To assert this statement, let’s say you are given a set of destinations {A, B} and your starting point as S.

The plan is to go to A first, followed by B and then return back to S.

S -> A -> B -> S.

Let’s identify the trip_score to be ‘x’ where trip_score is a function of trip experience based on personal preferences and the cost of the trip and assume it to be the only criterion of an optimal plan.

Can we make a claim about the ranking of this trip without looking at the trip_score of S -> B-> A -> S ?

Now, add one more destination C in the set and let’s make a claim about the trip

S -> A -> B -> C-> S whose trip_score is ‘y’.

Can we claim the holiday experience of this trip to be the best unless we look at the trip_score of

S -> A -> C -> B -> S,

S -> B -> C -> A -> S,

S -> B -> A -> C -> S,

S -> C -> A -> B -> S,

S -> C -> B -> A -> S

In both the cases, the claim would not be valid unless we look at all the possible permutations. If we keep on increasing destinations, the number of possibilities will keep increasing which can be validated in O(n!) but a polynomial time, thereby invalidating it as an NP-complete problem.

If you are still not convinced or want to ask something specific write to piyush at tripigator dot com.