基于动态选择启发值的改进TD-FTT算法 被引量：1

1

作者 李佳佳 刘晓静 +2 位作者 刘向宇 夏秀峰 朱睿 《计算机应用》 CSCD 北大核心 2018年第1期120-125,共6页

针对时间依赖路网中的K近邻(KNN)查询TD-FTT算法查询点发起时间与到达时间在同一时段的限制和预处理阶段计算时间代价大的问题,提出基于动态选择启发值改进的TD-FTT(ITD-FTT)算法。首先,在预处理阶段,根据各时段各边时间函数的最小值构... 针对时间依赖路网中的K近邻(KNN)查询TD-FTT算法查询点发起时间与到达时间在同一时段的限制和预处理阶段计算时间代价大的问题,提出基于动态选择启发值改进的TD-FTT(ITD-FTT)算法。首先,在预处理阶段,根据各时段各边时间函数的最小值构建最小路网Gmin;然后,在路网Gmin中利用网络泰森图(NVD)并行计算节点最近邻来减少预处理阶段的计算时间;最后,在查找阶段通过计算节点到达时间所在时段,动态选择启发值来解除时间段的限制。实验结果显示,在预处理阶段ITD-FTT算法比TD-FTT算法计算时间减少了70.12%;在查询阶段ITDFTT比TD-INE算法和TD-A算法在遍历节点个数上分别减少了46.52%和16.63%,响应时间比TD-INE算法和TD-A算法分别降低47.46%和18.24%。实验结果表明,ITD-FTT算法减少了查询扩展的节点数,降低了查找K近邻的时间,提高了查找效率。 展开更多

关键词 时间依赖路网 K近邻查询 TD-fW算法 预处理 网络泰森图

下载PDF 职称材料

面向时间依赖路网的空间索引方法 被引量：1

2

作者 李佳佳 臧寅旭 +2 位作者 刘向宇 夏秀峰 朱睿 《计算机工程》 CAS CSCD 北大核心 2019年第5期127-134,共8页

在兴趣点(POI)呈稀疏分布时,现有时间依赖路网中的k近邻查询方法效率较低,且无法高效支持多类型的POI查询。为此,建立基于POI分布的空间索引结构TDG。根据路径权值上、下界对预计算路径进行剪枝优化,在此基础上,提出一种索引更新策略与... 在兴趣点(POI)呈稀疏分布时,现有时间依赖路网中的k近邻查询方法效率较低,且无法高效支持多类型的POI查询。为此,建立基于POI分布的空间索引结构TDG。根据路径权值上、下界对预计算路径进行剪枝优化,在此基础上,提出一种索引更新策略与基于TDG的k近邻查询算法。实验结果表明,与启发式查询算法相比,该算法的扩展节点数量平均减少87.5%,查询响应时间平均缩短33%～66%。 展开更多

关键词 时间依赖路网 多类型POI 网格划分 上、下界剪枝 K近邻查询

下载PDF 职称材料

生鲜电商配送的开放式时变车辆路径问题研究 被引量：16

3

作者 付朝晖 刘长石 《计算机工程与应用》 CSCD 北大核心 2021年第1期271-278,共8页

针对生鲜电商配送的“最后一公里”难题,考虑到生鲜农产品的易腐易损性与生鲜电商通常采用普通车辆配送等现实情况,引入常温条件下生鲜农产品的鲜活度度量函数;分析城市路网的时变特性,设计时变路网条件下的车辆行驶时间计算方法;综合... 针对生鲜电商配送的“最后一公里”难题,考虑到生鲜农产品的易腐易损性与生鲜电商通常采用普通车辆配送等现实情况,引入常温条件下生鲜农产品的鲜活度度量函数;分析城市路网的时变特性,设计时变路网条件下的车辆行驶时间计算方法;综合考虑客户需求量、时间窗、生鲜农产品送达客户时的鲜活度、开放式车辆路径与车辆灵活出发时间等因素,以总配送成本最小为目标构建具有鲜活度限制的开放式时变车辆路径问题优化模型,并根据模型特点设计一种改进蚁群算法求解。仿真实验结果表明:与封闭式车辆路径策略相比较,基于开放式车辆路径策略的改进蚁群算法能有效降低生鲜电商的总配送成本,减少车辆使用数量,缩短车辆行驶距离,具有合理性与可行性。 展开更多

