حل مشکل خودرو مسیریابی با استفاده از روش برنامه ریزی حافظه تطبیقی

In this paper we develop an adaptive memory programming method for solving the capacitated vehicle routing problem called Solutions’ Elite PArts Search (SEPAS). This iterative method, first generates initial solutions via a systematic diversification technique and stores their routes in an adaptive memory. Subsequently, a constructive heuristic merges route components (called elite parts) from those in the adaptive memory. Finally, a tabu search approach improves the heuristically constructed solution and the adaptive memory is appropriately updated. SEPAS has been tested on two benchmark data sets and provides high quality solutions in short computational times for all problem instances. The method reaches several new best solutions for benchmark instances with a large number of customers.

The vehicle routing problem (VRP) [1] and [2] is a focal problem of distribution management within the area of service operations management and logistics. The capacitated vehicle routing problem (CVRP) constitutes the classical version of the VRP and can be formally defined as follows: let G=(V,E) be an undirected graph where V={u0,u1,…,un} is a vertex set and View the MathML source is an edge set. Vertex u0 represents the depot of a homogeneous fleet of m vehicles, each of capacity Q. The remaining vertices of V correspond to customers. Each customer has a non-negative demand qi and a service time si. A non-negative cost (distance or travel time) matrix C=[cij] is defined on E. The number of vehicles is either predetermined or is treated as a decision variable. The CVRP consists of designing a set of m delivery or collection routes such that: (a) the total routing cost is minimized, (b) each route starts and ends at the depot, (c) each customer is visited exactly once by exactly one vehicle, and (d) the total demand of any route does not exceed Q. The CVRP is an NP-hard combinatorial problem. As Toth and Vigo [3] report, no exact algorithm is capable of consistently solving CVRP-instances with more than 50 customers; thus, heuristics are mainly employed for real-life medium and large scale vehicle routing problems. Heuristics can be divided into two classes [4]: classical heuristics that perform relatively limited exploration of the search space to produce good solutions fast, and meta-heuristics that are general-purpose mechanisms guiding intelligently the search process, combining neighbourhood search rules, memory structures and recombination of solutions. The adaptive memory (AM) rationale was introduced by Rochat and Taillard [5]. According to this, an AM (i.e., a special data structure populated by a set of solutions, which can keep track of the “best” components of the solutions visited during the search), is initialized. Subsequently, a provisional solution is created by combining the “best” components of the solutions within the AM. The provisional solution is then improved via a local search algorithm and updates the AM. As Hertz and Kobler explain [6], search diversification is achieved in the initial steps of the AM procedure, when new solutions are created by combining different components of the solutions in the AM. However, as the procedure evolves, the search gradually intensifies since the components of the AM tend to belong to a very small set of solutions from a limited number of regions of the search space. The AM procedure shares many common principles and characteristics with other methods such as the memetic algorithm of Moscato and Cotta [7], the greedy randomized adaptive search procedure of Resende and Ribeiro [8], the hybrid ant system of Gambardella et al. [9] and the scatter search of Laguna [10]. This led to the development of the overall adaptive memory programming (AMP) approach, introduced by Taillard et al. [11] for unifying all such metaheuristics. To our knowledge, only two pure AMP algorithms for solving the CVRP have been presented to-date: the “probabilistic and intensification in local search” of Rochat and Taillard [5] and the BoneRoute method of Tarantilis and Kiranoudis [12]. In this paper we develop an AMP method for solving the CVRP called Solutions’ Elite PArts Search (SEPAS). This iterative method, first generates initial solutions via a systematic diversification technique and stores their routes in an adaptive memory. Subsequently, a constructive heuristic merges route components (called elite parts) from those in the adaptive memory. Finally, a tabu search approach improves the heuristically constructed solution and the adaptive memory is appropriately updated. SEPAS has been tested on two benchmark data sets and provides high quality solutions in short computational times for all problem instances. The remainder of the paper is organised as follows: in Section 2 SEPAS is developed for solving the CVRP and its special characteristics are provided in detail. Section 3 presents the computational results of the algorithm on the well-known benchmark instances of Christofides et al. [13] and on the large scale VRPs of Golden et al. [14]. The paper concludes in Section 4, where further research avenues are also identified.

This paper presented a new metaheuristic, called solutions’ elite parts search (SEPAS), to solve the capacitated vehicle routing problem (CVRP). Our approach, which is based upon the adaptive memory programming framework, produces a new solution out of parts of routes, called elite parts, of a set of solutions. SEPAS initially generates a population of diversified solutions in a systematic (not stochastic) way, and uses a constructive heuristic to complete the partial solutions composed by the elite parts; it finally employs a sophisticated tabu search to further improve the performance of the complete solution. SEPAS performs very well on two well-known sets of benchmark problems from the literature, providing high quality solutions with respect to the route cost, within reasonable computational times. The results presented indicate that SEPAS reaches several new best solutions for a large number of benchmark problems. Comparisons with other metaheuristics show that SEPAS is one of the most successful methods ever developed to solve the CVRP, yielding average deviations of less than 0.2% from the best-known solutions. In terms of future research directions, SEPAS can be easily applied to several variants of the VRP, such as the VRP with Time Windows, the VRP with Backhauls, the VRP with Heterogeneous Fleet or combination of them. Finally, given the structure of SEPAS, it is well-adapted for parallel implementation which could further reduce computation time.