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 routines like CROSS and 3-opt, which resulted in no meaningful value and higher computation time. Since the problem contains contradicting objectives, using specific to artificially help the algorithm in finding better solutions is harmful and reduces the effectiveness of the algorithm.In order to evaluate the performance of proposed algorithm optimization engine, a comprehensive experiment is conducted on a set of standard problem available in the literature. In this experiment we have used the (CMT) 14 standard VRP benchmark instances. These problems contain 50 to 199 cities in addition to depot. Our intention was to demonstrate the capability of proposed algorithm on classical VRP for which enormous research and experiments has been done. The performance of proposed algorithm is compared with several best known advanced heuristic algorithms. The average deviation of proposed algorithm results from the best known solutions is 0.55 percent. In three instances, it provides the best known solutions. This experiment shows that the proposed algorithm can provide comparable results with sophisticated TS algorithm for classical VRP. Since the proposed algorithm is deigned for real complex problems, we believe that it can easily attain higher quality solutions than algorithms which are designed and tested for standard problems. Most of available algorithms are quite specific and need special modification for more complex cases.The computation time of algorithms can not be compared directly, since they have run on different machines. Its average run time for the proposed algorithm on CMT set is 0.5 minutes, which is also an outstanding performance. This experiments shows that the proposed algorithm can provide high quality results comparing to the leading edge heuristic algorithms.