论文研究-Ant colony optimization with clustering for solving the dyn....pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.47M 资料格式：pdf 举报版权申诉

weixin_39841365-11565960-4744302543427527810.pdf-第1页.png

第1页 / 共31页

weixin_39841365-11565960-4744302543427527810.pdf-第2页.png

第2页 / 共31页

weixin_39841365-11565960-4744302543427527810.pdf-第3页.png

第3页 / 共31页

weixin_39841365-11565960-4744302543427527810.pdf-第4页.png

第4页 / 共31页

weixin_39841365-11565960-4744302543427527810.pdf-第5页.png

第5页 / 共31页

weixin_39841365-11565960-4744302543427527810.pdf-第6页.png

第6页 / 共31页

weixin_39841365-11565960-4744302543427527810.pdf-第7页.png

第7页 / 共31页

weixin_39841365-11565960-4744302543427527810.pdf-第8页.png

第8页 / 共31页

文本预览

http://www.paper.edu.cn 基于聚类的蚁群优化算法解决动态定位路径问题高尚策1,2，王艺睿1，程久军3，Yasuhiro Inazumi2，Yuki Todo4 1 东华大学信息科学与技术学院，中国上海市　201620 2 富山大学创新研究生院，日本富山市　930-8555 3 同济大学嵌入式系统与服务计算重点实验室，中国上海市　200092 4 金泽大学电子与计算机工程学院，日本金泽市　920-1192 摘要：蚁群算法由于它的鲁棒性和自适应性可以解决动态优化问题。在动态环境下，这种算法的目的不再是发现一个最优解，而是随着时间跟踪最优解。在本文，提出了一种聚类蚁群算法伴随三种移民策略去解决动态定位路径问题。这种问题可以划分为在动态环境下的定位分配问题和机车路由问题两部分。为了处理定位分配问题，一种K-means聚类算法被用来解决在一类中仓库的位置及其周边的城市。然后利用带有随机移民，精英移民和存储移民三种策略的蚁群算法解决由随机和循环交通因素组成的动态环境下的机车路由问题。通过对比实验来比较使用聚类的效果。基于不同种规模的LRP问题的实验结果证明，根据解的质量和鲁棒性，聚类算法能够显著提高K-ACS的性能。而且，K-ACS显示出了很有前景的性能在解决不同种动态环境下的LRP问题，意味着提出的算法可能成为一种新的技术，通过利用聚类和进化的特性去解决环境的变化。关键词：蚁群算法，聚类算法，移民策略，定位路由. 中图分类号： TP391 Ant colony optimization with clustering for solving the dynamic location routing problem Shangce Gao1,2, Yirui Wang1,Jiujun Cheng3,Yasuhiro Inazumi2,Yuki Todo4 1 College of Information Science and Technology, Donghua University, Shanghai, China 2 Graduate School of Innovative Life Science, University of Toyama, Toyama-shi, Japan 201620 930-8555 3 The Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai, China 200092 基金项目： National Natural Science Foundation of China (Grants No. 61203325), Shanghai Rising-Star Program (No. 14QA1400100), \Chen Guang”project supported by Shanghai Municipal Education Commission and Shanghai Education Development Foundation (No. 12CG35), Ph.D. Program Foundation of Ministry of Education of China (No. 20120075120004), the Fundamental Research Funds for the Central Universities (No. 2232013D3-39). 作者简介： Correspondence author：Gao Shangce，male，associate professor，gaosc@dhu.edu.cn, major research direction：articial immune system, articial neural network. - 1 -

http://www.paper.edu.cn 4 School of Electrical and Computer Engineering, Kanazawa University, Kanazawa-shi, Japan 920-1192 Abstract: Ant colony algorithm can resolve dynamic optimization problems due to its robustness and adaptation. The aim of such algorithms in dynamic environments is no longer to ﬁnd an optimal solution but to trail it over time. In this paper, a clustering ant colony algorithm with three immigrants schemes (K-ACS) is proposed to address the dynamic location routing problem (LRP). The LRP is divided into two parts constituted by a location allocation problem (LAP) and a vehicles routing problem (VRP) in dynamic environments. To deal with the LAP, a K-means clustering algorithm is used to tackle the location of depots and surrounding cities in each class. Then the ant colony algorithm with three immigrants including random immigrants, elitism-based immigrants and memory-based immigrants is utilized to handle the VRP in dynamic environments consisting of random and cyclic traﬃc factors. A comparative study is carried out to assess the eﬀect of the utilization of clustering. Experimental results based on diﬀerent scales of LRP instances demonstrate that the clustering algorithm can signiﬁcantly improve the performance of K-ACS in terms of the qualities and robustness of solutions. Furthermore, K-ACS show promising performance in solving the LRP in two diﬀerent dynamic environments, suggesting that the proposed algorithm may lead to a new technique for tracking the environmental changes by utilizing its clustering and evolutionary characteristics. Key words: Ant colony algorithm, clustering algorithm, immigrants schemes, location routing. 0 Introduction Ant colony optimization (ACO) algorithm is an intelligent bionic algorithm inspired by the foraging behavior of ant colony. It utilizes a special chemical substance called pheromone to communicate and exchange knowledge during individuals, and between individuals and the environment. Thus it can resolve various problems orderly via mutual cooperation. Ants judge and choose the path to move via sensing pheromone on the path, and this behavior has inspired people to create artiﬁcial ant systems to resolve combinatorial optimization problems and obtain approximately optimal solutions [1, 2]. The initial algorithm developed by Dorigo and Colorni, called ant system, was ﬁrst applied to travelling salesman problems (TSP) in 1991 [3,4]. However, it suﬀered from non-convergence and local optima problems. A majority of variants of ant system were proposed to tackle the static TSP eﬀectively, such as elitist ant system, max-min ant system, ant colony system, and so on [2]. Moreover, subsequent versions aimed to improve the performance of algorithms by introducing several novel mechanisms, such as the revision the transition rules to expand - 2 -

http://www.paper.edu.cn the space of random search, the utilization of a candidate list to store previous best solution, N -opt local random searches, etc [5]. On the other hand, the static TSP remaining under ﬁxed environment does not accord with numerous real-world problems. Most of these problems occur under dynamic environments, where the objective function, the problem instances or constraints change over time [6]. Therefore, when uncertain events take place, the optimum of the problem may change during the execution of the algorithm as well [7]. Specially, for the dynamic TSP, the purpose of algorithm is not to obtain the optimal solution anymore, but to attempt to track the optimal solution over time via knowledge of the previous search space. When useful knowledge can be transferred from the past, the algorithm needs to be suﬃciently ﬂexible to respond to the changes for accelerating the search. Under this consideration, the adaptability of algorithm is also a critical factor to enhance the eﬃciency of optimization [8]. ACO algorithm is a continuous adaptive algorithm since they can transfer useful infor- mation from past environment and adapt to dynamic changes. However, conventional ACO algorithm is prone to achieve the stagnation, because ants will follow the same path where the pheromone concentration is the highest once they ﬁnd the best routing [7]. This behavior can not meet the dynamic environment. A great deal of strategies for ACO algorithms are proposed to accomplish prospective results for resolving the dynamic TSP. For instance, the local and global restart strategies were ﬁrst introduced in [9]. Other eﬀective strategies can be summarized as: (1) diversity maintenance by immigrant schemes [7, 10]; (2) memory-based methods [11, 12]; (3) multiple population approaches [13, 14]; (4) clustering based algorithm- s [15, 16]; and (5) multi-strategy ensemble frameworks [17, 18]. The location routing problem (LRP) is a real-world problem relating to TSP. Unlike TSP which is a simple routing problem, the location of facilities in LRP not only aﬀects locational costs, but also has a major impact on routing costs. In fact, in these situations the overall problem is a multilevel locational and routing problem that should be addressed jointly, so a combined location-routing model is appropriate. The typical LRP was described by Laporte in 1986 [19]. To solve LRP, it is generally to ﬁnd solutions for its two sub-problems, i.e., a location allocation problem (LAP) and a vehicles routing problem (VRP). VRP is a known to be a NP- hard combinatorial optimization problem [20], which aims to ﬁnd a set of routes at a minimal cost (ﬁnding the shortest path, minimizing the number of vehicles, etc) beginning and ending the route at the depot, so that the known demand of all nodes are fulﬁlled. Nowadays, a large number of advanced meta-heuristic approaches such as tabu search [21] and simulated annealing [22] have been applied to the VRP. Meanwhile, ACO algorithm has also been used to address VRP with some strategies. In [23, 24], candidate lists and ranking techniques were introduced to reinforce the ability of ant colony for resolving the VRP. Multiple ant colonies with diﬀerent candidate lists were proposed to improve attainment of solution [25]. The variants of VRP such as capacitated VRP, VRP with time windows and dynamic VRP were studied with ACO by - 3 -

