-
题名最小费用充电站选址问题的分支定界算法
被引量：7
- 1
-
-
作者
孙智勇
宁爱兵
傅汤毅
尹思淼
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机应用研究》
CSCD
北大核心
2022年第1期80-83,共4页
-
基金
国家自然科学基金项目(71401106)
上海市“管理科学与工程”高原学科建设项目。
-
文摘
电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。
-
关键词
充电站选址
精确算法
上界算法
下界算法
分支定界算法
-
Keywords
charging station location problem
exact algorithm
upper bound algorithm
lower bound algorithm
branch and bound algorithm
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名充电站选址问题的降阶回溯算法
被引量：2
- 2
-
-
作者
孙智勇
宁爱兵
傅汤毅
夏萌萌
张惠珍
-
机构
上海理工大学管理学院
-
出处
《系统科学与数学》
CSCD
北大核心
2020年第7期1133-1145,共13页
-
基金
国家自然科学基金(71401106)
上海市教委“管理科学与工程”高原学科建设项目资助课题。
-
文摘
电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-难问题.文章首先研究了该问题良好的数学性质并给予相应的证明,其中包括可以批量确定某些设施一定开设或一定不开设的性质,利用这些性质降低问题的规模,从而降低问题的求解难度;然后设计了上界子算法,下界子算法,分配子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的降阶回溯算法;最后通过分析和求解一个示例来进一步阐述文章算法的原理和执行过程,结果表明所提出的算法能够有效地降低时间复杂度.
-
关键词
充电站选址
精确算法
上界算法
下界算法
回溯算法
-
Keywords
Charging station location problem
exact algorithm
upper bound algorithm
lower bound algorithm
backtracking algorithm
-
分类号
U491.8
[交通运输工程—交通运输规划与管理]
TM910.6
[交通运输工程—道路与铁道工程]
-
-
题名最大覆盖选址问题的一种降阶回溯算法
被引量：2
- 3
-
-
作者
彭大江
宁爱兵
尚春剑
张惠珍
-
机构
上海理工大学管理学院
-
出处
《系统管理学报》
CSSCI
CSCD
北大核心
2020年第2期346-353,共8页
-
基金
国家自然科学基金资助项目(71401106)
上海市一流学科建设资助项目(S1201YLXK)。
-
文摘
最大覆盖选址问题在实际生活中有广泛的应用,是组合优化中的一个NP-Hard问题。首先提出问题的上下界子算法,然后研究数学性质,其中包括可以批量确定某些设施一定开设或一定不开设的性质。最后,利用上下界子算法和这些数学性质设计出一种可以快速减小问题规模且能求出最优解的降阶回溯算法。通过一个示例阐述该算法的执行过程。
-
关键词
最大覆盖选址问题
精确算法
上界算法
下界算法
-
Keywords
maximal covering location problem
exact algorithm
upper bound algorithm
lower bound algorithm
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名最小连通顶点覆盖问题的降阶回溯算法
- 4
-
-
作者
曾宾
宁爱兵
付振星
李之桥
张惠珍
-
机构
上海理工大学管理学院
-
出处
《运筹与管理》
CSCD
北大核心
2024年第3期28-34,共7页
-
基金
国家自然科学基金资助项目(71401106)。
-
文摘
本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。
-
关键词
最小连通顶点覆盖
上界子算法
下界子算法
回溯子算法
-
Keywords
minimum connected vertex cover
upper bound sub algorithm
lower bound sub algorithm
backtracking sub algorithm
-
分类号
O223
[理学—运筹学与控制论]
-
-
题名灾后应急配送中心选址问题的降阶回溯算法
- 5
-
-
作者
胡开元
宁爱兵
尹远翔
陈至伟
张惠珍
-
机构
上海理工大学管理学院
-
出处
《物流科技》
2024年第16期1-5,共5页
-
基金
国家自然科学基金(71401106)
上海市“管理科学与工程”高原学科建设项目。
-
文摘
近年来自然灾害频发,提高灾后应急物资的配送效率一直以来都是性命攸关的大事,因此文章基于灾后应急配送中心选址问题的精确算法进行研究。首先,建立该问题的数学模型并对该问题中的数学性质进行研究和证明;其次,在这些数学性质的基础上,设计上下界子算法和降阶子算法,这些子算法能够有效减少解空间,提高算法的效率,使该算法能够更有效地处理规模更大的问题;再次,提出降阶回溯子算法,通过剪枝和局部降阶进一步缩小问题的搜索规模,并能得到最优解;最后,通过分析和解决一个案例来更清楚地说明算法的原理和操作步骤。
-
关键词
应急配送中心选址问题
上下界算法
降阶回溯算法
-
Keywords
location problem of emergency distribution center
upper and lower bound algorithm
reduced order backtracking algorithm
-
分类号
F259
[经济管理—国民经济]
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名最小支配阈值集问题的降阶回溯算法
- 6
-
-
作者
储旭
宁爱兵
胡开元
代苏玉
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机工程与科学》
CSCD
北大核心
2024年第5期897-906,共10页
-
基金
国家自然科学基金(71401106)。
-
文摘
图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出上界子算法、下界子算法和降阶子算法,并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR;最后,通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。
-
关键词
最小支配阈值集问题
数学性质
上下界算法
降阶回溯算法
-
Keywords
threshold-minimum dominating set problem
mathematical property
upper and lower bound algorithm
backtracking algorithm with reduction
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名有约束竞争选址问题的降阶回溯算法
被引量：1
- 7
-
-
作者
傅汤毅
宁爱兵
孙智勇
林道晗
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机应用研究》
CSCD
北大核心
2021年第12期3678-3682,共5页
-
基金
国家自然科学基金项目(71401106)
上海市一流学科建设项目(S1201YLXK)。
-
文摘
有约束竞争选址问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时或是无法求得最优解或是求解速度慢。针对现有算法的缺点,首先在这个经典问题的基础上进行修改,构建了一个新的数学模型;接着对该模型的数学性质进行研究,并在数学性质的基础上提出了上下界算法和降阶子算法对问题进行降阶,达到了缩减问题搜索解空间的目的,降阶的过程中既有单个的降阶,也有成批的降阶;然后在前面的基础上设计了一个回溯子算法来求解问题的最优解;最后通过两个示例分析更清楚地阐述该算法的原理,结果证明该算法可以较快求得最优解。
-
关键词
竞争选址
上下界算法
降阶算法
回溯算法
-
Keywords
competitive location
upper and lower bound algorithm
reduced order algorithm
backtracking algorithm
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名奖励-收集顶点覆盖问题的精确算法
- 8
-
-
作者
曾宾
宁爱兵
付振星
徐江盼
张惠珍
-
机构
上海理工大学管理学院
-
出处
《计算机时代》
2023年第5期51-56,共6页
-
基金
国家自然科学基金(71401106)
上海市“管理科学与工程”高原学科建设项目。
-
文摘
奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数学性质设计出上下界子算法、降阶子算法、回溯子算法,通过降阶子算法可以降低该问题的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间。通过应用和算法对比表明,所设计的算法比没有考虑该问题数学性质的一般精确算法的时间复杂度更低。
-
关键词
奖励-收集顶点覆盖
上下界子算法
降阶子算法
回溯子算法
-
Keywords
prize-collecting vertex cover
upper and lower bound sub-algorithm
reduced-order sub-algorithm
backtracking subalgorithm
-
分类号
O223
[理学—运筹学与控制论]
-
