Mathematical formulation of tabu search in combinatorial optimization
The Capacitated Arc Routing Problem (CARP) is a fundamental and well-known routing problem. This is a special form of arc routing problem which involves determining a fleet of homogeneous size vehicles and designing the routes to minimize the total cost. It is considered as CARP when the demands are...
| Main Author: | |
|---|---|
| Format: | Monograph |
| Language: | English |
| Published: |
Faculty of Sciences
2008
|
| Subjects: | |
| Online Access: | http://eprints.utm.my/9733/ http://eprints.utm.my/9733/1/78146.pdf |
| _version_ | 1848891925137981440 |
|---|---|
| author | Ismail, Zuhaimy |
| author_facet | Ismail, Zuhaimy |
| author_sort | Ismail, Zuhaimy |
| building | UTeM Institutional Repository |
| collection | Online Access |
| description | The Capacitated Arc Routing Problem (CARP) is a fundamental and well-known routing problem. This is a special form of arc routing problem which involves determining a fleet of homogeneous size vehicles and designing the routes to minimize the total cost. It is considered as CARP when the demands are located along the edges. One such problem is in the designing a tour for waste collection vehicle where each vehicle is limited in its capacity. CARP is known to be Non-deterministic Polynomialtime hard (NP-hard) where solutions are obtained through heuristic methods. Tabu Search (TS) is a heuristic method based on the use of prohibition-based techniques and basic heuristics algorithms like local search. The main advantage of TS with respect to other conventional search is in the intelligent use of past history of the search to influence its future search procedures. This study is to develop Reactive Tabu Search (RTS) heuristics for solving CARP. Our RTS algorithm allows for dynamic tabu list rather than static tabu list as being practiced in TS algorithm. The test instances involve five to 50 nodes systematically generated similar to the real world CARP. The newly modified RTS algorithm gives a better performance than TS and (Look-Ahead Strategy) LAS method. |
| first_indexed | 2025-11-15T21:05:42Z |
| format | Monograph |
| id | utm-9733 |
| institution | Universiti Teknologi Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T21:05:42Z |
| publishDate | 2008 |
| publisher | Faculty of Sciences |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | utm-97332017-08-15T03:25:47Z http://eprints.utm.my/9733/ Mathematical formulation of tabu search in combinatorial optimization Ismail, Zuhaimy Q Science (General) The Capacitated Arc Routing Problem (CARP) is a fundamental and well-known routing problem. This is a special form of arc routing problem which involves determining a fleet of homogeneous size vehicles and designing the routes to minimize the total cost. It is considered as CARP when the demands are located along the edges. One such problem is in the designing a tour for waste collection vehicle where each vehicle is limited in its capacity. CARP is known to be Non-deterministic Polynomialtime hard (NP-hard) where solutions are obtained through heuristic methods. Tabu Search (TS) is a heuristic method based on the use of prohibition-based techniques and basic heuristics algorithms like local search. The main advantage of TS with respect to other conventional search is in the intelligent use of past history of the search to influence its future search procedures. This study is to develop Reactive Tabu Search (RTS) heuristics for solving CARP. Our RTS algorithm allows for dynamic tabu list rather than static tabu list as being practiced in TS algorithm. The test instances involve five to 50 nodes systematically generated similar to the real world CARP. The newly modified RTS algorithm gives a better performance than TS and (Look-Ahead Strategy) LAS method. Faculty of Sciences 2008-09-27 Monograph NonPeerReviewed application/pdf en http://eprints.utm.my/9733/1/78146.pdf Ismail, Zuhaimy (2008) Mathematical formulation of tabu search in combinatorial optimization. Project Report. Faculty of Sciences, Skudai, Johor. (Unpublished) |
| spellingShingle | Q Science (General) Ismail, Zuhaimy Mathematical formulation of tabu search in combinatorial optimization |
| title | Mathematical formulation of tabu search in combinatorial optimization |
| title_full | Mathematical formulation of tabu search in combinatorial optimization |
| title_fullStr | Mathematical formulation of tabu search in combinatorial optimization |
| title_full_unstemmed | Mathematical formulation of tabu search in combinatorial optimization |
| title_short | Mathematical formulation of tabu search in combinatorial optimization |
| title_sort | mathematical formulation of tabu search in combinatorial optimization |
| topic | Q Science (General) |
| url | http://eprints.utm.my/9733/ http://eprints.utm.my/9733/1/78146.pdf |