关键词 时变路网 生鲜农产品 开放式车辆路径问题 改进蚁群算法

下载PDF 职称材料

考虑时变路网的多行程电动车辆路径问题研究

4

作者 程泽 王正国 +1 位作者 秦虎 毛树华 《武汉理工大学学报（信息与管理工程版）》 CAS 2024年第4期590-596,共7页

为了降低城市物流的电动车配送成本,考虑道路交通网络的时变性对电动车多行程配送活动进行研究。首先,以固定成本、充电成本和时间惩罚成本之和最小化为优化目标,构建时变路网下的多行程电动车辆路径问题模型;其次,利用自适应大规模邻... 为了降低城市物流的电动车配送成本,考虑道路交通网络的时变性对电动车多行程配送活动进行研究。首先,以固定成本、充电成本和时间惩罚成本之和最小化为优化目标,构建时变路网下的多行程电动车辆路径问题模型;其次,利用自适应大规模邻域搜索算法对实际案例进行求解;最后,分别对出发时刻、路网时变性、充电策略和电价进行分析。结果表明:路网时变性在不同时刻下对成本和配送用时的影响不同,不同出发时刻有着不同的最优路线规划;电价的小范围波动对配送活动的影响很小;充电策略的选择对配送用时和成本的影响显著。 展开更多

关键词 多行程 时变路网 车辆路径 自适应大规模邻域搜索 电动车辆

下载PDF 职称材料

时变路网条件下联合配送的开放式车辆路径问题 被引量：6

5

作者 刘长石 王松 +1 位作者 罗亮 邓胜前 《运筹与管理》 CSSCI CSCD 北大核心 2021年第11期26-33,共8页

针对城市物流系统中的多物流中心联合配送问题,设计一种多物流中心处理方法共享物流资源;分析城市路网的时变特性,设计路段行驶时间计算方法;综合考虑客户需求、时间窗、车辆不同出发时间、油耗、碳排放与联合配送模式等因素,以总成本... 针对城市物流系统中的多物流中心联合配送问题,设计一种多物流中心处理方法共享物流资源;分析城市路网的时变特性,设计路段行驶时间计算方法;综合考虑客户需求、时间窗、车辆不同出发时间、油耗、碳排放与联合配送模式等因素,以总成本最小为目标构建联合配送的开放式时变车辆路径规划模型,设计改进蚁群算法求解;实验结果表明以上方法具有可行性与有效性。 展开更多

关键词 时变路网 联合配送 多物流中心 开放式车辆路径问题 蚁群算法

下载PDF 职称材料

时变路网下考虑时空距离的同时配集货车辆路径优化 被引量：5

6

作者 范厚明 田攀俊 +1 位作者 吕迎春 张跃光 《系统管理学报》 CSSCI CSCD 北大核心 2022年第1期16-26,共11页

针对道路行驶速度时变且软时间窗条件下的同时配集货车辆路径问题,以车辆派遣成本、时间窗惩罚成本以及车辆运输成本之和最小化为目标建立路径优化模型。根据问题特征设计了考虑时空距离的混合变邻域搜索遗传算法,采用时空距离对客户进... 针对道路行驶速度时变且软时间窗条件下的同时配集货车辆路径问题,以车辆派遣成本、时间窗惩罚成本以及车辆运输成本之和最小化为目标建立路径优化模型。根据问题特征设计了考虑时空距离的混合变邻域搜索遗传算法,采用时空距离对客户进行聚类生成初始解,提高算法求解质量;将变邻域搜索算法的深度搜索能力运用到遗传算法的局部搜索策略中,增强算法的局部搜索能力;提出自适应邻域搜索次数策略以及模拟退火的新解接受机制,平衡种群进化所需的广度和深度。通过多组不同规模的算例验证了本文模型及算法的有效性,研究成果不仅深化和拓展同时配集货车辆路径问题的相关研究,也为物流企业优化车辆调度方案提供理论依据。 展开更多

关键词 时空距离 同时配集货 时变路网 异型车辆 混合变邻域搜索遗传算法