http://www.paper.edu.cn Rizzoli et al [26]. The dynamism in VRP is almost originated from the demand of commodities, services, travel time, or the requests of customers [27,28]. LRP is more complicated than VRP, thus requiring sophisticated algorithms to handle it especially in dynamic environments [29]. In this paper, a K-means clustering algorithm is introduced to combine with ACO algo- rithm for addressing the dynamic LRP. The resultant algorithm is thus called a clustering ant colony algorithm (K-ACS). To simulate the actual situation of LRP, dynamic environments consisting of random and cyclic traﬃc factors are applied. Random traﬃc factors are often referred to traﬃc delays caused by accidents, while cyclic factors represent those delays caused by the rush hours which are regular and cyclic in work days. K-ACS is a two-phase approach which oﬀers a computationally eﬃcient strategy that integrates facility location (i.e. LAP) and routing decisions (i.e. VRP), where the K-means is mainly deal with the LAP, and ACO manipulates the VRP. Like other diversity maintenance strategies [7, 10], K-ACS utilizes three kinds of immigrants schemes, i.e. random immigrant, elitism-based immigrant and memory- based immigrant to calculate the minimum cost of routing. These immigrants are generated randomly, constructed by the best ant from the previous environments and the memory respec- tively [7]. Besides, the K-means algorithm classiﬁes facilities (or cities) into certain classes in order to enable K-ACS to optimize the routing quickly and eﬀectively. The objective of the ant search in K-ACS is to quickly trail the minimum distance of optimal routes, depending on the number and loading capacities of vehicles, the number of clusters, or the requests of customers. Experiments are carried out based on instances adapted from those benchmark problems in TSPLIB. The proposed K-ACS with clustering are compared with an ACS without clustering for resolving the dynamic LRP. Simulation results indicate that clustering scheme can signiﬁ- cantly improve the performance of the algorithm for ﬁnding better solutions, and the immigrant strategies can enable the algorithm to be more ﬂexible so that adapt with the environmental changes well. Furthermore, the promising computational results for the dynamic LRP suggest that the same approach can be taken for other problems with changing environments. This rest of the paper is organized as follows. Section 1 introduces the concept of location routing problem and the constitution of dynamic environments. Section 2 presents a K-means clustering algorithm to locate the depots. Section 3 describes the conventional ACO algorithm and the proposed algorithm with three immigrants schemes. Section 4 shows the experimental results and analyzes the performance of algorithms with or without applying the clustering algorithm in diﬀerent dynamic environments. Finally, section 5 comes to a conclusion and gives some perspectives for future investigations. - 4 -

http://www.paper.edu.cn 图 1: The graphs of LAP, VRP and LRP. 1 Location routing problem Under the condition of certain constraints for LRP, the locations and number of depots as well as the best transportation route are determined by the objective function which is the minimum total distribution costs. The total costs include the cost of depot construction, the cost of transportation, the cost of vehicles and so on. Under normal circumstances, the LRP belonging to the planning problem of logistics system is seen as an integrated problem between LAP and VRP. This combinatorial optimization is also a NP-Hard problem, and the solution space increases exponentially with the expansion of the problem. Accordingly, the heuristic methods are utilized to resolve the LRP instead of the limited exact methods. 1.1 LAP For LAP, several depots are selected as the logistics distribution centers to accomplish the minimum total logistics costs when products are transported to a number of customers. In Fig.1(a), the transportation routes between depot and customers are divergent. The circular route is not considered in this method from point to point. In other words, each vehicle returns back directly after transporting commodities from the distribution center to customers. This approach is only applicable to the large volumes of commodities and the request of each customer exceeding the loading capacity of each vehicle. In actual distribution, the transportation cost will increase due to the limited loading capacities of vehicles. 1.2 VRP Vehicle routing problem was ﬁrst applied in the domain of logistics distribution in the early 1960s [30]. It is to ﬁnd the minimum distance or cost of the routes for several vehicles which return to the depot with certain capacity from a depot to a number of customers. - 5 -

