The Ant System and its Application to Combinatorial Optimization Problems
- Autor(en)
- Bernd Bullnheimer, Christine Strauss
- Abstrakt
The Ant System is a new Meta-Heuristic which can be used to solve hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search and has been successfully applied to the traveling salesman problem (TSP), the quadratic assignment problem (QAP), the job-shop scheduling problem and also the graph coloring problem. In this paper we use the Ant System to solve the vehicle routing problem in its basic form, i.e. with capacity and route length restrictions, one central depot and identical vehicles. First, we adapt the TSP-Ant System so it can be applied to the VRP and then we show, that a hybridization using the 2-opt-algorithm can be used to reduce the length of the tours found for several benchmark problems from literature. Finally, we show that the introduction of additional parameters which guide the greedy search, leads to even better results.
- Organisation(en)
- Institut für Marketing und International Business
- Publikationsdatum
- 1997
- Peer-reviewed
- Ja
- ÖFOS 2012
- 101015 Operations Research, 502052 Betriebswirtschaftslehre
- Link zum Portal
- https://ucrisportal.univie.ac.at/de/publications/354833f1-04a7-4ed0-9937-b4c69477863d