Пролог
Периодически сталкиваюсь со сложностью выбора билетов на региональные автобусные рейсы. Прямых рейсов нет, перевозчиков несколько, стоимость разная, время прибытия тоже разное. Порой ручной выбор двух подходящих билетов затягивается на несколько часов.
Я решил положить этому конец и распетлять задачу при помощи ЭВМ.
Постановка задачи
Надо доехать из города A в город C. При этом надо совершить пересадку в городе B. На сайтах есть множество билетов в направлении A->B и B->C. Надо выбрать два билета так чтобы:
1--минимальное время пересадки
2--минимизировать стоимость поездки
3--минимизировать общее время в пути
Надо написать программу. Буквально загружаешь все доступные в продаже билеты, запускаешь программу и получаешь целеуказание на самый оптимальный комплект билетов.
Терминология
Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
Название алгоритма |
Название алгоритма |
AVERAGE Performance |
insertion sort |
Сортировка вставками |
¼ n 2 |
bubble sort |
Сортировка пузырьком |
½ n 2 |
mergesort |
Сортировка слиянием |
n log2 n |
распарсить - произвести синтаксический разбор строки. То есть из строки распознать структуру данных и заполнить её бинарное представление в компьютерной программе.
Теоретическая часть
Есть два множества
1--множество возможных рейсов A->B. Пусть будет D вариантов.
2--множество возможных рейсов B->C. Пусть будет E вариантов.
Фаза 1 Сколько способов выбрать два билета?
Сколько способов выбрать два билета? Сначала выбираем первый билет, потом второй. По правилу произведения получается всего F=D*E возможных комплектов.
Фаза 2 Удалить пересекающиеся билеты
Из множества пар билетов надо удалить те, которые пересекаются, как временные интервалы. Очевидно, что так мы не доберёмся до города C.
Фаза 3 Вычислить метрики
Для каждой пары вычислим время ожидания и для каждой пары вычислить общую стоимость поездки. Для каждой пары вычислить полное время поездки.
Фаза 4 Определить функцию оптимальности
Определить функцию оптимальности. Скорее всего это будет функция от стоимости, времени ожидания и общего времени поездки. Скорее всего будут какие-то коэффициенты определяющие приоритетность того или иного критерия оптимальности.
В самом простом случае критерий оптимальности может быть такой:
1—Сначала сортируем по цене. Приоритет дешевым билетам.
2—Затем сортирует по длительности пересадки. При одинаковой цене предпочтение отдаем тому набору билетов, где пересадка короче.
Вот и получается, что надо последовательно сделать две сортировки: по цене и по длительности пересадки ожидания.
Фаза 5 Стабильная сортировка и выбор
Отсортировать по функции оптимальности и выбрать первый элемент в массиве. Стабильная сортировка нужна, чтобы вторая сортировка не слишком уж сильно поломала первую сортировку.
Практическая часть
Вот нам дали *.csv файл со списком возможных рейсов.
Stage Number, Departure Time, Departure date, Arrival time, Arrival date, from, to, cost, seller
1, 03:00 , 14.6 , 4:30 , 14.6, San-Komarik, Grabenberg, 1450,blablacar
1, 18:00 , 14.6 , 20:20 , 14.6 , San-Komarik, Grabenberg, 780, blablacar
1, 11:10 , 14.6 , 13:30 , 14.6 , San-Komarik, Grabenberg, 780, blablacar
2, 21:00 , 14.6, 5:55 , 15.6 , Grabenberg, Los-Paganos, 3210, blablacar
2, 21:00 , 14.6, 5:55 , 15.6 , Grabenberg, Los-Paganos, 3636, unitiki
2, 20:30 , 14.6, 5:20 , 15.6 , Grabenberg , Los-Paganos, 3273, unitikiПрежде всего надо его распарсить и посчитать сколько всего рейсов.
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
| Sta | cost | dep | Arvl | dep | Arvl | Duration | seller |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
| 1 | 1450 | San-Komarik | Grabenberg | 3:00:00,14Jun | 4:30:30,14Jun | 1.51 | blablacar |
| 1 | 780 | San-Komarik | Grabenberg | 18:00:00,14Jun | 20:20:20,14Jun | 2.34 | blablacar |
| 1 | 780 | San-Komarik | Grabenberg | 11:10:10,14Jun | 13:30:30,14Jun | 2.34 | blablacar |
| 2 | 3210 | Grabenberg | Los-Paganos | 21:00:00,14Jun | 5:55:55,15Jun | 8.93 | blablacar |
| 2 | 3636 | Grabenberg | Los-Paganos | 21:00:00,14Jun | 5:55:55,15Jun | 8.93 | unitiki |
| 2 | 3273 | Grabenberg | Los-Paganos | 20:30:30,14Jun | 5:20:20,15Jun | 8.83 | unitiki |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+На втором этапе следует выделить массив рейсов первой поездки и второй поездки
0.413,74 I,[TicketSetOpt] Round:1
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
| Sta | cost | dep | Arvl | dep | Arvl | Duration | seller |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
| 1 | 1450 | San-Komarik | Grabenberg | 3:00:00,14Jun | 4:30:30,14Jun | 1.51 | blablacar |
| 1 | 780 | San-Komarik | Grabenberg | 18:00:00,14Jun | 20:20:20,14Jun | 2.34 | blablacar |
| 1 | 780 | San-Komarik | Grabenberg | 11:10:10,14Jun | 13:30:30,14Jun | 2.34 | blablacar |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
0.456,75 I,[TicketSetOpt] Round:2
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
| Sta | cost | dep | Arvl | dep | Arvl | Duration | seller |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
| 2 | 3210 | Grabenberg | Los-Paganos | 21:00:00,14Jun | 5:55:55,15Jun | 8.93 | blablacar |
| 2 | 3636 | Grabenberg | Los-Paganos | 21:00:00,14Jun | 5:55:55,15Jun | 8.93 | unitiki |
| 2 | 3273 | Grabenberg | Los-Paganos | 20:30:30,14Jun | 5:20:20,15Jun | 8.83 | unitiki |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+Программа строит массив всех возможных пар билетов
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+
| N | depTime | depTown | depMidTime | depMidTown | ArvlTime | ArvlTown | waitH | costR |
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+
| 0 | 3:00:00,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 16.49 | 4660 |
| 1 | 3:00:00,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 16.49 | 5086 |
| 2 | 3:00:00,14Jun | San-Komarik | 20:30:30,14Jun | Grabenberg | 5:20:20,15Jun | Los-Paganos | 16.00 | 4723 |
| 3 | 18:00:00,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 0.66 | 3990 |
| 4 | 18:00:00,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 0.66 | 4416 |
| 5 | 18:00:00,14Jun | San-Komarik | 20:30:30,14Jun | Grabenberg | 5:20:20,15Jun | Los-Paganos | 0.17 | 4053 |
| 6 | 11:10:10,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 7.49 | 3990 |
| 7 | 11:10:10,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 7.49 | 4416 |
| 8 | 11:10:10,14Jun | San-Komarik | 20:30:30,14Jun | Grabenberg | 5:20:20,15Jun | Los-Paganos | 7.00 | 4053 |
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+Среди всех рейсов надо удалить те, которые пересекаются по времени. Затем надо отсортировать по цене и отсортировать по времени ожидания пересадки. Важно использовать именно стабильную сортировку.
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+
| N | depTime | depTown | depMidTime | depMidTown | ArvlTime | ArvlTown | waitH | costR |
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+
| 0 | 18:00:00,14Jun | San-Komarik | 20:30:30,14Jun | Grabenberg | 5:20:20,15Jun | Los-Paganos | 0.17 | 4053 |
| 1 | 18:00:00,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 0.66 | 3990 |
| 2 | 18:00:00,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 0.66 | 4416 |
| 3 | 11:10:10,14Jun | San-Komarik | 20:30:30,14Jun | Grabenberg | 5:20:20,15Jun | Los-Paganos | 7.00 | 4053 |
| 4 | 11:10:10,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 7.49 | 3990 |
| 5 | 11:10:10,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 7.49 | 4416 |
| 6 | 3:00:00,14Jun | San-Komarik | 20:30:30,14Jun | Grabenberg | 5:20:20,15Jun | Los-Paganos | 16.00 | 4723 |
| 7 | 3:00:00,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 16.49 | 4660 |
| 8 | 3:00:00,14Jun | San-Komarik | 21:00:00,14Jun | Grabenberg | 5:55:55,15Jun | Los-Paganos | 16.49 | 5086 |
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+Первый элемент и будет самым оптимальным рейсом
0.797,91 W,[TicketSetOpt] Tickets:
0.799,92 I,[TicketSetOpt] phase:1,
0.802,93 I,[TicketSetOpt] Cost :780 RUR,
0.806,94 I,[TicketSetOpt] From :18:00:00,14Jun,San-Komarik
0.809,95 I,[TicketSetOpt] To :20:20:20,14Jun,Grabenberg
0.813,96 I,[TicketSetOpt] Shop :blablacar
0.816,97 I,[TicketSetOpt] phase:2,
0.819,98 I,[TicketSetOpt] Cost :3273 RUR,
0.822,99 I,[TicketSetOpt] From :20:30:30,14Jun,Grabenberg
0.826,100 I,[TicketSetOpt] To :5:20:20,15Jun,Los-Paganos
0.830,101 I,[TicketSetOpt] Shop :unitiki
0.833,102 I,[TicketSetOpt] total_cost:4053
0.836,103 I,[TicketSetOpt] waiting between routes:0.16944444 hЕсли вам хочется тоже воспользоваться этой простой утилитой или протестировать её, то бинарь можно скачать тут.
Итоги
Удалось написать консольную утилиту для выбора оптимального комплекта из двух билетов.
Ссылки
№ |
Название |
URL |
1 |
Algorithms and Data Structures Cheatsheet |
|
2 |
Дистрибутив утилиты ticket_set_opter |
https://github.com/aabzel/Artifacts/tree/main/ticket_set_opter |
Комментарии (21)
Radisto
09.06.2025 02:29Первый элемент и будет самым оптимальным рейсом
Лучше оставить разницу хотя бы в пять, а лучше 10 минут: если ваш автобус хоть немного опоздает (а это весьма вероятно), то можно только помахать ручкой следующему.
pavelsha
09.06.2025 02:29Я согласен с комментарием о временном окне на пересадку. Важно учитывать не только возможные опоздания, но и наличие альтернативных вариантов в случае задержки автобуса. А ещё размеры автостанции для пересадки тоже важны. Куда приходят рейсы, которые стыковало наше расписание? Может, это одна остановка или соседние «терминалы», а может, надо идти минимум 10 минут.
Нужно оценить, что делать, если рейс для пересадки отменён или по какой-то причине вы на него опоздали. Например, если следующий подходящий рейс будет только через 12 или 24 часа, стоит ли рисковать и экономить 15 минут?
randomsimplenumber
09.06.2025 02:29А есть ещё проходящие автобусы. Существуют города где >1 автостанция. Существуют, кроме автобусов, железные дороги. И воще самое интересное в этой задаче - парсить сайты разных перевозчиков.
Походу кто-то начал ходить по собеседованиям ;)
pavelsha
09.06.2025 02:29Походу кто-то начал ходить по собеседованиям ;)
Ездить же на автобусе, а не ходить
alexws54tk
Работа проделана интересная и, определённо, имеет полное право на жизнь.
Но, из всех предложенных алгоритмом тестовых вариантов лично я бы выбрал второй вариант, с «полу-часовой» пересадкой.
Подходящих нам рейсов из ГабенБурга в ЛосПаганос всего 2 — на 20:30 (основной) и 21:00 (добавочный). Есть шанс, что большинство пассажиров поедет на первом автобусе — на втором будет комфортнее.
Мы уже ехали 2 часа — надо размяться, сходить в туалет (а там зачастую очереди), перекусить (там тоже очереди) — поэтому пересадка длительностью 40 минут будет оптимальнее, чем пересадка в 10 минут.
В пути бывают разные непредвиденные ситуации, и автобус из СанКомарика элементарно может опоздать на рейс в 20:30 в ГабенБурге.
Прибытие в 5:20 нам не добавляет существенных преимуществ над прибытием в 5:55 — т.к. городской транспорт полноценно начинает ходить с 6 утра — те же самые 30 минут ожидания, что мы провели на пересадке. Либо вызывать такси.
Бонусом: поездка чуточку дешевле.