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:
- Cost of flight
- Waiting time can be considered as cost of 0.5$ per minute (one can change it based on priorities)
- 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.
Comments: