论文摘要
货运配载是在我国交通运输行业特定历史环境下产生的一种运输模式,它为提高我国公路运输效率做出了巨大贡献。这种运输模式中,最关键的环节之一是配货信息的交流。传统配货信息的交流主要是通过分布于道路两侧的“空车配货站”进行,这种信息交流方式效率低下,经常会出现有货源信息但一时又找不到合适的车辆信息,有了车辆信息却找不到货源信息的状态,丧失了许多交易机会。为此,交通部公路科学院在1998年投资1000多万元建设了华夏交通在线,开展网络配载业务,随后几年,又有多个配货网站投入运营。利用互联网进行配货信息交流,拓宽了货源信息交流渠道,有助于配载交易形成,在一定程度上降低了空载率,提高了运输效率,无疑是空车配货模式发展的正确方向。但是,这种通过网页浏览的方式来对海量配货信息进行发布和检索效率仍然不高,迫切需要一种能够自动根据路径特点对配货信息进行筛选的信息检索方式。货运配载的路径匹配问题,属于开放型车辆路径问题(Open Vehicle RoutingProblem,OVRP)的一类。但目前对车辆路径问题的研究大多面向数学模型,通常需要较长的建模与计算时间,是面向离线的、非实时的应用,并不能直接应用于求解我国货运配载路径信息匹配的实际问题。针对此情况,本文在充分调研我国货运配载的产生发展和运营过程的基础上,对近几年出现的网络配载模式及功能进行深入分析,引入网络图模型,提出了一个基于交通路网的路径匹配算法。该算法利用交通路网中各结点之间的距离关系,可以检索给定起迄点间及起迄点与各自邻近结点群之间存在的配货信息,同时规划出收益费用比最优的行驶路径,并能根据配货行驶路径的特点对检索出的所信息进行分析、评价和优选,以方便配货组织。文章除了对算法思想和算法描述进行了详细介绍外,还对算法的时空复杂度进行了分析,以证实算法的可行性。最后,文章有重点地介绍了算法仿真实现所需的数据结构、功能函数和部分关键代码。