Splitting algorithms for the multiple depot arc routing problem: application by ant colony optimization
Fuente:
Redalyc
Saved in:
| Main Author: | |
|---|---|
| Format: | Artículo científico |
| Language: | en |
| Published: |
International Journal of Combinatorial Optimization Problems and Informatics
2012
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1876472508454010880 |
|---|---|
| author | Ali Kansou |
| author_facet | Ali Kansou |
| contents | Splitting algorithms for the multiple depot arc routing problem: application by ant colony optimization Ali Kansou Adnan Yassine Computación MDCARP problem insertion heuristic ant colony optimization Capacitated arc routing problem This paper handles the Capacitated Arc Routing Problem with Multiple Depots (MDCARP). The well known CARP problem consists of designing a set of vehicle trips, so that each vehicle starts and ends at the single depot. The MDCARP on a mixed graph involves the assignment of tasks (arcs and edges), which have to be served, to depots and the determination of vehicle trips for each depot. The MDCARP is NPhard, to resolve it efficiently, two ant colony approaches are developed. The first proposed work is based on ant colony optimization (ACO) combined with an insertion heuristic: the ACO is used to optimize the order of insertion of the tasks, and the heuristic is devoted to inserting each task in the solution. A generalization for the splitting method of Ulusoy is incorporated with the ant colony optimization in the second approach. Computational results on benchmark instances show the good quality of the proposed methods and the superiority of the first algorithm compared to the second method on the large instances. Another experimental results of instances with known optima suggest the performance of the two methods is significantly better than the methods of literature. 2012 artículo científico 2007-1558 https://www.redalyc.org/articulo.oa?id=265224452002 en http://www.redalyc.org/revista.oa?id=2652 International Journal of Combinatorial Optimization Problems and Informatics application/pdf International Journal of Combinatorial Optimization Problems and Informatics International Journal of Combinatorial Optimization Problems and Informatics (México) Num.3 Vol.3 |
| format | Artículo científico |
| id | redalyc_265224452002 |
| institution | Redalyc |
| language | en |
| publishDate | 2012 |
| publisher | International Journal of Combinatorial Optimization Problems and Informatics |
| spellingShingle | Splitting algorithms for the multiple depot arc routing problem: application by ant colony optimization Ali Kansou Computación MDCARP problem insertion heuristic ant colony optimization Capacitated arc routing problem Splitting algorithms for the multiple depot arc routing problem: application by ant colony optimization Ali Kansou Adnan Yassine Computación MDCARP problem insertion heuristic ant colony optimization Capacitated arc routing problem This paper handles the Capacitated Arc Routing Problem with Multiple Depots (MDCARP). The well known CARP problem consists of designing a set of vehicle trips, so that each vehicle starts and ends at the single depot. The MDCARP on a mixed graph involves the assignment of tasks (arcs and edges), which have to be served, to depots and the determination of vehicle trips for each depot. The MDCARP is NPhard, to resolve it efficiently, two ant colony approaches are developed. The first proposed work is based on ant colony optimization (ACO) combined with an insertion heuristic: the ACO is used to optimize the order of insertion of the tasks, and the heuristic is devoted to inserting each task in the solution. A generalization for the splitting method of Ulusoy is incorporated with the ant colony optimization in the second approach. Computational results on benchmark instances show the good quality of the proposed methods and the superiority of the first algorithm compared to the second method on the large instances. Another experimental results of instances with known optima suggest the performance of the two methods is significantly better than the methods of literature. 2012 artículo científico 2007-1558 https://www.redalyc.org/articulo.oa?id=265224452002 en http://www.redalyc.org/revista.oa?id=2652 International Journal of Combinatorial Optimization Problems and Informatics application/pdf International Journal of Combinatorial Optimization Problems and Informatics International Journal of Combinatorial Optimization Problems and Informatics (México) Num.3 Vol.3 |
| title | Splitting algorithms for the multiple depot arc routing problem: application by ant colony optimization |
| topic | Computación MDCARP problem insertion heuristic ant colony optimization Capacitated arc routing problem |
| url | https://www.redalyc.org/articulo.oa?id=265224452002 |