Есть прямые автобусы Одесса - Краснодар и Одесса - Сочи. Они идут через Новороссийск. Время в пути 18 часов. Не знаю, каково будет троим детям почти сутки в автобусе, но не уверен, что им понравится и значительно большее количество времени на поездах с двумя пересадками (и значительно дороже, кстати говоря) . По крайней мере, если поездка планируется до конца мая, до ввода нового ж. -д. расписания.
По ж. д. : харьковским поездом №60 доехать до Знаменки, там ночная пересадка на 18-й Киев - Анапа (с 1-16 до 2-52). Выйти в Ростове, через три часа пересесть на 404-й Нижний Новгород - Новороссийск. Итого полтора суток - выезд из Одессы в 18-12, прибытие в Новороссийск через две ночи в 5-35 утра. Из Одессы выезжать в нечётное число.
Давно (в советские времена) плавала на теплоходе Одесса - Сухум с заходом в большие порты, в том числе и в Новороссийск.
Узнайте, может и сейчас есть какой-то морской путь, хотя дешевым он не будет.