Ngày 6/12/1897, Hội đồng tối cao Đông Dương quyết định thông qua đề án tổng thể về đường sắt Đông Dương gồm:
– Tuyến đường sắt lớn từ Sài Gòn, băng qua Trung Kỳ, qua các tỉnh Quy Nhơn, Đà Nẵng, Huế đến Hà Nội nối tiếp với tuyến đường Hà Nội – Quảng Tây (Trung Quốc).
– Tuyến Hải Phòng – Hà Nội, chạy qua lưu vực sông Hồng đến Vân Nam.
– Tuyến Savannakhet (Lào) đến Quảng Trị.
– Tuyến Quy Nhơn – Kon Tum.
– Tuyến Sài Gòn – Phnom Penh.
Tổng chiều dài các tuyến khoảng 3.200km.
Sau phiên họp ngày 14/9/1898 Hội đồng tối cao Đông Dương nhất trí ưu tiên xây dựng trước các tuyến:
– Hải Phòng – Hà Nội – Lào Cai.
– Lào Cai – Vân Nam (Trung Quốc).
– Hà Nội – Nam Định – Vinh.
– Đà Nẵng – Huế – Quảng Trị.
– Sài Gòn – Khánh Hòa qua cao nguyên Langbiang (Đà Lạt).
– Mỹ Tho – Vĩnh Long – Cần Thơ.
Đề án này đã được Paul Doumer về nước trực tiếp trình Quốc hội Pháp và đã được thông qua vào ngày 25/12/1898. Trong các tuyến đường được phê duyệt, chỉ có tuyến Mỹ Tho – Vĩnh Long – Cần Thơ là không được phê duyệt xây dựng do sự khó khăn về địa lý của vùng Nam Bộ.
Kế hoạch của Toàn quyền Doumer nhanh chóng được tiến hành. Trước đó, năm 1896, Toàn quyền Đông Dương ký quyết định ban hành Nghị định số 1680 về việc phê duyệt dự án xây dựng cầu sắt qua sông Đuống, sông Cầu, sông Thương, sông Kỳ Cùng của Công ty Schneider et Vézin trên tuyến Hà Nội – biên giới Trung Quốc. Chi phí xây dựng các công trình hầm, cầu trên tuyến không nằm trong kính xây dựng đường. Việc hàng loạt những cây cầu sắt được xây dựng đã kết nối thông suốt con đường từ đồng bằng Bắc Bộ lên các tỉnh vùng núi phía Bắc.
Đến cuối năm 1898, Paul Doumer đã trình làng ý tưởng về sự cần thiết của một cây cầu sắt lớn bắt ngang sông Hồng. Ban đầu, nhiều người đã cho rằng đây là một ý tưởng điên rồ và không khả thi. Chưa từng có thứ gì lớn lao như vậy được xây dựng trên dòng sông này. Đã có không ít các chính khách mỉa mai rằng Paul Doumer và các cộng sự là “những gã theo chủ nghĩa đường sắt” vì những ý tưởng điên rồ của họ. Tuy nhiên, vượt qua những tranh cãi, công trình vẫn được thi công cùng các đoạn còn lại trên tuyến Hà Nội – Lạng Sơn.