网络图中多约束条件下的路径选择问题

中国管理科学 ›› 2003, Vol. ›› Issue (4): 41-46.

网络图中多约束条件下的路径选择问题

贺铁林

中国科学院科技政策与管理科学研究所北京 100080

收稿日期:2002-10-18 修回日期:2003-05-30 出版日期:2003-08-28 发布日期:2012-03-06

On Multi-Constrained Paths in Networks

HE Tie-lin

Institute of Policy and Management, Chinese Academy of Sciences, Beijing 100080, China

Received:2002-10-18 Revised:2003-05-30 Online:2003-08-28 Published:2012-03-06

摘要/Abstract

摘要： 本文探讨了多约束条件下的路径选择问题。本文的工作在于对多约束条件下的路径选择问题进行了规范的描述和分类,并针对各类问题讨论了典型的求解算法,同时对现有算法进行了改进,使其更适用于求解管理科学领域中的MCP问题,从而拓展了该问题的应用空间。

关键词: 多约束条件, 最短路径算法, NP完全问题, 启发式算法

Abstract: In this paper,we discussed the multi constrained path(MCP)finding problem.The contributions of this paper lie in illustrating and classifying the MCP problem normatively.And for each kind of problem,it discusses typical algorithms.At the same time,the algorithms are extended to be more appropriate in solving MCP problem in the areas of management sciences.

Key words: multi-constraints, shortest path finding algorithms, NP-Complete, heuristic algorithms

中图分类号:

O221.7

贺铁林. 网络图中多约束条件下的路径选择问题[J]. 中国管理科学, 2003, (4): 41-46.

HE Tie-lin. On Multi-Constrained Paths in Networks[J]. Chinese Journal of Management Science, 2003, (4): 41-46.

[1]	黄志红,黄卫来,郭放. 考虑电池损耗的电动物流汽车充电设施选址与充电策略协同优化研究[J]. 中国管理科学, 2024, 32(6): 68-78.
[2]	代业明, 齐尧, 高红伟, 李陆. 基于PMSC管理及奖惩机制的智能电网实时定价研究[J]. 中国管理科学, 2022, 30(7): 88-98.
[3]	许保光, , 常嘉欣, , 高敏刚. 考虑人车混采的道路信息采集的路径规划研究[J]. 中国管理科学, 2022, 30(4): 218-227.
[4]	郭放, 黄志红, 黄卫来, 杨超. 考虑自取服务和门到门服务的电动汽车物流网络优化策略研究[J]. 中国管理科学, 2022, 30(2): 264-275.
[5]	王秀利, 徐悦, 胡修武. 中小呼叫中心月度排班优化模型与算法[J]. 中国管理科学, 2021, 29(4): 169-178.
[6]	吴江, 王旻轲, 谭涛, 张培文. 非平稳需求下考虑碳配额的供应链选址-库存模型与算法研究[J]. 中国管理科学, 2020, 28(3): 162-173.
[7]	郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8): 118-128.
[8]	张杨, 但斌, 高华丽. 带工期指派的产品服务系统订单随机调度问题研究[J]. 中国管理科学, 2019, 27(2): 93-106.
[9]	杨珺, 冯鹏祥, 孙昊, 杨超. 电动汽车物流配送系统的换电站选址与路径优化问题研究[J]. 中国管理科学, 2015, 23(9): 87-96.
[10]	熊中楷, 方衍, 张聪誉. 以旧换新收购方式下的逆向物流网络优化设计[J]. 中国管理科学, 2011, 19(6): 65-72.
[11]	蓝伯雄, 姜楠, 郑燕. 求解大规模生产批量问题的启发式算法[J]. 中国管理科学, 2010, 18(2): 81-88.
[12]	肖依永, 常文兵, 张人千. 能力与资源双重约束下的启发式组合生产计划研究[J]. 中国管理科学, 2008, 20(6): 33-40.
[13]	鲁奎, 杨昌辉, 戴道明. 一种能力外包且费用时变批量问题的启发式算法[J]. 中国管理科学, 2008, 16(1): 80-85.
[14]	乔忠, 李凌颖. 商品交易市场网络节点选址的双层规划模型——以安徽省砀山县为例[J]. 中国管理科学, 2008, 16(1): 125-130.
[15]	何波, 杨超, 张华. 废弃物回收的多层逆向物流网络优化设计问题研究[J]. 中国管理科学, 2007, 15(3): 61-67.