Research On The Inverse Dynamic Minimum Cost Path Problem Under L₁ Norm

In this paper, We study an inverse dynamic minimum cost path problem under L₁ norm which combined dynamic network combinatorial optimization with inverse optimization. The cost of traversing arc (i,j) is defined as the weighted sum of the minimum possible travel time d_ij^* and the excess travel time (over the minimum possible travel time) e_ij(t). The paper is organized as follows:(1) Presents two basic dynamic network flow models including discrete flow over time and continuous flow over time, and the concept of time-expanded graph which can transform every discrete flow over time problem into a static flow problem.(2) develops a pseudopolynomial-time algorithm to solve the minimum cost walk problem (for integer travel times) and extend the problem to the more realistic case.(3) discusses solving the inverse linear programming problem under the L₁ norm and clarifies the connection between the dual of the inverse problem and a relaxation of the original problem.(4) Gives the result and an algorithm of the inverse dynamic minimum cost path problem under L₁ norm by using time-expanded graph and the approach for solving the inverse linear programming problem under L₁ norm.