The Ant System and its Application to Combinatorial Optimization Problems

Bernd Bullnheimer, Christine Strauss

Veröffentlichungen: Beitrag zu KonferenzSonstiger KonferenzbeitragPeer Reviewed

Abstract

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.
OriginalspracheEnglisch
PublikationsstatusVeröffentlicht - 1997
VeranstaltungSixth Viennese Workshop on Optimal Control, Dynamic Games, Nonlinear Dynamics and Adaptive Systems - Vienna, Österreich
Dauer: 21 Mai 199723 Mai 1997

Konferenz

KonferenzSixth Viennese Workshop on Optimal Control, Dynamic Games, Nonlinear Dynamics and Adaptive Systems
Land/GebietÖsterreich
OrtVienna
Zeitraum21/05/9723/05/97

ÖFOS 2012

  • 101015 Operations Research
  • 502052 Betriebswirtschaftslehre

Fingerprint

Untersuchen Sie die Forschungsthemen von „The Ant System and its Application to Combinatorial Optimization Problems“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitationsweisen