A TABU SEARCH ALGORITHM FOR VEHICLE ROUTING AND SCHEDULING PROBLEM

Q: How can I download an article?

To download an article from SID, first log in to the site, search for the article title, and click on the 'Download Article' option.

Q: How can I download an ISI article?

To download an ISI article on SID, enter the keyword or article title in the search bar, view the relevant results, click on the desired article, and select the 'Download Article' option.

Q: How can I access the SID database?

To access the SID database, visit SID.ir, create an account, and log in to access scientific resources.

Q: Is downloading articles from SID free?

Some articles on SID are available for free, while others require payment. Details are specified on the article's page.

MODARES A.A.H.

Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Journal Paper

Paper Information

Journal: JOURNAL OF TRANSPORTATION RESEARCH Year:2010 | Volume:6 | Issue:4 (21) Page(s): 351-365

Download Full-Text

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Persian Verion

View:

2,054

Download:

Cites:

Information Journal Paper

Title

A TABU SEARCH ALGORITHM FOR VEHICLE ROUTING AND SCHEDULING PROBLEM

Author(s)

MODARES A.A.H. | Issue Writer Certificate

Keywords

TABU SEARCHQ3

TRANSPORTATIONQ3

SUPPLY CHAINQ2

VEHICLE ROUTING AND SCHEDULING PROBLEMQ3

Abstract

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 have 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 designed 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.

Cites

COMPARISON OF PARTICLE SWARM OPTIMIZATION AND TABU SEARCH ALGORITHMS FOR PORTFOLIO SELECTION PROBLEM

References

No record.

Cite

APA: Copy

MODARES, A.A.H.. (2010). A TABU SEARCH ALGORITHM FOR VEHICLE ROUTING AND SCHEDULING PROBLEM. JOURNAL OF TRANSPORTATION RESEARCH, 6(4 (21)), 351-365. SID. https://sid.ir/paper/83818/en

Vancouver: Copy

MODARES A.A.H.. A TABU SEARCH ALGORITHM FOR VEHICLE ROUTING AND SCHEDULING PROBLEM. JOURNAL OF TRANSPORTATION RESEARCH[Internet]. 2010;6(4 (21)):351-365. Available from: https://sid.ir/paper/83818/en

IEEE: Copy

A.A.H. MODARES, “A TABU SEARCH ALGORITHM FOR VEHICLE ROUTING AND SCHEDULING PROBLEM,” JOURNAL OF TRANSPORTATION RESEARCH, vol. 6, no. 4 (21), pp. 351–365, 2010, [Online]. Available: https://sid.ir/paper/83818/en

Related Journal Papers