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

中国管理科学 ›› 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]. 中国管理科学, 2025, 33(8): 144-155.
[2]	王艳婷, 郑维博, 马志强, 何正文. 不同业主支付方式下基于鲁棒性阈值的净现值最大化项目调度优化[J]. 中国管理科学, 2025, 33(4): 185-196.
[3]	张杰, 李妍峰. 突发传染病环境下生鲜配送的选址-路径问题[J]. 中国管理科学, 2025, 33(3): 196-208.
[4]	赵金龙, 蒋忠中, 万明重, 张春征. 考虑配送截止时间的“货到人”订单拣选优化问题研究[J]. 中国管理科学, 2025, 33(3): 239-255.
[5]	黄志红,黄卫来,郭放. 考虑电池损耗的电动物流汽车充电设施选址与充电策略协同优化研究[J]. 中国管理科学, 2024, 32(6): 68-78.
[6]	郑斐峰, 王志鑫, 刘明. 考虑峰谷分时电价和电池损耗成本的纯电动公交车充电调度优化研究[J]. 中国管理科学, 2024, 32(11): 125-135.
[7]	代业明, 齐尧, 高红伟, 李陆. 基于PMSC管理及奖惩机制的智能电网实时定价研究[J]. 中国管理科学, 2022, 30(7): 88-98.
[8]	许保光, , 常嘉欣, , 高敏刚. 考虑人车混采的道路信息采集的路径规划研究[J]. 中国管理科学, 2022, 30(4): 218-227.
[9]	郭放, 黄志红, 黄卫来, 杨超. 考虑自取服务和门到门服务的电动汽车物流网络优化策略研究[J]. 中国管理科学, 2022, 30(2): 264-275.
[10]	王秀利, 徐悦, 胡修武. 中小呼叫中心月度排班优化模型与算法[J]. 中国管理科学, 2021, 29(4): 169-178.
[11]	吴江, 王旻轲, 谭涛, 张培文. 非平稳需求下考虑碳配额的供应链选址-库存模型与算法研究[J]. 中国管理科学, 2020, 28(3): 162-173.
[12]	郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8): 118-128.
[13]	张杨, 但斌, 高华丽. 带工期指派的产品服务系统订单随机调度问题研究[J]. 中国管理科学, 2019, 27(2): 93-106.
[14]	杨珺, 冯鹏祥, 孙昊, 杨超. 电动汽车物流配送系统的换电站选址与路径优化问题研究[J]. 中国管理科学, 2015, 23(9): 87-96.
[15]	熊中楷, 方衍, 张聪誉. 以旧换新收购方式下的逆向物流网络优化设计[J]. 中国管理科学, 2011, 19(6): 65-72.