Trip Planning: hardest of the hard problem

Piyush Grover
Nov 23, 2015 · 3 min read

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

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

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.

Tripigator App

Insights into our products, technology and operations

Tripigator App

Insights into our products, technology and operations

Piyush Grover

Written by

Technology, Psychology & Spirituality and in no particular order. Knowledge democrat. Cofounder — Maasika.in, Researching innovations, IIT Kharagpur ’09

Tripigator App

Insights into our products, technology and operations