下载PDF 职称材料

随机时变路网环境下稳健路径选择及实证研究 被引量：5

7

作者 曹慧 段征宇 陈川 《交通运输系统工程与信息》 EI CSCD 北大核心 2014年第5期194-201,共8页

交通拥挤、天气、突发事故等不确定性因素影响着城市区域之间的路网提供的连通服务水平.本文对城市片区间道路连通路径选择进行研究.根据随机时变网络描述和稳健路径选取原则,建立了最优化模型,并采用改进的Dijkstra算法.通过深圳实例计... 交通拥挤、天气、突发事故等不确定性因素影响着城市区域之间的路网提供的连通服务水平.本文对城市片区间道路连通路径选择进行研究.根据随机时变网络描述和稳健路径选取原则,建立了最优化模型,并采用改进的Dijkstra算法.通过深圳实例计算,分析了出发时刻与最短路径行程时间和路段构成之间关系,并与确定性时变路网环境下进行计算结果对比.结果表明,随机时变路网环境下鲁棒性最优算法选择稳健路径具有合理性和可行性,可以很好地应用到区域动态连通情况的研究. 展开更多

关键词 智能交通 稳健路径选择 随机时变路网 鲁棒性 路网连通水平

下载PDF 职称材料

时间依赖路网上的移动对象K近邻查询算法 被引量：3

8

作者 张彤 秦小麟 《计算机科学》 CSCD 北大核心 2020年第1期79-86,共8页

随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点。以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景。因... 随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点。以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景。因此,文中提出了一种针对时间依赖路网上的移动对象K近邻查询算法TD-MOKNN,该算法分为预处理阶段和查询阶段。在预处理阶段,通过建立路网和网格索引,提出了一种新的移动对象到路网的映射方法,解除了以往研究假设移动对象恰好在路网顶点上的限制;在查询阶段,采用启发式搜索,借助倒排网格索引计算了一种新的高效启发值,通过预处理信息和启发值设计了高效K近邻查询算法,并给出了算法的正确性证明和时间复杂度分析。实验验证了所提算法的有效性,相比现有算法,TD-MOKNN算法在遍历顶点数和响应时间上分别减少了55.91%和54.57%,查询效率平均提升了55.2%。 展开更多

关键词 K近邻查询 移动对象 时间依赖路网 A^*算法 网格索引

下载PDF 职称材料

时变路网无能力约束车辆路径优化 被引量：2

9

作者 彭勇 刘洋 《价值工程》 2012年第27期114-116,共3页

讨论了一类时变路网下的无能力约束车辆配送路径优化问题,建立了基于时变路网的以配送总耗时最短为优化目标的无能力约束车辆配送路径优化模型。提出了基于实时Dijkstra算法的模型求解方法。数值算例表明考虑路网时变特性得到的优化配... 讨论了一类时变路网下的无能力约束车辆配送路径优化问题,建立了基于时变路网的以配送总耗时最短为优化目标的无能力约束车辆配送路径优化模型。提出了基于实时Dijkstra算法的模型求解方法。数值算例表明考虑路网时变特性得到的优化配送方案将更加符合配送实际。 展开更多

关键词 路径优化 车辆配送 时变路网 实时Dijkstra算法 无能力约束

下载PDF 职称材料

一种时间依赖路网最小时间路径规划算法研究 被引量：2

10

作者 孙奥 朱桂斌 +1 位作者 江铁 史名一 《计算机应用研究》 CSCD 北大核心 2012年第11期4148-4151,共4页

研究时间依赖路网(TDN)的最短路径规划算法,对指导人们出行和解决城市交通等问题具有十分重要的意义。在研究前人算法的基础上,提出了一种利用结构体数组来求解TDN路网最小时间路径规划算法。对算法的基本原理和结构体数组的构造进行了... 研究时间依赖路网(TDN)的最短路径规划算法,对指导人们出行和解决城市交通等问题具有十分重要的意义。在研究前人算法的基础上,提出了一种利用结构体数组来求解TDN路网最小时间路径规划算法。对算法的基本原理和结构体数组的构造进行了介绍,对算法实现流程及其中一些关键步骤进行了重点阐述,最后在VC++环境中利用MapX控件对算法进行了实验仿真。仿真结果表明,该算法具有较高的搜索效率,且能适应路况变化,基本满足现实需要。 展开更多

