Introduction

Problem Statement

    Suppose members of a family who stay in different parts of country wish to meet up in Seattle. They all will arrive same day and leave on the same day. There are many flights from all locations to Seattle and Seattle to respective locations. We have to give them a flight plan based on cost, waiting time and travel time. Of course, all over cost must be low and we must consider any member shouldn’t waste much time on travel and wait.

Solution

    We have to write a cost function which will consider below factors and gives us cost of a solution:

1. Cost of flight
2. Waiting time can be considered as cost of 0.5$ per minute (one can change it based on priorities)
3. Each minute in air can be considered as cost of 1$ per minute (one can change it based on priorities)

Then we can use this cost function to calculate cost of a plan. There are many ways to create a solution one is just create all combinations of flights, calculate cost and find best solution among them. Other way is Hill Climbing approach which is optimized one. In this article, we will go with Hill Climbing approach only.

Hill Climbing

    Suppose you are dropped at random location on a landscape. You have to look for lowest point to find water, to do that you will look at each direction and follow where landscape slopes down. Once you reach lowest point each side you can see landscape slopes up.

Implementation

    We have data of supernatural TV series cast for family in file Family.txt. Below family members and their respective cities are comma separated.

John,Boston

Mary,San Francisco

Dean,Los Angeles

Sam,Chicago

Bobby,Honolulu

So we will have sample data of flights in file Flights.txt. Below Flight’s Origin, Destination, Departure, Arrival and Cost is comma separated respectively.

Boston,Seattle,08:10,09:00,120

Boston,Seattle,10:00,11:30,140

San Francisco,Seattle,08:30,10:00,110

San Francisco,Seattle,09:30,10:30,130

San Francisco,Seattle,10:30,11:30,100

Los Angeles,Seattle,07:30,9:00,150

Los Angeles,Seattle,08:00,13:00,140

Chicago,Seattle,07:30,9:00,110

Chicago,Seattle,08:30,9:30,120

Chicago,Seattle,09:00,10:30,150

Honolulu,Seattle,07:30,9:00,100

Honolulu,Seattle,10:00,11:30,120

Seattle,Boston,20:00,21:00,130

Seattle,Boston,20:30,21:30,170

Seattle,San Francisco,19:00,21:00,150

Seattle,San Francisco,19:30,21:00,140

Seattle,Los Angeles,19:00,20:00,160

Seattle,Los Angeles,20:00,21:30,110

Seattle,Chicago,18:30,20:30,130

Seattle,Chicago,19:30,21:00,120

Seattle,Chicago,20:00,22:00,150

Seattle,Honolulu,20:30,21:30,140

Seattle,Honolulu,21:00,22:00,110

We will generalize our implementation so in case of any change in family/flight data our algorithm will still work. For solution we will use array of double length of family members. If there are two family member solution will be like [1,0,2,1]. First two elements of array belong to 1st family member’s flight(upbound and return), next two elements of array belong 2nd person’s flight(upbound and return). Here first element is 1 means 1st family member takes 2nd flight to reach Seattle and second element is 0 which means same person returns by 1st flight. Third element is 2 means 2nd person takes 3rd flight to reach Seattle and returns by 2nd flight. we will consider 0 means 1st person/flight.

Now let’s create a python class groupTravel and write it’s constructor:

class groupTravel:

    def __init__(self, people, flights, dest):
        self.familyMembers = []
        self.flights = {}
        self.destination = dest
        #Dumping family data in dictionary
        with open(people) as file:
            for line in file:
                person,city = line.strip().split(',')
                self.familyMembers.append([person,city])
        #Dumping flights data in dictionary
        with open(flights) as file:
            for line in file:
                source,destination,departure,arrival,price = line.strip().split(',')
                self.flights.setdefault((source,destination), [])
                #Key is (origin, destination) and value is (departure, arrival, price) of flight
                self.flights[(source,destination)].append((departure,arrival,int(price)))

Above code shows how we can initialize family and flight data in objects. Family data we append in array and flight data in dictionary where key is tuple of source, destination and value is array of departure, arrival, price.

Now we will write method to calculate minutes from time format of HH:MM

#Converts HH:MM into minutes
def getMinutes(self, time):
    hours = time.strip().split(':')
    return int(hours[0])*60 + int(hours[1])

And we have to create a method to print our solution

#Printing solution
def printSolution(self, solution, cost):
    i = 0
    print('Trip plan:')
    for person, city in self.familyMembers:
        print(person, ':')
        print('    ', 'from:', city, self.flights[(city, self.destination)][solution[i]][0], 'To:', self.destination, self.flights[(city, self.destination)][solution[i]][1])
        i = i + 1   #For return flight
        print('    ', 'from:', self.destination, self.flights[(self.destination, city)][solution[i]][0], 'To:', city, self.flights[(self.destination, city)][solution[i]][1])
        i = i + 1
    print('Total cost:', cost)

Now we are all set with basic setup and we have to write cost function which calculates cost of each solution.

