Групповые путешествия

Планирование путешествия группы людей (в данном примере семейства Глассов), которые, отправляясь из разных мест, должны прибыть в одно и то же место, всегда вызывало сложности и представляет собой интересную оптимизационную задачу. Для начала создайте новый файл optimization.py и вставьте в него такой код: import time import random import math

people = [(‘Seymour’,’BOS’), (‘Franny’,’DAL’), (‘Zooey’,’CAK’), (‘Walt’,’MIA’), (‘Buddy’,’ORD’), (‘Les’,’OMA’)]

# Место назначения – аэропорт Ла Гардиа в Нью-Йорке destination=’LGA’

Члены семьи живут в разных концах страны и хотят встретиться в Нью- Йорке. Все они должны вылететь в один день и в один день улететь и при этом в целях экономии хотели бы уехать из аэропорта и приехать в него на одной арендованной машине. Ежедневно в Нью-Йорк из мест проживания любого члена семьи отправляются десятки рейсов, все в разное время. Цена билета и время в пути для каждого рейса разные. Пример файла с данными о рейсах можно скачать со страницы http:// kiwitobes.com/optimize/schedule.txt.

Для каждого рейса в файле через запятую указаны аэропорт отправления, аэропорт назначения, время отправления, время прибытия и цена билета:

LGA,MIA,20:27,23:42,169 MIA,LGA,19:53,22:21,173 LGA,B0S,6:39,8:09,86

BOS,LGA,6:17,8:26,89 LGA,BOS,8:23,10:28,149

Загрузим эти данные в словарь, для которого ключом будет аэропорт отправления и аэропорт назначения, а значением – список, содержащий детальную информацию о рейсах. Добавьте следующий код в файл optimization.py:

flights={} #

for line in file(‘schedule.txt’): origin,dest,depart,arrive,price=line.strip( ).split(‘,’) flights.setdefault((origin,dest),[])

# Добавить информацию о возможном рейсе в список flights[(origin,dest)].append((depart,arrive,int(price)))

Сейчас будет полезно написать служебную функцию getminutes, которая вычисляет смещение данного момента времени от начала суток в минутах. Так нам будет удобнее вычислять время в пути и время ожидания. Добавьте эту функцию в файл optimization.py:

def getminutes(t): x=time.strptime(t,’%H:%M’) return x[3]*60+x[4]

Задача состоит в том, чтобы решить, каким рейсом должен лететь каждый член семьи. Разумеется, следует минимизировать общую стоимость, но есть и много других факторов, которые следует учитывать при поиске оптимального решения, например общее время ожидания в аэропорту или общее время в пути. Эти факторы мы подробнее обсудим чуть позже.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100