Еще одной головной болью должен был стать дефицит топлива. Поначалу паровозы использовали исключительно английский уголь, доставлявшийся морем в Одессу. Затем были сделаны пробные топки донецким антрацитом. Оказалось, что антрацита расходуется на треть менее, чем английского каменного угля, но, с другой стороны, колосники в паровозных топках скорее перегорали вследствие сильного жара от горения антрацита, а ремонт их обходился в три раза дороже первоначальной цены. Несмотря ни на что, употребление антрацита сулило несомненные выгоды при условии, если Одесская дорога будет соединена с Донецкими угольными копями.
Еще до того времени, когда Одесско-Балтская дорога была закончена постройкой, неугомонный П. Е. Коцебу задумал изменить ее первоначальное направление. Вместо Киева он предложил тянуть рельсы на Кременчуг и далее на Харьков; другую линию вести к австрийской границе до Новоселиц. Уязвимым местом его плана было то, что Киев оказывался вне связи с крупнейшим черноморским портом России. Помимо этого, соединение Одессы с обеими столицами отодвигалось на неопределенное время. Предложение Коцебу наделало много шума. Оно обсуждалось и в прессе, и в ученом мире, и в правительственных кругах.
2 и 7 декабря 1864 года состоялось специальное заседание статистического отдела Русского географического общества, где скрестили копья сторонники киевского и кременчугского направлений. Киевскую партию возглавляли M. H. Катков и И. С. Аксаков (не явившиеся на заседание); противную — П. Е. Коцебу и директор статистического отдела Министерства внутренних дел П. П. Семенов.
Приверженцы киевского направления оперировали геополитическими и стратегическими аргументами. Лишь В. П. Безобразов — известный экономист либерального направления — доказывал, что дорога через Киев облегчит сбыт на южной Украине изделий московских текстильных фабрик.
Одесский банкир Рафалович прочел доклад на французском языке. Он указал на исключительную важность кременчугского направления для расширения российского экспорта через Одессу. Ни в Подольской, ни в Киевской губерниях производство товарной пшеницы не могло быть увеличено, тогда как посевные площади Харьковской и Екатеринославской губерний постоянно росли. Далее трехсотверстного расстояния вывоз хлеба он вообще считал нецелесообразным ввиду высокой стоимости провоза.
Большинство участников дискуссии высказались в пользу киевского направления. Но император решил иначе: 28 декабря 1864 года состоялось высочайшее повеление, которым предложение П. Е. Коцебу о направлении дороги от Балты на Харьков получило силу закона. 28 марта 1865 года были утверждены и основные условия контракта. Его удостоился проверенный в деле контрагент казны — барон К. К. Унгерн-Штернберг. Для производства строительных работ в его распоряжение назначались две бригады штрафных солдат общей численностью 9 тыс. человек.
Дорога должна была иметь протяженность 234 версты, сметная стоимость ее составляла 45 тыс. руб. на версту, а всего 10,5 млн. Предварительные изыскания были сделаны подрядчиком, он же выбрал и основное направление пути. Условиями контракта допускалось и отклонение от избранного направления, но не свыше 5 верст в сторону. За строительством наблюдал инспектор от Министерства путей сообщения; в министерство представлялись и все технические отчеты по работам. Подрядчик обязался не только построить магистраль со всей положенной инфраструктурой, но еще и снабдить ее подвижным составом. Он должен был поставить 9 паровозов весом до 28 т, 25 — до 35 т; вагонов пассажирских — 90, товарных — 560.
Контроль за расходованием казенных денежных сумм осуществлял бессарабский и новороссийский генерал-губернатор. Вся денежная и материальная отчетность в установленные сроки представлялась государственному контролю.
Барона К. К. Унгерн-Штернберга, уроженца острова Эзеля, одесские острословы прозвали «Эзелем с острова Унгерна». Над ним посмеивались, вспоминал К. А. Скальковский, но уважали — «…ослом барон не был — напротив, это был хотя и чудаковатый, но бойкий и даже остроумный человек… Женщин барон не выносил, и если кто из приближенных к нему людей задумывал жениться, барон без церемоний увольнял его от службы. Барон вообще отличался странностями. Он, например, прочел где-то, что смеяться полезно во время еды, ибо это приводит в движение желудок и селезенку. И вот барон во время завтрака и обеда рассказывал… без конца анекдоты, вовсе не смешные, но от которых сам добросовестно покатывался от смеха»11.