The paper is devoted to the problem of trip demand estimation in a road network. Commonly, when solving trip demand estimation problem researchers suppose the presence of so-called a prior origin-destination matrix. Unlike such an approach we assume that the only input data for trip demand estimation problem is traffic load on arcs. Thus, in this paper we intend to avoid using a prior origin-destination matrix for trip demand estimation and show that in such a case one is faced with the problem of combinatorial optimization. Computational complexity of appeared problem is discussed. Heuristic procedure for solving the problem is proposed and it is applied to the test example.