#Calculates total cost of a solution
def calculateCost(self, solution):
    totalCost = 0
    lastArrivalAtDestination = 0
    firstDepartureFromDestination = 24*60
        
    i = 0
    for person, city in self.familyMembers:
        outboundFlight = self.flights[(city,self.destination)][solution[i]]
        returnFlight = self.flights[(self.destination, city)][solution[i+1]]
        #Time taken in going and returning
        minutesOutbound  = self.getMinutes(outboundFlight[1]) - self.getMinutes(outboundFlight[0])
        minutesReturn  = self.getMinutes(returnFlight[1]) - self.getMinutes(returnFlight[0])

        #Outbound and return flight cost
        totalCost += outboundFlight[2];
        totalCost += returnFlight[2];
        #Hour cost is 1$/hour
        totalCost += minutesOutbound * 1;
        totalCost += minutesReturn * 1;

        #Setting arrival time of person reaches last
        if(lastArrivalAtDestination < self.getMinutes(outboundFlight[1])):
            lastArrivalAtDestination = self.getMinutes(outboundFlight[1])
        #Setting departure time of person leaves first
        if(firstDepartureFromDestination > self.getMinutes(returnFlight[0])):
            firstDepartureFromDestination = self.getMinutes(returnFlight[0])
        i = i + 2

    totalWait = 0
    i = 0
    for person, city in self.familyMembers:
        #Person's waiting time on airport
        outboundFlight = self.flights[(city,self.destination)][solution[i]]
        returnFlight = self.flights[(self.destination, city)][solution[i+1]]
        waitOutbound  = lastArrivalAtDestination - self.getMinutes(outboundFlight[1])
        waitReturn  = self.getMinutes(returnFlight[0]) - firstDepartureFromDestination

        totalWait += (waitOutbound + waitReturn)
        i = i + 2
    #Per hour cost of wait is 0.5$/hour
    totalCost += 0.5 * totalWait
    return totalCost

Go through line by line and understand cost function with the help of comments. We are summing up cost of each flight taken by each family member, adding waiting time and travel time cost. Once cost function is ready we are almost done, now we only have to write hill climb function.

#Hill Climbing Approach to find best solution
def hillClimbSolution(self, costFun):
    randomSolution = []
    #Generating a random solution
    for person, city in self.familyMembers:
        maxFlightsOutBound = len(self.flights[(city, self.destination)])
        maxFlightsReturn = len(self.flights[(self.destination, city)])
        randomSolution.append(random.randint(0, maxFlightsOutBound - 1))
        randomSolution.append(random.randint(0, maxFlightsReturn - 1))

    while 1:
        neighbours = []
        for i in range(len(randomSolution)):
            origin = None
            destination = None
            #Switching origin and destination based on index
            #(0,2,4,6,8) are upbound and (1,3,5,7,9) are return for each person
            if(i%2 == 0):
                origin = self.familyMembers[int(i/2)][1]
                destination = self.destination
            else:
                origin = self.destination
                destination = self.familyMembers[int(i/2)][1]

            #One way up
            if(randomSolution[i] < (len(self.flights[(origin, destination)]) - 1)):
                solution = randomSolution[0:i]+[randomSolution[i]+1]+randomSolution[i+1:]
                neighbours.append(solution)
            #One way down
            if(randomSolution[i] > 0):
                solution = randomSolution[0:i]+[randomSolution[i]-1]+randomSolution[i+1:]
                neighbours.append(solution)
        #Current solution cost
        currentSolution = costFun(randomSolution)
        bestSolution = currentSolution
        print('Current cost:', currentSolution)
        for solution in neighbours:
            cost = costFun(solution)
            #If neighbour is best solution
            if cost < bestSolution:
                bestSolution = cost
                randomSolution = solution

        #If no improvement in neighbours then we have reached bottom of hill
        if(currentSolution == bestSolution):
            break;

    return randomSolution, bestSolution

Hill climbing approach as you can see above, it creates a random solution and find all it’s neighbors. Then algorithm will see if any neighbor is better solution. We will keep doing this until we find a solution where no neighbor is better than it. Now let's run the code using:

grp = groupTravel('Data\\Family.txt', 'Data\\Flights.txt', "Seattle")
sol, cost = grp.hillClimbSolution(grp.calculateCost)
grp.printSolution(sol, cost)

Output:

Current cost: 2680.0

Current cost: 2375.0

Current cost: 2285.0

Current cost: 2210.0

Current cost: 2160.0

Trip plan:

John :

     from: Boston 08:10 To: Seattle 09:00

     from: Seattle 20:00 To: Boston 21:00

Mary :

     from: San Francisco 08:30 To: Seattle 10:00

     from: Seattle 19:30 To: San Francisco 21:00

Dean :

     from: Los Angeles 07:30 To: Seattle 9:00

     from: Seattle 20:00 To: Los Angeles 21:30

Sam :

     from: Chicago 08:30 To: Seattle 9:30

     from: Seattle 19:30 To: Chicago 21:00

Bobby :

     from: Honolulu 07:30 To: Seattle 9:00

     from: Seattle 21:00 To: Honolulu 22:00

Total cost: 2160.0

Conclusion

    You can see in output, current cost is getting reduced in each iteration and once we reach at lowest cost we print the solution. Hill climbing approach will give minimum in its domain, not the best solution among all possible solutions and each time you run the code you will see different solution but this method is better than brute force in terms of complexity.