高速公路通行卡调配路径算法研究

摘要

随着高速公路的不断发展和里程不断增加,对于高速公路的管理而言,传统的高速公路收费模式由于不能很好地辨别司机走过的路径,只能以最低收费标准进行收费,每年因为高速公路通行卡偷逃漏行为而造成巨大的经济损失.尤其是随着高速公路省界收费站的取消,高速公路收费问题会变得更加严重,因此急需一种新的收费管理模式.在此情况下,CPC卡取代IC卡成为新的高速公路通行凭证,可以完美地解决二义性路段的收费问题,但是高昂的造价使得其调拨问题显得愈发重要.为了解决CPC卡的调拨问题,本文提出了一种可行的CPC卡调配方法.首先,在确定调拨周期后确定每个站点的盈亏情况,根据盈亏情况计算得到初始携带卡量.其次,将整个最短路问题视为TSP问题,在得到需进行调配站点坐标的情况下运用禁忌搜索算法得到一条连接所有站点的最短路以及需要的车辆个数.最后,车辆从调拨中心出发,携带一定卡量,对路途上缺卡公司进行补充,盈卡公司进行回收,完成整个调拨过程.