A Study of Greedy, Local Search, and Ant Colony Optimization Approaches for Car Sequencing Problems
| Autor: | Jens Gottlieb, Markus Puchta, Christine Solnon |
|---|---|
| Přispěvatelé: | SAP Research (SAP Research), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2) |
| Rok vydání: | 2003 |
| Předmět: |
Mathematical optimization
021103 operations research Computer science business.industry Heuristic Heuristic (computer science) Ant colony optimization algorithms 0211 other engineering and technologies Evolutionary algorithm 02 engineering and technology 0202 electrical engineering electronic engineering information engineering Benchmark (computing) [INFO]Computer Science [cs] 020201 artificial intelligence & image processing Local search (optimization) Greedy algorithm Heuristics business Greedy randomized adaptive search procedure |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783540009764 EvoWorkshops Applications of Evolutionary Computing EvoWorkshops: Workshops on Applications of Evolutionary Computation EvoWorkshops: Workshops on Applications of Evolutionary Computation, Apr 2003, Essex, United Kingdom. ⟨10.1007/3-540-36605-9_23⟩ Web of Science |
| DOI: | 10.1007/3-540-36605-9_23 |
| Popis: | International audience; This paper describes and compares several heuristic approaches for the car sequencing problem. We first study greedy heuristics, and show that dynamic ones clearly outperform their static counterparts. We then describe local search and ant colony optimization (ACO) approaches, that both integrate greedy heuristics, and experimentally compare them on benchmark instances. ACO yields the best solution quality for smaller time limits, and it is comparable to local search for larger limits. Our best algorithms proved one instance being feasible, for which it was formerly unknown whether it is satisfiable or not. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|