关键词 路径规划 最小时间 时间依赖路网 行程时间 结构体数组

下载PDF 职称材料

时变路网单车路径优化模型及算法 被引量：2

11

作者 彭勇 刘颖 《物流技术》 北大核心 2012年第9期249-252,共4页

讨论了一类时变路网下单车辆配送路径优化问题,建立了基于时变路网以配送完成时间最早为优化目标的单车配送路径优化模型。在增加贪婪配送策略情况下,给出了车辆行驶时间满足FIFO规则的动态规划精确求解方法。数值算例验证了理论分析得... 讨论了一类时变路网下单车辆配送路径优化问题,建立了基于时变路网以配送完成时间最早为优化目标的单车配送路径优化模型。在增加贪婪配送策略情况下,给出了车辆行驶时间满足FIFO规则的动态规划精确求解方法。数值算例验证了理论分析得到的结论。 展开更多

关键词 路径优化 动态规划 时变路网 FIFO规则

下载PDF 职称材料

时间依赖路网中限制到达时间的k近邻查询

12

作者 安云哲 倪灿灿 +2 位作者 李佳佳 张安珍 夏秀峰 《河南科技学院学报（自然科学版）》 2022年第5期58-68,共11页

针对网约车平台中用户希望车辆能够在指定时间内到达的问题,提出了时间依赖路网中限制到达时间的k近邻(Time-dependent k-Nearest Neighbor Query with Limited Arrival Time,TD-Lk NN)查询,目标是返回能够在给定时间段内到达查询点,且... 针对网约车平台中用户希望车辆能够在指定时间内到达的问题,提出了时间依赖路网中限制到达时间的k近邻(Time-dependent k-Nearest Neighbor Query with Limited Arrival Time,TD-Lk NN)查询,目标是返回能够在给定时间段内到达查询点,且车辆的空车时间最少的k个移动对象.首先提出了一种基于网格索引的TIGR(Time-aware Incremental Grid-based restrict)算法,用来获取移动对象的位置,以及限制查询范围.为进一步缩小查询范围以及减小候选集的大小,又提出了三种剪枝策略以及基于剪枝策略的TIGR_P(TIGR with Pruning Strategies)算法.基于对四组纽约真实地图数据进行的实验,验证了所提方法的正确性,以及三种剪枝策略的有效性.结果表明,在六组不同的实验参数下,使用不同的最快路径查询算法来支持TD-Lk NN查询时,TIGR_P算法的查询效率均可以比TIGR算法提升一个数量级左右. 展开更多

关键词 时间依赖路网 限制到达时间 空车时间 K近邻查询

下载PDF 职称材料

反向时间依赖路网上移动对象的启发式k近邻查询算法 被引量：1

13

作者 宋力翔 秦小麟 《小型微型计算机系统》 CSCD 北大核心 2021年第7期1532-1538,共7页

针对实际应用中用户在真实路网上进行移动服务(如出租车,救护车,外卖等)的查询需求,提出反向时间依赖路网上移动对象的k近邻查询问题.在分析现有查询算法的不足后,建立了反向时间依赖路网和基于标记点的最短路径树.并在此基础上,给出了... 针对实际应用中用户在真实路网上进行移动服务(如出租车,救护车,外卖等)的查询需求,提出反向时间依赖路网上移动对象的k近邻查询问题.在分析现有查询算法的不足后,建立了反向时间依赖路网和基于标记点的最短路径树.并在此基础上,给出了一种针对反向时间依赖路网上移动对象的k近邻查询算法TDSPT-k NN.通过采用基于最短路径树的启发式函数等剪枝策略,进一步提升查询效率.最后,通过仿真实验对TDSPT-k NN算法和已有算法在多种情况下的对比分析,结果表明相比现有算法,TDSPT-k NN算法查询效率平均提升65.9%,可以高效地处理反向时间依赖路网上移动对象的k近邻查询问题. 展开更多

关键词 K近邻查询 移动对象 时间依赖路网 启发式算法 最短路径树

下载PDF 职称材料