Modelling and Solving the Capacitated Location-Routing Problem with Simultaneous Pickup and Delivery Demands

Abstract

In this work, the capacitated location-routing problem with simultaneous pickup and delivery (CLRP-SPD) is considered. This problem is a more realistic case of the capacitated location-routing problem (CLRP) and belongs to the reverse logistics of the supply chain. The problem has many real-life applications of which some have been addressed in the literature such as management of liquid petroleum gas tanks, laundry service of hotels and drink distribution. The CLRP-SPD is composed of two well-known problems; facility location problem and vehicle routing problem. In CLRP-SPD, a set of customers with given delivery and pickup demands should be supplied by a fleet of vehicles that start and end their tours at a single depot. Moreover, the depots and vehicles have a predefined capacity and the objective function is minimizing the route distances, fixed costs of establishing the depot(s) and employing the vehicles. The node-based MIP formulation of the CLRP-SPD is proposed based on the literature of the problem. To solve the model, a greedy clustering method (GCM) is developed which includes four phases; clustering the customers, establishing the proper depot(s), assigning the clusters to depot(s) and constructing the vehicle tours by ant colony system (ACS). The numerical experiments on two sets of test problems with different sizes on the number of customers and candidate depots show the efficiency of the heuristic method with the proposed method in the literature. Finally, performance of the heuristic method to the similar methods in the literature is evaluated by several standard test problems of the CLRP.