الگوریتم بهینه سازی چندگانه کلونی مورچه ها برای مسئله مسیریابی محل ظرفیت بندی شده

The success of a logistics system may depend on the decisions of the depot locations and vehicle routings. The location routing problem (LRP) simultaneously tackles both location and routing decisions to minimize the total system cost. In this paper a multiple ant colony optimization algorithm (MACO) is developed to solve the LRP with capacity constraints (CLRP) on depots and routes. We decompose the CLRP into facility location problem (FLP) and multiple depot vehicle routing problem (MDVRP), where the latter one is treated as a sub problem within the first problem. The MACO algorithm applies a hierarchical ant colony structure that is designed to optimize different subproblems: location selection, customer assignment, and vehicle routing problem, in which the last two are the decisions for the MDVRP. Cooperation between colonies is performed by exchanging information through pheromone updating between the location selection and customer assignment. The proposed algorithm is evaluated on four different sets of benchmark instances and compared with other algorithms from the literature. The computational results indicate that MACO is competitive with other well-known algorithms, being able to obtain numerous new best solutions.

The design of a logistics system is an important issue in today's competitive environment due to the significant contribution of the distribution cost to the total supply chain cost. This kind of problem is commonly solved in two phases: facility location for a long term policy and vehicle routing to satisfying customer demands for the operational decisions. These two components can be treated separately, but may lead to suboptimal solutions (Salhi and Rand, 1989). The location routing problem (LRP) integrates facility location problem (FLP), which determines the depot locations and allocates customers to each selected depot, and vehicle routing problem (VRP), which constructs the vehicle routes of the selected depot. Several real world applications can be found in the literature, for example, bill delivery (Lin et al., 2002), parcel delivery (Wasner and Zäpfel, 2004), and mobile network design (Billionnet et al., 2005). The LRP with capacities on both depots and routes is called capacitated LRP (CLRP) which is the focus of this paper. The CLRP can be represented by a graph G=(V, E), where V=I∪J. I={1, …, n} is the set of customer nodes and J={1, …, m} denotes the set of candidate depot locations. Each customer i∈I has a demand di. A capacity Rj and an opening cost fj are associated with each candidate depot site j∈J. Associated to each edge (i, j)∈E there is a routing cost cij which denotes the traveling distance or traveling cost between nodes i and j. A set K of homogeneous vehicles with capacity Q and cost C are available. Each customer must be served exactly once by only one vehicle. Each route must begin and end at the same depot and its total load cannot exceed vehicle capacity. The total load of the vehicles assigned to a depot cannot exceed the capacity of that depot. The objective is to find the optimal number and locations of the depots as well as the vehicle routes of each opened depot so as to minimize the sum of the fixed facility costs, transportation costs, and vehicle costs. The CLRP is very difficult to solve since it encompasses two NP-hard problems: facility location problem and vehicle routing problem (Garey and Johnson, 1979). In CLRP, the location–allocation decision will influence the total cost of vehicle routes and the architecture of vehicle routes will affect the location of depots and allocation of customers. Consequently, how to deal with the interdependence between these decisions is an important issue. In this paper, we solve both location and routing problems simultaneously rather than independently with nested methods based on the ant colony optimization algorithm. We apply a hierarchical structure, with facility location as the main problem and vehicle routing as a subordinate one. To wit, we decompose the CLRP into facility location and multi-depot vehicle routing problem, while the latter problem is embedded into the first one. This concept of hierarchy is also emphasized by Balakrishnan et al. (1987) and Nagy and Salhi (1996). The proposed multiple ant colony optimization algorithm (MACO) is evaluated by four sets of CLRP benchmark instances from the literature and its computational results are compared with state-of-the-art algorithms. The remainders of this paper are organized as follows. Section 2 provides an extensive review of LRP in the literature. The multiple ant colony optimization algorithm to tackle the CLRP is described in Section 3. In Section 4, the computational results of four groups of benchmark problems are reported. For each benchmark set we compare to the best available algorithms. Finally, conclusions are followed in Section 5

In this paper we proposed a multiple ant colony optimization (MACO) heuristic, which adopts a nested mechanism with three hierarchical solution construction rules, to solve the capacitated location routing problem (CLRP). The CLRP is to solve each of the three decisions in LRP: location selection, customer assignment and route construction. We decompose the CLRP hierarchically into facility location problem (FLP) and multiple depot vehicle routing problem (MDVRP), while the first one is the main problem and the latter problem to be a subordinate one. Thus, the MDVRP is solved embedded in the facility location problem. In each iteration, two ant colonies (location selection and customer assignment) communicate with each other through the global pheromone updating rule. The computational experiments are carried out on four sets of instances from the literature. Our MACO is able to obtain optimal or near-optimal solutions in a reasonable computation time for most benchmark instances. Our MACO reaches 28 and updates 12 best known solutions, respectively, in 94 instances considered in this study. The results show that the MACO can obtain good solutions on various kinds of CLRP instances within reasonable computational times. The MACO is especially very effective to solve the largest size LRP instances (n≥200) and the overall performance is competitive with other algorithms in the literature. Our MACO checks the facility capacity constraint after finishing the customer assignment, in the future we could check this during the customer assignment construction to reduce the computational time. Currently, each colony has its own control parameters in the MACO approach. It would be interesting to study the effect of using the same control parameters in each colony in the future. Another research direction could be the study on reliable location routing problem, in which some facilities are subject to failure. This could be happened in the disaster relief network. Other possible perspective could be applying the MACO to other combinatorial optimization problems that contain multiple-level decisions.