We consider two combinatorial optimization problems the pipeline transportation problem (PTD) and the problem of searching with different access costs (PBC). In PTD, we are given a directed graph G = (N,A) where each arc corresponds to a pipeline. We are also given a set of batches, each batch being initially located at an arc or node and having a destination node. A subset of these batches are considered as further batches. Our aim is to find a sequence of pipeline operations leading all non-further batches to their corresponding destination nodes. First, we show that PDT is NP-hard, even for the case where G is acyclic. Next, we present a polynomial algorithm called BPA. This algorithm solves PTDS, a variation of PTD, for general graphs. For acyclic graphs, BPA also minimizes a general cost function. For the case of makespan minimization for PTDS, we prove that there is no n1-e - approximate algorithm for any E]0, unless P = NP, where n is the instance size. The previous result also holds if G is both ayclic and planar. In PBC, we are given an ordered vector with n elements and the corresponding access costs. Our aim is to find a search strategy that minimizes either the average cost (PBPC). In both cases, the best known exact algorithm requires in O(n3) time and O(n2) space. For PBCM, we present the ratio algorithm, that requires O(n2) time and O(n3)space. This algorithm always obtains a search strategy with average cost at most 41n(n+1)/n, assuming the sum of all access costs to be 1. Furthermore, we introduce approximation algorithms for both PBCM and PBPC. Both of them give (2+E+0(1)) - approximate solutions, for any E}0, in O(n) time and space.