基于马尔可夫决策过程的出租车寻客路径优化

Route Optimization of Taxicab Based on Markov Decision Process

为提高出租车的长期收益,作者在路网网格化的基础上建立了基于马尔可夫决策过程的路径优化模型。将车辆当前所位于的网格位置定义为状态,将从当前网格选择某一相邻网格出发定义为动作,使用策略迭代法对问题进行求解,并采用高斯-赛德尔迭代进行加速。以深圳市典型工作日全天797辆出租车的GPS数据进行试算和仿真,计算速度是雅克比迭代的1.85倍。将该算法与随机游走和全局热点算法进行比较,结果表明,所提出模型的平均单位距离收益分别提高了22.1%和12.9%,载客里程占比分别提高了18.8%和10.4%,具有较好的优化效果。

A dynamic route optimization model based on Markov decision process is formulated after gridding of network.The state is defined by the grid location of vehicle while the action is defined by the selection of an adjacent grid from the current location.The problem is solved by the policy iteration,Gauss Seidel iteration is used for acceleration.The model is tested by taking the GPS data of 797 taxicabs in a typical working day in Shenzhen,and the speed is 1.85 times that of Jacobi iteration.The model is compared with two heuristic algorithms by simulation,showing that the average profit per unit distance of the optimal route strategy is 22.1% and 12.9% higher than that of random walk and global hotspot algorithm,while the proportion of passenger carrying distance is 18.8% and 10.4% respectively, which has a good effect on route optimization.