A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery

被引：119

作者：

Karaoglan, Ismail ^{[2
]}

Altiparmak, Fulya ^{[1
]}

Kara, Imdat ^{[3
]}

Dengiz, Berna ^{[3
]}

机构：

[1] Gazi Univ, Dept Ind Engn, Ankara, Turkey

[2] Selcuk Univ, Dept Ind Engn, Konya, Turkey

[3] Baskent Univ, Dept Ind Engn, Ankara, Turkey

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2011年 / 211卷 / 02期

关键词：

Logistics; Location-routing problem; Simultaneous pickup and delivery; Branch-and-cut; Simulated annealing; DEPOT; PROJECTION; SINGLE;

D O I：

10.1016/j.ejor.2011.01.003

中图分类号：

C93 [管理学];

学科分类号：

120117 [社会管理工程];

摘要：

This paper addresses a location-routing problem with simultaneous pickup and delivery (LRPSPD) which is a general case of the location-routing problem. The LRPSPD is defined as finding locations of the depots and designing vehicle routes in such a way that pickup and delivery demands of each customer must be performed with same vehicle and the overall cost is minimized. We propose an effective branch-and-cut algorithm for solving the LRPSPD. The proposed algorithm implements several valid inequalities adapted from the literature for the problem and a local search based on simulated annealing algorithm to obtain upper bounds. Computational results, for a large number of instances derived from the literature, show that some instances with up to 88 customers and 8 potential depots can be solved in a reasonable computation time. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：318 / 332

页数：15

共 45 条

[1]

An improved branch-and-cut algorithm for the capacitated vehicle routing problem [J].