主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

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

• 论文 • 上一篇    下一篇

目标函数为∑和max的双目标最短路问题:算法和复杂性

李帮义1, 盛昭翰2   

  1. 1. 南京航空航天大学经济管理学院 南京 210016;
    2. 南京大学管理科学与工程研究院 南京 210093
  • 收稿日期:2002-08-19 修回日期:2003-08-28 出版日期:2003-10-28 发布日期:2012-03-06
  • 基金资助:
    国家自然科学基金资助项目(70171028)

One Shortest Path Problem with ∑ and max Objectives:Algorithms and Complexity

LI Bang-yi1, SHENG Zhao-han2   

  1. 1. College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China;
    2. Graduate School of Management Science and Engineering, Nanjing University, Nanjing 310093, China
  • Received:2002-08-19 Revised:2003-08-28 Online:2003-10-28 Published:2012-03-06

PDF (PC)

2017

被引次数

16

摘要： 本文研究了一个双目标最短路问题。在该问题中,一个目标函数是∑形式,另一个目标函数是max形式。首先给出了一个时间复杂性为O(m2logn)的算法产生代表有效解集合。然后研究了∑和max的组合目标函数最短路问题,对动态问题和静态问题,分别给出了一个时间复杂性都为O(m2logn)的算法。最后在字典序最优解的意义下,本文给出了两个时间复杂性都为O(mlogn)的算法。

关键词: 双目标, 最短路, 有效解, 算法

Abstract: In this paper,we study one bi-objective shortest path problem with one ∑ objective and one max objective.Firstly,an algorithm with time complexity O(m2 log n) is given to obtain the presenting efficient solution set.Then two algorithms with the same time complexity O(m2 log n) are given to obtain the ∑ and max optimal solutions for the static and dynamic combined problems.Lastly,two algorithms with the same time complexity O(m log n) are given to obtain the lexicographic order-optimal solution.

Key words: objective, shortest path, efficient solution, algorithm

中图分类号: