روش بهینه سازی کلونی مورچه ها برای حل مساله مسیریابی خودرو مینیمم - ماکزیمم چندانباری

The Multi-Depot Vehicle Routing Problem (MDVRP) involves minimizing the total distance traveled by vehicles originating from multiple depots so that the vehicles together visit the specified customer locations (or cities) exactly once. This problem belongs to a class of Nondeterministic Polynomial Hard (NP Hard) problems and has been used in literature as a benchmark for development of optimization schemes. This article deals with a variant of MDVRP, called min–max MDVRP, where the objective is to minimize the tour-length of the vehicle traveling the longest distance in MDVRP. Markedly different from the traditional MDVRP, min–max MDVRP is of specific significance for time-critical applications such as emergency response, where one wants to minimize the time taken to attend any customer. This article presents an extension of an existing ant-colony technique for solving the Single Depot Vehicle Routing Problem (SDVRP) to solve the multiple depots and min–max variants of the problem. First, the article presents the algorithm that solves the min–max version of SDVRP. Then, the article extends the algorithm for min–max MDVRP using an equitable region partitioning approach aimed at assigning customer locations to depots so that MDVRP is reduced to multiple SDVRPs. The proposed method has been implemented in MATLAB for obtaining the solution for the min–max MDVRP with any number of vehicles and customer locations. A comparative study is carried out to evaluate the proposed algorithm's performance with respect to a currently available Linear Programming (LP) based algorithm in literature in terms of the optimality of solution. Based on simulation studies and statistical evaluations, it has been demonstrated that the ant colony optimization technique proposed in this article leads to more optimal results as compared to the existing LP based method.

Transportation of goods at various levels including within a city, region, nation, or around the globe is an essential part of modern supply chains. The efficient transportation of goods holds immense value due to its high impact on cost and customer satisfaction by reducing energy consumption and speedy delivery. In the last decade, research [1] suggested that 10–15% of the traded goods corresponded to the transportation costs. Also, U.S. Bureau of Labor Statistics estimates that transportation-related fields are growing by nearly 56,000 jobs a year, thus showing an increase in trade and logistic businesses [2]. Realizing the importance of this factor, researchers have devoted a lot of effort in finding novel and optimal ways for efficient transportation. According to Toth and Vigo [1], utilization of computational tools for transportation route optimization has a potential to result in significant cost savings ranging from 5% to 20%. A well-known problem in this field, which has emerged as a benchmark optimization problem during the past few decades, is the Single Depot Vehicle Routing Problem (SDVRP). It is an extension of the classical Traveling Salesman Problem [3] in which one vehicle originates from a common depot to visit a set of customer locations with the objective of minimizing the total tour length. The goal in the SDVRP, on the other hand, is to minimize the total distance traveled by all the vehicles while meeting customer demands and vehicle constraints, e.g., maximum travel distance or vehicle capacity. SDVRP, or simply, VRP as commonly referred, was first proposed in 1959 by Dantzig [4]. Since then, it has been studied extensively and serves as one of the benchmark problems in the field of optimization. Just like TSP, VRP is known to be a computationally Nondeterministic Polynomial Hard (NP Hard) Problem [5] and [6]. Multi-Depot Vehicle Routing Problem (MDVRP) extends the SDVRP by having multiple depots where multiple vehicles can originate from. MDVRP can be traced back to 1976 when Gillet and Johnson published a paper on Multi Terminal Vehicle-Dispatch Algorithm [7]. In this paper, a heuristic algorithm was developed to obtain an approximate solution. Their objective was to determine a set of vehicle routes that originate in two or more depots, visit the collection of demand points and return to the depots, such that the total distance traveled was minimized. They employed a sweep algorithm which was based on a strategy to break the problem to single-terminal problem in order to significantly reduce the computational time. The solution was also extended to satisfy some of the constraints such as the vehicle capacity and the length of each route. After this paper, much effort has been dedicated by researchers around the globe and many have come up with different methods to solve this problem [8], [9], [10] and [11]. In 2005, Lim and Wang [12] proposed a more practical variant of this problem and it was named MDVRP with Fixed Distribution of vehicles (MDVRPFD). They proposed this problem with bounds on the number of vehicles in a depot unlike the traditional MDVRP where the limit was unrealizable infinite number of vehicles. With an assumption of exactly one vehicle in each depot, they developed a binary programming technique to obtain the solution and generalized the solution for any number of vehicles in a depot. More importantly, they proposed a new one-stage approach where the assignment of customers to the depots and the route calculations were carried out in a single stage. This paper focuses on an interesting variant of the MDVRP called the min–max Multi-Depot Vehicle Routing Problem (min–max MDVRP). The objective of this problem is to minimize the maximum distance traveled by any vehicle instead of the total distance traveled which is the case in the conventional MDVRP. Clearly, similar to the manner in which the min–max SDVRP is different from the traditional SDVRP [13], the min–max MDVRP is fundamentally different from the traditional MDVRP. In the min–max MDVRP, an optimal solution makes use of all available vehicles in an attempt to reduce the distance traveled by those vehicles with the largest tours, and this leads to more equitable sharing of loads between the vehicles. This problem is often of interest when minimization of time taken to visit all points is more important than the total distance traveled. The application includes emergency management situations where the objective is to use all available vehicles to minimize the time taken to attend to all points needing emergency resources. The optimization of vehicle routes for emergency management and relief efforts [14] has been a topic of much interest recently, and different versions of vehicle routing problems have been formulated in literature motivated from issues in emergency management including the min–max VRP [15], average cost VRP [15], and last mile distribution [16]. Other applications of this problem are in defense and computer networking. For example, assigning tours to a group of Unmanned Aerial Vehicles (UAVs) engaged in large scale surveillance operation by solving min–max problem will minimize the maximum time of travel of UAVs, and hence help achieve desired objectives in time-critical scenarios. In computer networking, depots represent servers, vehicles represent data packets, and customers represent clients. In this problem, a network routing topology generated by solving the min–max problem would result in minimizing the maximum latency between any pair of server and a client. One of the first attempts to solve the min–max class of problems was by Gold et al. in [13] where they proposed a method based on Tabu search and adaptive memory heuristic. Using several test cases, they showed that their method provided good quality solutions within reasonable computational time. However, they considered just the single depot problem. The min–max problem for the multiple depots case was first formulated in 2007 by Carlsson et al. [17]. Carlsson's work, being one of the most widely accepted works in literature, is used in this paper for comparison purposes. In their paper, Carlsson et al. [17] performed a theoretical analysis by developing an asymptotic bound for the longest tour length L and concluded that the optimal solution to min–max MDVRP with uniformly distributed n points would numerically approach a value proportional to View the MathML sourcen/k, which is the value of optimal TSP tour of all customers split by number of vehicles ‘k’, under the constraint. Additionally, they developed two different heuristics to solve the min–max MDVRP. The first heuristic was a load-balancing technique based on Linear Programming, while the second heuristic is the region partition based method. In the second technique, noticing that a convex equitable partitioning of the region yields an even division of points, they divided the service region into a set of sub-regions with equal area and generated good initial solutions by assigning the customer points in the depot region to the respective depot. Other recent works on min–max VRP include [15] that uses insertion heuristics, [18] that uses hybrid Genetic Algorithm and Tabu search heuristic, and [19] that uses the branch-and-bound method. However, all of these works pertain to the single depot version of min–max VRP. For min–max MDVRP, Carlsson's method remains to be the most widely accepted method in literature to the best of the authors' knowledge and hence has been used in this paper as a benchmark method for comparison purposes. The swarm intelligence technique, called ant colony optimization (ACO), based on the foraging strategies of ants, was first applied to TSP in [19], [20], [21] and [22]. The basic idea underlying this ant based algorithm is to use a positive feedback mechanism, based on an analogy with the pheromone-laying, pheromone-following behavior of some species of ants and some other social insects, and to reinforce those portions of good solutions that contribute to the quality of these solutions. The initial algorithm developed by Dorigo and Colorni [20], called ant system, suffered from problems including non-convergence and local minima. Subsequent versions of the algorithm [21] and [22] introduced several mechanisms such as modified transition rules that promoted directed random search, use of candidate list, new pheromone update rule that promoted exploration of solution space, and local random searches such as 1-opt and 2-opt techniques. There are several features of ant based algorithms that make them ideal for the combinatorial optimization problems such as the one considered in this paper. The unique mechanism of laying pheromones provides a positive feedback that exploits the global knowledge by reinforcing the good solutions and directs the search to solutions of good potential. Furthermore, mechanisms, such as the transition rule, introduce stochastic components that allow the algorithm to explore the environment and escape local minima situations. Since the algorithm involves simple rules of each ant with decentralized control where each ant makes its own decision, this technique is computationally efficient and fairly easy to implement. More importantly, the agent-based framework allows parallelization or distribution of a lot of computations, and hence provides a scalable mechanism to solve NP Hard problems such as the TSP and MDVRP. Motivated by the above features, ant based algorithms have been applied to solve a number of combinatorial optimization problems including Job Scheduling Problem [23], Graph Coloring Problem [24], Quadratic Assignment Problem [25], School Bus Routing Problem [26], and SDVRP [27]. Of particular interest to the problem considered in this paper is the application of ant based algorithms to SDVRP. For example, in [27], a hybrid ant system algorithm was presented that utilized information such as savings and capacity utilization to obtain the solution. In 2004, Bell et al. [28] developed multiple ant colony methods to solve the vehicle routing problem. This method uses separate specialized ant groups with unique pheromone depositions for each vehicle to solve the VRP. This separation is intended to differentiate paths typically used in the route of the first vehicle from those used by subsequent vehicles. This technique is found to be more useful when the size of the problem, i.e., the number of cities and/or the number of vehicles, is large. Also, their paper reinstates the route improvement strategies such as 2-opt heuristic and candidate list technique which were initially proposed by Bullnheimer et al. [27]. In [29], Rizzoli et al. studied ACO application to variants of VRP such as Capacitated VRP, VRP with Time Windows, Time Dependent VRP and Dynamic VRP. They showed the application of ACO to industry size problems for a super market chain in Switzerland and Pick-up and Delivery problem for an industry in Italy. In [30], the authors provide a number of applications of the ACO algorithm for practical business problems including call routing in telecommunication network, minimizing delays in internet traffic, routing of fleet of oil trucks, factory efficiency, and business idea management. In [31], Reimann et al. proposed D-Ants algorithm that improved the ant systems algorithm for VRP via decomposition of the problem into several disjoint sub-problems and showed its applications to variants such as VRP with Time Window, VRP with Backhauls, and VRP with Backhauls and Time Windows. Ant based algorithms [32] have also been applied to an interesting variant of VRP called Capacitated Arc Routing Problem [33] (CARP) where the objective is to determine minimum cost routes of a vehicle that is required to service demands located along routes (edges of the networks). The ant based methods [32] have been demonstrated to perform extremely well as compared to the state-of-the-art meta-heuristics for the CARP. This article, based on the M.Sc. thesis work by the first author [34], proposes an ant colony based algorithm to solve the min–max MDVRP. To the best of the authors' knowledge, this is the first application of ant colony optimization method to solve this important class of problem. The algorithm is inspired by the algorithm developed in [27] to solve the traditional SDVRP. This article extends the algorithm developed in [27] in two ways. Firstly, it argues that minimization of the “distance constraint” used in [27] will lead to the solution of the min–max variant of SDVRP, and provides an algorithm to carry out the minimization. Secondly, it uses region partitioning technique to extend the min–max SDVRP to solve the min–max MDVRP. The paper is organized as follows. First, a mathematical formulation of the min–max MDVRP is presented. Then, the proposed ant colony approach to solve the min–max SDVRP is presented. This is followed by the extension of that approach to solve the min–max MDVRP using region partitioning technique. Next, the results from simulation studies are presented and compared with respect to the best known methods in literature to solve this class of problems. The paper ends with some conclusions and suggestions for future work.

The paper presents an approximate solution to the min–max MDVRP based on an ant colony optimization. Unlike the traditional MDVRP, which minimizes the total distance traveled, the min–max MDVRP minimizes the maximal distance traveled by a vehicle. This variant of the problem holds special relevance for time-critical problems. The approach is based on decomposing the overall problem into several min–max SDVRPs via equitable partitioning of the region consisting of depots and cities. The min–max SDVRP is then solved using the ant colony method that finds out the minimum value of distance constraint that yields a solution to the traditional SDVRP. This optimal distance constraint, when used in a traditional SDVRP, minimizes the maximal distance traveled by a vehicle. Simulation studies and statistical tests validate the effectiveness of the proposed method and demonstrate that the proposed approach provides improvements in terms of optimality of the solution as compared to one of the best known methods in literature. Furthermore, the proposed ant colony based method provides much consistent solution over different runs showing convergence of the solution to a small neighborhood. Future work includes developing region-partitioning techniques for cases where we have non-uniform distribution or smaller number of cities. Further attempt should be made to implement the inherently distributed ant colony based method in a parallel computing framework, thus fully utilizing its potential. Additionally, an evaluation of the performance of various local search algorithms to complement the proposed ant based method for the min–max MDVRP would be an interesting direction for future work.