一种求解广义旅行商问题的圈生成算法
实质审查的生效
摘要
本发明公开了一种求解广义旅行商问题的圈生成算法，包括以下步骤：S1、搜索所有服务节点之间的最短路，将GTSP转化为TSP；S2、构建初始费用矩阵；S3、构造指派问题并求解；S4、由指派问题的解获取联接了网路中所有元素的序列集合；S5、由序列生成圈、合成圈；S6、判断是否生成最终回路，如果是，输出结果；否则计算圈之间的费用并构造费用矩阵，返回S3进行构造指派问题生成圈,直到生成一个圈时结束算法。根据本发明，可以在多项式时间内求得一个NP难问题的近似最优解，避免了现有方法计算效率低下的问题。
基本信息
专利标题 ：
一种求解广义旅行商问题的圈生成算法
专利标题（英）：
暂无
公开（公告）号 ：
CN114386711A
申请号 ：
CN202210077476.X
公开（公告）日 ：
2022-04-22
申请日 ：
2022-01-24
授权号 ：
暂无
授权日 ：
暂无
发明人 ：
何胜学崔允汀梁士栋袁鹏程何建佳
申请人 ：
上海理工大学
申请人地址 ：
上海市杨浦区军工路516号
代理机构 ：
上海邦德专利代理事务所(普通合伙)
代理人 ：
梁剑
优先权 ：
CN202210077476.X
主分类号 ：
G06Q10/04
IPC分类号 ：
G06Q10/04
IPC结构图谱
G
G部——物理
G06
计算；推算或计数
G06Q
专门适用于行政、商业、金融、管理、监督或预测目的的数据处理系统或方法；其他类目不包含的专门适用于行政、商业、金融、管理、监督或预测目的的处理系统或方法
G06Q10/00
行政；管理
G06Q10/04
预测或优化，例如线性规划、“旅行商问题”或“下料问题”
法律状态
2022-05-10 ：
实质审查的生效
IPC(主分类) : G06Q 10/04
申请日 : 20220124
申请日 : 20220124
2022-04-22 ：
公开
注：本法律状态信息仅供参考，即时准确的法律状态信息须到国家知识产权局办理专利登记簿副本。
文件下载
暂无PDF文件可下载
