基于Voronoi邻近的物流车辆路径快速优化算法

 现代物流业需要快速高效并智能化制定物流运输方案。传统路径优化方法适合处理中小规模的车辆路径问题,计算时间较长,方案质量较低,故需发展短时间内能提供高质量路径方案的启发式算法。针对大规模物流车辆路径优化,本文提出了一种Voronoi邻近的快速优化方法。该方法先创建初始解,而后进行迭代优化。初始解创建利用Voronoi邻近关系,顾及车辆容量约束,自底向上进行客户点空间聚类,将问题降维;采用最廉价插入算法安排聚类内部路径,生成性质良好的初始解。迭代优化在客户点Voronoi邻近内进行有效的局部搜索,利用模拟退火机制接受较差解,从而跳出局部最优,不断提高解的质量。本文利用模拟生成的北京市大规模车辆路径问题进行实验,结果表明:本文算法能够在4500s内优化客户点高达12 000个物流车辆路径问题,计算时间较短,解的质量优良,算法性能稳定。本文与其他算法比较,能在较短时间内提供高质量车辆路径方案,适用于大规模物流车辆路径的优化。     

免疫遗传算法及其在VRP中的应用

物流配送车辆路径问题（VRP）是一类典型的NP问题。在基本遗传算法的基础上,根据生物的免疫系统原理,提出一种改进的算法——免疫遗传算法。在算法中构造一种基于抗体浓度的群体多样性保持策略,引入免疫算子和免疫记忆库。将该算法应用于求解VRP问题,实验结果表明算法可以实现解的多样性,避免出现早熟收敛,可以有效防止进化过程中最优解退化的可能,是求解车辆路径问题的一种有效的算法。     

车辆路径问题:从时间地理学的视角

车辆路径问题具有典型的时空分布特征,受到众多时空约束条件的制约。在车辆路径规划中,综合考虑时间和空间因素是非常必要的。本文从时间地理学这一全新的视角来研究车辆路径问题,提出一套完整的时间地理学分析框架,阐述了时间地理学的基本概念,提出了车辆路径问题中的时空约束、时空路径、时空棱柱、时空可达性、时空距离等概念,并给出了图示或定量化的度量方法。论文提出的时空距离度量方法综合考虑了顾客在空间位置和时间窗口2个方面的特征,可更科学地判定顾客之间的"邻近性"。论文通过设计一种求解大规模软时间窗车辆路径问题的算法,证明了时空距离的价值,并展望了时间地理学在求解动态车辆路径规划问题、移动设施路径规划问题等方面的应用。本文的贡献在于,通过时间地理学所提供的一系列概念和方法,实现了在统一的框架下同时考虑车辆路径问题(VRP)的时间和空间特征的构想,挖掘了传统时间地理学理论在车辆路径领域中的应用潜力,这将有利于更快或者更好地求解VRP问题。     

一种改进蚁群算法及其应用

蚁群算法是近年来出现的一种新的仿生优化算法.针对基本蚁群算法在求解过程中容易出现收敛时间过长以及易陷入局部最优解的不足,对算法中的状态转移、搜索方式以及信息素更新进行改进,提出了一种新的改进蚁群算法.一类典型旅行商问题的仿真实验表明改进的蚁群算法具有收敛速度快、全局搜索能力强和计算时间短的特点,证明了方法的可行性和有效性.     

一种基于改进蚁群算法与GIS的多约束配送中心选址方法

针对单一指派约束和容量约束的设施选址问题（Single Source Capacitated Facility Location Problem, SSCFLP）,建立了一种基于改进蚁群算法与GIS的配送中心选址方法。构建了以总成本费用最小为目标的配送中心选址模型;提出了适合求解SSCFLP问题的改进双层蚁群算法,将求解过程划分为彼此关联的设施选择层和需求指派层2层蚁群,采用改进的全局信息素更新策略加强双层蚁群交流,并对迭代最优解的指派关系进行局部优化;将方法应用于汽车配送中心的选址,利用GIS工具构建选址空间。实验结果表明,该选址方法能找到质量较好的选址及指派结果,对于求解同类问题具有较强的借鉴意义。     

城市商业区智能泊车系统的设计与开发

针对石家庄市商业区停车压力和停车管理系统现状,基于运动车辆的当前位置、车库中的车位数量、道路状况、路口限制等动态约束因子,进行了智能泊车系统的技术设计与软件开发。通过建立复杂约束条件下的模糊预测模型,并使用扩展和改进后相邻节点低值传递的最短路径引导算法,实现了城市商业区泊车过程中动态最短路径与最佳路径的分析与可视查询,并介绍了模拟应用情况。     

一种求解不等式约束秩亏平差问题的新算法

提出一种求解不等式约束秩亏平差问题的新算法,该算法将先验信息表示为不等式形式,并与秩亏平差模型构成不等式约束秩亏平差模型。结合Karush-Kuhn-Tucker条件可将该模型转化为线性互补问题,然后利用Lemke算法求解,克服了秩亏网中必要起算数据不足的问题,能保证解的唯一性。最后,模拟附先验信息的秩亏的GPS观测网,并结合多种经典的秩亏平差方法,验证了Lemke算法在处理不等式约束秩亏问题上的有效性。     

基于迭代局部搜索的区划问题算法研究

区划问题是将特定地理区域划分为若干空间连续的分区,满足分区内差异最小和分区间差异最大这一基本原则,广泛应用于地理、环境、生态、经济、农业、城市等领域。1960s以来,学者尝试建立各种区划问题数学模型,设计了一系列的求解算法,代表性的算法主要有：AZP、ARISEL、SKATER和REDCAP。本文提出了一个基于迭代局部搜索(ILS)的区划问题算法,进一步提升算法性能。该算法主要机制包括：邻域单元移动搜索改进分区质量;参照中心单元快速计算分区方差,提升算法速度;使用扰动机制跳出当前解局部最优状态;更新分区中心点提升分区方案目标值;使用群搜索探索更大的解空间;以及算法各步骤中通过分区空间连续判断和破碎修复保持分区空间连续。55个基准案例测试表明： ILS算法求解质量优于ARISEL和SKATER算法。一个多指标气候分区实验也表明： ILS算法求解质量优于SKATER、REDCAP和ARISEL算法。     

参数带椭球约束平差算法的应用

针对实际工程应用中遇到的参数带有范围约束的情形，提出带椭球约束的平差算法，并给出其具体模型和解算步骤。数值模拟实验和病态测边网数据计算表明，在处理病态问题时，最小二乘平差（least-squares，LS）已不适用，而与岭估计、奇异值分解法（singular value decomposition，SVD）以及不等式约束相比，本文算法精度更高。     

SA*：一种多线程路径规划算法

路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法（SA*）。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。