The multi-criteria constrained shortest path problem

被引：27

作者：

Shi, Ning ^{[1
]}

Zhou, Shaorui ^{[1
]}

Wang, Fan ^{[1
]}

Tao, Yi ^{[2
]}

Liu, Liming ^{[3
]}

机构：

[1] Sun Yat Sen Univ, Sch Business, Guangzhou, Guangdong, Peoples R China

[2] Guangdong Univ Technol, Sch Business, Guangzhou, Guangdong, Peoples R China

[3] Lingnan Univ Hongkong, Sch Business, Tuen Mun, Hong Kong, Peoples R China

来源：

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW | 2017年 / 101卷

基金：

中国国家自然科学基金;

关键词：

Routing; Constrained shortest path; Multi-criteria; Pareto-optimal paths; BI-OBJECTIVE OPTIMIZATION; INTERMODAL TRANSPORTATION; HAZARDOUS MATERIALS; ROUTING PROBLEM; NETWORK DESIGN; ALGORITHM; MODEL; ENUMERATION; SOLVE;

D O I：

10.1016/j.tre.2017.02.002

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

In this study, we propose an exact method for finding all the Pareto-optimal paths for a multi-criteria constrained shortest path problem. We show that solving the special bi-criteria problem is equivalent to generating at most |P| constrained shortest paths with successive tightened constraints, where |P| is the total number of all Pareto-optimal paths. For the general multi-criteria case, we propose a decomposition procedure and theoretically prove that this method can identify all the Pareto-optimal paths from at most (u - 1)!|P| candidate paths, where u is the number of criteria. Numerical studies demonstrate that our algorithm is highly efficient and robust. (C) 2017 Elsevier Ltd. All rights reserved.

引用

页码：13 / 29

页数：17

共 47 条

[1]

Ahuja RK, 1993, Network flows

[2] SHORTEST CHAIN SUBJECT TO SIDE CONSTRAINTS [J].

ANEJA, YP ;

AGGARWAL, V ;

NAIR, KPK .

NETWORKS, 1983, 13 (02) :295-302

[3]

[Anonymous], 1979, COMPUTERS INTRACTABI

[4]

[Anonymous], 2005, MULTICRITERIA OPTIMI

[5] A multi-objective sustainable load planning model for intermodal transportation networks with a real-life application [J].

Baykasoglu, Adil ;

Subulan, Kemal .

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2016, 95 :207-247

[6] AN ALGORITHM FOR THE RESOURCE CONSTRAINED SHORTEST-PATH PROBLEM [J].

BEASLEY, JE ;

CHRISTOFIDES, N .

NETWORKS, 1989, 19 (04) :379-394

[7] The Pollution-Routing Problem [J].

Bektas, Tolga ;

Laporte, Gilbert .

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL, 2011, 45 (08) :1232-1250

[8] A hybrid nature-inspired optimizer for wireless mesh networks design [J].

Benyamina, D. ;

Hafid, A. ;

Hallam, N. ;

Gendreau, M. ;

Maureira, J. C. .

COMPUTER COMMUNICATIONS, 2012, 35 (10) :1231-1246

[9] Accelerated label setting algorithms for the elementary resource constrained shortest path problem [J].

Boland, N ;

Dethridge, J ;

Dumitrescu, I .

OPERATIONS RESEARCH LETTERS, 2006, 34 (01) :58-68

[10] Bi-objective optimization of drayage operations in the service area of intermodal terminals [J].

Braekers, Kris ;

Caris, An ;

Janssens, Gerrit K. .

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2014, 65 :50-69

← 1 2 3 4 5 →