http://www.paper.edu.cn Mathematically, G = (V, A, D), where V = {V0, V1, ..., Vn}, A = {(Vi, Vj) : i ̸= j} and D = {dij : i ̸= j} indicate the vertices, the edges and the distance respectively. qi represents the request of customer i, and Q is the capacity constraint of each vehicle. Moreover, the requests of customers can not exceed the capacity Q of each vehicle, i.e. max qi 6 Q. The VRP is a combinatorial optimization problem where the number of solutions increases exponentially with the number of customers serviced. In Fig.1(b), the transportation tour is considered to optimize routes and improve the utilization of the vehicles, but the distribution center is ﬁxed. The total logistics costs can not reach the minimum due to ignoring the location of distribution center. In real life, the scale of VRP is large. Although the exact algorithm can address it, lots of time will be taken. Thus, it can not meet the requirement of practical applications. In the meantime, the heuristic algorithms have been proposed to search for the space of subopti- mal solution. It signiﬁcantly reduces the search time and ﬁnds the suboptimal solution close to the practical requirement. Now, the well-known heuristics algorithms include simulated annealing, tabu search, artiﬁcial neural network, genetic algorithm and ant colony algorithm. In [31], [32–34], the genetic algorithms were used for the VRP. Reimann et al. proposed D-Ants algorithm for VRP [35]. The capacitated arc routing problem where the aim was to ﬁnd the minimum cost routes of a vehicle was solved by ant based algorithms [36]. The ﬁrst dynamic vehicle routing problem (DVRP) was proposed by Wilson and Colvin [37]. Montemanni et al. introduced ant colony system for DVRP [38]. Particle swarm optimization and variable neigh- bourhood search were used for DVRP [39]. There were various variants of VRP such as the capacitated VRP (CVRP) where customers had requests and vehicles had limited capacity, the VRP with time windows (VRPTW) where a speciﬁc time was given for visiting each customer, the Heterogeneous ﬂeet VRP (HVRP) where the capacities of vehicles were diﬀerent and so on [40]. In [5], a min-max MDVRP where the purpose was to minimize the total distance travelled by vehicles with the largest tours was optimized by an improved ant colony algorith- m. Adaptive large neighbourhood search [41] utilized numerous heuristic algorithms to tackle CVRP, CVRPTW etc. In [42], ant colony algorithm was used for solving multi-compartment VRP where k-means clustering algorithm improved the performance of the solution. 1.3 LRP The LRP has been mentioned above. The aim is to ﬁnd the total minimum cost with speciﬁc number and locations of depots and the optimal transportation routes according to the requests of customers. In Fig.1(c), both the capacities and number of depots and the optimal routes of vehicles are taken into account. It integrating the VRP and LAP has more complex constraints and is closer to reality. The LRP can be divided into three subproblems including location, demand allocation and vehicle routing. Laporte et al. introduced a random LRP - 6 -

