بهينه سازي مسيريابي دربرنامه ريزي توزيع با استفاده از الگوريتم جستجوي ممنوع

A Tabu Search Algorithm for Vehicle Routing and Scheduling Problem

The most important operational decision related to transportation in the supply chain planning is the routing and scheduling of deliveries. Vehicle Routing and Scheduling Problem (VRSP) is a significant task in both supply chain planning and distribution optimization. A very large body of research and modeling literature has been devoted to address VRSP. But most of them concentrated on hypothetical or simplified problems and disregarded many practical aspects of such problems. On the other hand, many practical problems have been tackled by different commercial systems for this class of problems, but little has been published about them. The primary objective of this paper is to develop a flexible algorithm for solving complex real VRSP arises in practice. VRSP can be simply defined as: planning efficient flow of goods between facilities by a fleet of carriers through the transportation networks. This statement reveals the main components or objects of VRSP problems, namely, goods, facilities, carriers and transportation networks. Each object may have its owners, who impose their objectives and restrictions to the problem. For example, drivers may be considered as the owners of vehicles who may impose working time or region constraints. In developing the algorithm, the most important criteria have been flexibility and speed. Most of new algorithms developed by researchers are problem specific. They might improve the quality of results at the expense of reducing the flexibility of algorithm to handle new constraints or increasing its computation time. Among various families of heuristics for optimization problems, Tabu Search (TS), Genetic Algorithms (GA) and Simulated Annealing (SA) have shown promising performance to solve various combinatorial problems. TS has several features which make it suitable candidate for real life complex cases. Robustness, simplicity and flexibility are the most important features of TS. In our experiences, the flexibility of GA is questionable and SA needs complicated parameter adjustment to gain high quality results. Therefore, we selected TS as framework for developing optimization algorithm. In TS algorithm , during the search process, current solution may deteriorate from one iteration to the next. To avoid cycling, recent explored solutions are temporarily declared forbidden by putting their selected attributes in the Tabu list. The TS algorithm has been evolved over time and several innovative features are included in this algorithm by researchers to enhance its performance. In the proposed algorithm , a cheapest insertion routine has been used for building initial solution. Neighborhood structure is another component which heavily influences the behavior of the algorithm. In order to improve the quality of solution or speed up the algorithm, numerous enhanced neighborhood structures have been proposed by researchers. Practical experiments show that a combination of relocation, exchange and 2opt* can provide high quality results within low computational time. We have examined more complex routins like CROSS and 3-opt, which resulted in no meaningful value and higher computation time.