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

KARAOĞLAN İ., ALTIPARMAK BAYKOÇ F., KARA İ., DENGİZ B.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.211, sa.2, ss.318-332, 2011 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 211 Sayı: 2
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1016/j.ejor.2011.01.003
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.318-332
  • Anahtar Kelimeler: Logistics, Location-routing problem, Simultaneous pickup and delivery, Branch-and-cut, Simulated annealing, DEPOT, PROJECTION, SINGLE
  • Gazi Üniversitesi Adresli: Evet

Özet

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.