http://www.paper.edu.cn where the request of each customer was known only when the vehicle reached [43]. Chien proposed a method using two diﬀerent estimated values to predict the length of routes for LRP [44]. Salhi and Fraser described an iterative method where an appropriate termination rule was found by exchanging information between location and arrangement of routes [45]. Robert Russell et al. adopted tabu search to resolve LRP with time windows [46]. Several LRPs with the boundary constraints such as capacity, the minimum cost and the maximum transportation length were studied in [43, 47]. A two-phase tabu search approach considering both facility location and vehicle routing was proposed to explore the solution space of the LRP eﬃciently [48]. A cluster analysis based sequential heuristic algorithm with hierarchical and non-hierarchical techniques and several proximity measures was presented to address the capacitated location-routing problem [49]. These methods are utilized to address the LRP well in static environment. However, the LRP in dynamic environments is one of the most challenging and complex problems. And a characteristic of the dynamic environments is that changes occur frequently over time. When the environment changes, it is likely that the search space alters and the new optimal solution is diﬀerent from the current solution. Thus, for dynamic LRP, the purpose is to track the optimal solution over time with the environmental changes. The dynamic environments consist of random and cyclic traﬃc factors. 1.3.1 LRP with random traﬃc factor Random traﬃc congestion indicates the distance between cities i and j changes randomly with the limited traﬃc factor over time. The expression is Dij = Dij × Tij, where Dij is the travelled distance between cities i and j, and Tij is the traﬃc factor between cities i and j. The traﬃc factor represents the condition of current traﬃc congestion between cities. Tij ∈ [TL, TH], where TL and TH denote the lower and upper bounds of traﬃc factor respectively. In each iteration of algorithm, Tij is generated randomly according to probability rules. TL generated with a higher probability indicates slight traﬃc congestion, and TL = 1 means no traﬃc. TH given with a higher probability illustrates serious traﬃc congestion. 1.3.2 LRP with cyclic traﬃc factor In the real world, the traﬃc usually represents cyclic pattern. In rush hours, the traﬃc congestion is severe. However, in the rest of time, the traﬃc keeps steady. Therefore, the cyclic traﬃc pattern corresponds better to the realistic traﬃc situation because the previous environment will appear again in the future. It is the hybrid of several traﬃc factors since it uses traﬃc factors to generate diﬀerent dynamic environments. In each dynamic environment, the traﬃc factors are generated with diﬀerent probabilities as the base states. The environment of each iteration is in these base states and changes cyclically. The generating method of cyclic - 7 -

http://www.paper.edu.cn traﬃc factors is the same as the random traﬃc factors, and TL and TH indicate the environments are in evening hours and rush hours respectively. In this paper, we assume that the capacity of each depot is inﬁnite and the request of each customer is met by a single vehicle whose capacity is certain. The number and requests of customers determine the number of vehicles. The depots and surrounding cities are constructed by the K-means algorithm described in section 2. In this way, we can obtain the total minimum cost based on the distance of the routes constructed by all the vehicles. 2 K-means algorithm K-means algorithm is a typical clustering method where the objective function is the sum of distance between data and clustering center, and the method of function extremum is used to adjust judgement rule during the iterations. The core idea is to divide a set of n data into diﬀerent k classes in order to minimize the objective function and implement the separate and compact classes as far as possible. In K-means algorithm, the metric of similarity is Euclidean distance. The initial clustering centers are classiﬁed optimally according to the minimum value of evaluating indicator Jc which ||p− mi||2 where Xi is the indicates the sum of error squares. It is deﬁned as:Jc = clustering center i, mi is the average value of the clustering center i and p is the data included in the clustering center i. The search of objective function is along the sum of error squares p2Xi k i=1 ∑ ∑ decreasing direction. The traditional K-means algorithm can resolve the clustering problems eﬀectively, but it depends on the k value. Improper k inﬂuences the actual eﬀect of the algorithm. Therefore, how to determine the k value is a signiﬁcant thing to consider. In this paper, the distance cost function F [50] is used to determine the k value. It is described as follow: k∑ F = i=1 k∑ ∑ p2Xi i=1 |mi − m| + |p − mi| (1) where m is the average value of all the data and other parameters deﬁned are the same as Jc. When the F is minimum, the clustering result is the best. And the k is obtained according to the minimum F . Besides the function F , the upper bound of k is deﬁned as k 6 √ n [51], where n is the scale of the problem. This method can reduce the search range of optimal k. The K-means algorithm based on the distance cost function can quickly implement the optimal k due to the simple structure and low computational complexity. This kind of K-means algorithm is shown in Algorithm 1. Through classiﬁcation of this algorithm to establish several depots and nearby cities, the ant colony optimization introduced in section 3 can implement better performance of resolving the VRP with dynamic environments. - 8 -

分享到：

赞收藏

资料库

论文研究-Ant colony optimization with clustering for solving the dyn....pdf

相关推荐

开发技术

热门标签

最新资料