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

中国管理科学 ›› 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]. 中国管理科学, 2020, 28(3): 162-173.
[2]	郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8): 118-128.
[3]	张杨, 但斌, 高华丽. 带工期指派的产品服务系统订单随机调度问题研究[J]. 中国管理科学, 2019, 27(2): 93-106.
[4]	杨珺, 冯鹏祥, 孙昊, 杨超. 电动汽车物流配送系统的换电站选址与路径优化问题研究[J]. 中国管理科学, 2015, 23(9): 87-96.
[5]	熊中楷, 方衍, 张聪誉. 以旧换新收购方式下的逆向物流网络优化设计[J]. 中国管理科学, 2011, 19(6): 65-72.
[6]	蓝伯雄, 姜楠, 郑燕. 求解大规模生产批量问题的启发式算法[J]. 中国管理科学, 2010, 18(2): 81-88.
[7]	肖依永, 常文兵, 张人千. 能力与资源双重约束下的启发式组合生产计划研究[J]. 中国管理科学, 2008, 20(6): 33-40.
[8]	乔忠, 李凌颖. 商品交易市场网络节点选址的双层规划模型——以安徽省砀山县为例[J]. 中国管理科学, 2008, 16(1): 125-130.
[9]	鲁奎, 杨昌辉, 戴道明. 一种能力外包且费用时变批量问题的启发式算法[J]. 中国管理科学, 2008, 16(1): 80-85.
[10]	何波, 杨超, 张华. 废弃物回收的多层逆向物流网络优化设计问题研究[J]. 中国管理科学, 2007, 15(3): 61-67.
[11]	李延晖, 马士华. 基于时间约束的单源/p个中转点配送系统的MINLP模型[J]. 中国管理科学, 2004, (3): 86-90.
[12]	黄伟文, 钱雁南, 许保光. “行/列约束法”在外贸进出口货柜运输业务上的应用[J]. 中国管理科学, 2002, (1): 89-93.
[13]	单连龙, 高自友. 公交系统随机平衡网络设计模型及求解算法[J]. 中国管理科学, 2001, (1): 41-49.
[14]	赵赫, 杜端甫. TSP的邻域搜索算法的分析和改进[J]. 中国管理科学, 1997, (1): 35-39.