A branch-and-price algorithm for the multi-trip multi-repairman problem with time windows

被引：24

作者：

Liu, Shixin ^{[1
]}

Qin, Shujin ^{[1
]}

Zhang, Ruiyou ^{[1
]}

机构：

[1] Northeastern Univ, Coll Informat Sci & Engn, Shenyang 110819, Liaoning, Peoples R China

来源：

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW | 2018年 / 116卷

基金：

中国国家自然科学基金;

关键词：

Multi-trip multi-repairman problem; Integrated traveling cost; Route-generating approach; Branch-and-price algorithm; Cloud branching strategy; VEHICLE-ROUTING PROBLEM; COLUMN GENERATION; CONSTRAINTS;

D O I：

10.1016/j.tre.2018.05.009

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

This study introduces the multi-trip multi-repairman problem with time windows where an integrated traveling cost involving distance-dependent and time-dependent costs needs to be minimized. The problem is formulated as two mixed integer programming models. A branch-and-price algorithm is proposed, in which two route-generating approaches are devised to handle the pricing sub-problem. A large number of instances are randomly generated based on an actual service network of China. The proposed algorithm is validated based on these instances and compared to the direct solving method using Cplex. The comparison to the single-trip mode indicates the advantages of the multi-trip mode.

引用

页码：25 / 41

页数：17

共 32 条

[1] Branching rules revisited [J].

Achterberg, T ;

Koch, T ;

Martin, A .

OPERATIONS RESEARCH LETTERS, 2005, 33 (01) :42-54

[2]

[Anonymous], 1990, WORKING PAPER

[3]

Applegate D., 2011, TRAVELING SALESMAN P, P411

[4] An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles [J].

Azi, Nabila ;

Gendreau, Michel ;

Potvin, Jean-Yves .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 202 (03) :756-763

[5] Branch-and-price: Column generation for solving huge integer programs [J].

Barnhart, C ;

Johnson, EL ;

Nemhauser, GL ;

Savelsbergh, MWP ;

Vance, PH .

OPERATIONS RESEARCH, 1998, 46 (03) :316-329

[6]

Berthold Timo, 2013, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013. Proceedings, P28, DOI 10.1007/978-3-642-38171-3_3

[7]

Blum A., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P163, DOI 10.1145/195058.195125

[8]

Bnichou M., 1971, Math. Program, V1, P76, DOI DOI 10.1007/BF01584074

[9] Solving the traveling repairman problem on a line with general processing times and deadlines [J].

Bock, Stefan .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 244 (03) :690-703

[10] Vehicle routing problems with multiple trips [J].

Cattaruzza, Diego ;

Absi, Nabil ;

Feillet, Dominique .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2016, 14 (03) :223-259

← 1 2 3 4 →