{"title":"Optimal Path Planning under Priori Information in Stochastic, Time-varying Networks","authors":"Siliang Wang, Minghui Wang, Jun Hu","country":null,"institution":"","volume":37,"journal":"International Journal of Computer and Information Engineering","pagesStart":69,"pagesEnd":73,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/177","abstract":"A novel path planning approach is presented to solve\r\noptimal path in stochastic, time-varying networks under priori traffic\r\ninformation. Most existing studies make use of dynamic programming\r\nto find optimal path. However, those methods are proved to\r\nbe unable to obtain global optimal value, moreover, how to design\r\nefficient algorithms is also another challenge.\r\nThis paper employs a decision theoretic framework for defining\r\noptimal path: for a given source S and destination D in urban transit\r\nnetwork, we seek an S - D path of lowest expected travel time\r\nwhere its link travel times are discrete random variables. To solve\r\ndeficiency caused by the methods of dynamic programming, such as\r\ncurse of dimensionality and violation of optimal principle, an integer\r\nprogramming model is built to realize assignment of discrete travel\r\ntime variables to arcs. Simultaneously, pruning techniques are also\r\napplied to reduce computation complexity in the algorithm. The final\r\nexperiments show the feasibility of the novel approach.","references":null,"publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 37, 2010"}