| In this dissertation we investigate network flow problems with nonlinear are cost functions. The first group of problems consists of concave piecewise linear network flow, fixed charge network flow, and dynamic pricing problems that arise in the areas of supply chain management and logistics. Based on the MIP formulation, we construct bilinear reduction problems, in which the global solution of the latter is a solution of the initial formulation. To solve the reduction problem, we propose some heuristic algorithms. In the experiments, we compare the solution provided by our algorithm with an exact solution as well as a solution provided by other heuristic algorithms in the literature. Numerical experiments on randomly generated instances confirm the quality of the algorithms.; The second group of problems is related to the dynamic traffic assignment problem. In particular, we consider a periodic discrete time dynamic traffic assignment problem (DTDTA), in which the travel time is a function of the number of cars on the road, and the planning horizon is circular. The mathematical formulation belongs to the class of nonlinear mixed integer problems. To obtain an appropriate solution to the problem, we construct a linear mixed integer problem for providing an upper bound and discuss an approximation scheme based on the bounding problem. However, the bounding problem involves binary variables, and when the problem is large, it is hard to solve. To overcome these difficulties, we propose a heuristic algorithm based on a bilinear relaxation of the problem. Using an approximate solution, in the dissertation we develop a toll pricing framework for the dynamic case. In particular, based on a feasible vector of DTDTA we describe a set of valid tolls and discuss several toll pricing problems. By constructing an appropriate time-expanded network, one may consider a similar toll pricing framework for other solutions obtained, for example, from a simulation. |
