A Branch-and-Cut method for the Capacitated Location-Routing Problem

被引：161

作者：

Belenguer, Jose-Manuel ^{[1
]}

Benavent, Enrique ^{[1
]}

Prins, Christian

Prodhon, Caroline

Calvo, Roberto Wolfler ^{[2
]}

机构：

[1] Univ Valencia, Dept Estadist & Invest Operat, E-46003 Valencia, Spain

[2] Univ Paris 13, LIPN, UMR 7030, F-93430 Villetaneuse, France

来源：

COMPUTERS & OPERATIONS RESEARCH | 2011年 / 38卷 / 06期

关键词：

Location Routing Problem; Branch and Cut; Vehicle routing; Facility location; ALGORITHM; VEHICLE; DEPOT;

D O I：

10.1016/j.cor.2010.09.019

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Recent researches in the design of logistic networks have shown that the overall distribution cost may be excessive if routing decisions are ignored when locating depots The Location-Routing Problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions The aim of this paper is to propose an exact approach based on a Branch-and-Cut algorithm for solving the LRP with capacity constraints on depots and vehicles The proposed method is based on a zero-one linear model strengthened by new families of valid inequalities The computational evaluation on three sets of instances (34 instances in total) with 5-10 potential depots and 20-88 customers shows that 26 instances with five depots are solved to optimality including all instances with up to 40 customers and three with 50 customers (C) 2010 Elsevier Ltd All rights reserved

引用

页码：931 / 941

页数：11

共 36 条

[21] ODD MINIMUM CUT SETS AND b-MATCHINGS REVISITED [J].

Letchford, Adam N. ;

Reinelt, Gerhard ;

Theis, Dirk Oliver .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (04) :1480-1487

[22] A new branch-and-cut algorithm for the capacitated vehicle routing problem [J].

Lysgaard, J ;

Letchford, AN ;

Eglese, RW .

MATHEMATICAL PROGRAMMING, 2004, 100 (02) :423-445

[23]

Lysgaard J., 2004, CVRPSEP PACKAGE

[24] Combined location-routing problems: A synthesis and future research directions [J].

Min, H ;

Jayaraman, V ;

Srivastava, R .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 108 (01) :1-15

[25]

Naddef D, 2002, SIAM MONOG DISCR MAT, P53

[26]

Nagy G., 1998, Top, V6, P261

[27] A BRANCH-AND-CUT ALGORITHM FOR THE RESOLUTION OF LARGE-SCALE SYMMETRICAL TRAVELING SALESMAN PROBLEMS [J].

PADBERG, M ;

RINALDI, G .

SIAM REVIEW, 1991, 33 (01) :60-100

[28]

Prins C., 2006, SOLVING CAPACITATED, V4, P221, DOI DOI 10.1007/S10288-006-0001-9

[29] Solving the capacitated location-routing problem by a cooperative lagrangean relaxation-granular tabu search heuristic [J].

Prins, Christian ;

Prodhon, Caroline .

TRANSPORTATION SCIENCE, 2007, 41 (04) :470-483

[30]

Prins C, 2006, LECT NOTES COMPUT SC, V3906, P183

← 1 2 3 4 →