Multi-commodity location-routing: Flow intercepting formulation and branch-and-cut algorithm

Research on the location-routing problem (LRP) is very active, producing a good number of effective exact and approximated solution approaches. It is noteworthy that most of the contributions present in the literature address the single-commodity LRP, whereas the multi-commodity case has been scarcely investigated. Yet, this issue assumes an important role in many LRP applications, particularly in the context of designing single-tier freight distribution City Logistics systems. To fill this gap, we define a new multi commodity LRP, proposing an original integer linear programming model for it. The proposed formulation takes into account the multi-commodity feature of the problem, modeling the strategic location and the tactical routing decisions using the flow intercepting approach. We therefore name this problem the flow intercepting facility location-routing problem. It is solved by a branch-and-cut algorithm which exploits cuts derived and adapted from literature. The proposed method is successfully experienced and validated on test instances reproducing different network topologies and problem settings. (C) 2017 Elsevier Ltd. All rights reserved.