# Comparing routing algorithms to find the most convenient strategy

Mertcan Coskun

2 years ago | 5 min read

Suppose you have a lot of free time in your hands and you want to fly to a lot of cities, but you are not sure which strategy to use to plan your trip. Should you buy the cheapest ticket at that day or wait a couple of days to find the lowest price? Can you complete your trip if you do so?

I will be exploring those ideas and writing the algorithms from scratch to showcase which strategies are the most suitable for our dream trip.

First things first;

• We want to visit each city,
• We want to minimize the cost,
• We have a time constraint,
• We always start the journey on the first day from a selected city,
• We can go back to a previously visited city in order to achieve the lowest total cost.

## What does the data look like?

Figure 1: Initial look at the data

The data includes all the possible combinations of flights for all possible days. Total days here can be changed, new cities can be added but the dataset used for this problem includes 6 cities and 40 days (at max).

## What are the strategies?

First, there is the standard strategy of choosing the cheapest flight on each day. If we are in Munich and the cheapest flight is to Stuttgart, we will choose to go to Stuttgart.

`def standard(days):    for i in range(1,days+1):        start_idx = df[df.From == to_city][i].idxmin()        cost.append(min(df[df.From == to_city][i]))        from_city = df.iloc[start_idx]['From']        to_city = df.iloc[start_idx]['To']        cities_visited.add(from_city)        cities_visited.add(to_city)        route.append(to_city)        if (cities_visited) == (cities):            total_cost.append(sum(cost))            return total_cost            break`

The Standard Strategy

But what if we are in Munich and the cheapest flight is to Stuttgart but tomorrow is even cheaper? This is called a price dip and it exists in real life ticket prices.

## The Price Dip strategy

Why does the price dip happen? Because airlines need to find the right balance between making sure every seat is filled and earning enough money to cover the operating costs.

For this reason, ticket prices will drop and rise very regularly, depending on lots of different things that are associated with flights such as business trips and real time bookings. The Price Dip strategy finds the price dip by comparing the next days’ prices for that day.

`def price_dip(days):    if (i < days - 1):        if (min(df[df.From == to_city][i]) > min(df[df.From == to_city][i+1])):            continue        start_idx = df[df.From == to_city][i].idxmin()        cost.append(min(df[df.From == to_city][i]))        from_city = df.iloc[start_idx]['From']        to_city = df.iloc[start_idx]['To']        cities_visited.add(from_city)        cities_visited.add(to_city)          route.append(to_city)        if (cities_visited) == (cities):            total_cost.append(sum(cost))            return total_cost`

The Price Dip Strategy

Is the Price Dip strategy better than the normal strategy? For that, we need to create a simulation where a random term is added to the original database. This way, the algorithm can be run 1000 times to find the list of total costs and a T-test can be applied to see if there is a difference between strategies.

Distributions of Standard and Price Dip strategies

The T-test shows that there is a significant difference between two strategies therefore the Price Dip strategy is considerably better. But is the problem solved now? Unfortunately no, because the Price Dip strategy skips a lot of days and needs a lot of them to conclude all cities.

## Modifying the Price Dip strategy

Source: Pexels

T test results show that the Price Dip strategy shows significant improvements over the standard strategy. But with a catch; the Price Dip strategy does not conclude most of the time. Meaning it can not reach every city in a given time. To combat this, I will try to overcome its problem by going to the last city when there is only one city left. Because most of the time the route is missing that one city for completion.

The Modified Price Dip Strategy

`#price dip, price dip as well for last citydef price_dip_all():    for i in range(1,days+1):        if len(cities_left) == 1:            if (min(df[df.From == to_city][i]) > min(df[df.From == to_city][i+1])):                continue            cost.append(df[(df.From == to_city) & (df.To == list(city_left)[0])][i].values[0])            from_city = df.iloc[start_idx]['From']            to_city = df.iloc[start_idx]['To']            cities_visited.add(from_city)            cities_visited.add(to_city)            route.append(list(cities_left)[0])            total_cost.append(sum(cost))            return total_cost            break`

Now let’s see how often strategies fail to go to every city, given the 6 given cities. Let’s also see if the improved Price Dip strategy achieves better success.

Completion Rate of strategies based on given days

In case of 25 days are given to travel to all 6 cities, the standard strategy fails 4 % of the time, Price Dip strategy fails 39 % of the time and improved Price Dip strategy fails 5 % of the time.

The improved Price Dip strategy (Price-Dip-All) has significantly high completion rate but t statistics show that it has similar cost, meaning price wise it did not show significant improvement compared to the normal Price Dip strategy.

## Conclusion

In this article, some ideas about how to plan your dream trip have been discussed. It turned out the standard strategy of buying cheapest ticket every day made you visit every city but at a high cost.

Price Dip strategy came in to significantly reduce the total cost, but it did not complete every city in given time. For 6 given cities and 20 days, the algorithm failed to visit all cities 39% of the time. The Price Dip strategy was altered and was modified to visit the last remaining city when there was one city left. The modified strategy had the best features of previous two, low cost and high completion ratio

Upvote

Created by

Mertcan Coskun

Post

Upvote

Downvote

Comment

Bookmark

Share

Related Articles