In [2]:
import time
import random
import math
people = [('Seymour','BOS'),
('Franny','DAL'),
('Zooey','CAK'),
('Walt','MIA'),
('Buddy','ORD'),
('Les','OMA')]
# LaGuardia airport in New York
destination='LGA'
"""Load this data into a dictionary with the origin and destination (dest) as the keys
and a list of potential flight details as the values."""
flights={}
#
for line in file('schedule.txt'):
origin,dest,depart,arrive,price=line.strip( ).split(',')
flights.setdefault((origin,dest),[])
# Add details to the list of possible flights
flights[(origin,dest)].append((depart,arrive,int(price)))
In [3]:
"""Calculates how many minutes into the day a given time is. This makes it easy to calculate
flight times and waiting times"""
def getminutes(t):
x=time.strptime(t,'%H:%M')
return x[3]*60+x[4]
In [4]:
"""Routine that prints all the flights that people decide to take in a nice table"""
def printschedule(r):
for d in range(len(r)/2):
name=people[d][0]
origin=people[d][1]
out=flights[(origin,destination)][r[d]]
ret=flights[(destination,origin)][r[d+1]]
print '%10s%10s %5s-%5s $%3s %5s-%5s $%3s' % (name,origin,
out[0],out[1],out[2],
ret[0],ret[1],ret[2])
This will print a line containing each person’s name and origin, as well as the depar- ture time, arrival time, and price for the outgoing and return flights
In [5]:
s=[1,4,3,2,7,3,6,3,2,4,5,3]
printschedule(s)
Observation: Even disregarding price, this schedule has some problems. In particular, since the family members are traveling to and from the airport together, everyone has to arrive at the airport at 6 a.m. for Les’s return flight, even though some of them don’t leave until nearly 4 p.m. To determine the best combination, the program needs a way of weighting the various properties of different schedules and deciding which is the best.
In [6]:
"""This function takes into account the total cost of the trip and the total time spent waiting at airports for the
various members of the family. It also adds a penalty of $50 if the car is returned at a later time of
the day than when it was rented.
"""
def schedulecost(sol):
totalprice=0
latestarrival=0
earliestdep=24*60
for d in range(len(sol)/2):
# Get the inbound and outbound flights
origin=people[d][1]
outbound=flights[(origin,destination)][int(sol[d])]
returnf=flights[(destination,origin)][int(sol[d+1])]
# Total price is the price of all outbound and return flights
totalprice+=outbound[2]
totalprice+=returnf[2]
# Track the latest arrival and earliest departure
if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])
# Every person must wait at the airport until the latest person arrives.
# They also must arrive at the same time and wait for their flights.
totalwait=0
for d in range(len(sol)/2):
origin=people[d][1]
outbound=flights[(origin,destination)][int(sol[d])]
returnf=flights[(destination,origin)][int(sol[d+1])]
totalwait+=latestarrival-getminutes(outbound[1])
totalwait+=getminutes(returnf[0])-earliestdep
# Does this solution require an extra day of car rental? That'll be $50!
if latestarrival>earliestdep: totalprice+=50
return totalprice+totalwait
In [7]:
#Print schedule cost
schedulecost(s)
Out[7]:
Observation: Now that the cost function has been created, it should be clear that the goal is to minimize cost by choosing the correct set of numbers.
In [8]:
"""The function takes a couple of parameters. Domain is a list of 2-tuples that specify the minimum and maximum values
for each variable. The length of the solution is the same as the length of this list. In the current example,
there are nine outbound flights and nine inbound flights for every person, so the domain in the list is (0,8)
repeated twice for each person.
The second parameter, costf, is the cost function, which in this example will be schedulecost. This is passed as
a parameter so that the function can be reused for other optimization problems. This function randomly generates
1,000 guesses and calls costf on them. It keeps track of the best guess (the one with the lowest cost) and returns it.
"""
def randomoptimize(domain,costf):
best=999999999
bestr=None
for i in range(1000):
# Create a random solution
r=[random.randint(domain[i][0],domain[i][1])
for i in range(len(domain))]
# Get the cost
cost=costf(r)
# Compare it to the best one so far
if cost<best:
best=cost
bestr=r
return r
In [10]:
#Let's try 1000 guesses. 1,000 guesses is a very small fraction of the total number of possibilities'
domain=[(0,8)]*(len(people)*2)
s=randomoptimize(domain,schedulecost)
schedulecost(s)
printschedule(s)
Observation: Due to the random element, your results will be different from the results here. The results shown are not great, as they have Zooey waiting at the airport for six hours until Walt arrives, but they could definitely be worse. Try running this function several times to see if the cost changes very much, or try increasing the loop size to 10,000 to see if you find better results that way.
In [ ]: