Routenoptimierung

[Armin0102]

Hallo zusammen,

ich habe mal ein Programm entwickelt für eine Routenoptimierung. Das Ganze ist GUI basiert aber nicht mit irgendwelchen Maps oder so. Die Routen werden einfach in Form einer Tabelle am Ende darfestellt. Funktioniert soweit auch alles super, sobald ich jedoch 2 Städt 2 mal bereisen will führt mein algorithmus dazu, dass eben diese Städte plötzlich durch andere ersetzt werden. Bsp.: schwerin, Kiel, Bremen, Köln Lübeck und Hamburg 2 mal werden bereist. Am ende meines Algo kann es dazu kommen, dass plötzlich Hamburg und schwerin 2 mal bereist werden. könnt ihr mir helfen? hier der Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
package Routenoptimierung.Algo1;
 
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.text.DecimalFormat;
import java.util.Iterator;
import java.util.Random;
import GUI.FrameErgebnis;
import Routenoptimierung.*;
 
public class AlgorithmusSchnell {
 
    private RouteList routeList, routeList2;
    private CityList cityList, cityList2;
    private double entfernung;
    private double gesamtEntfernung, gesamtEntfernung2;
    private Entfernungsberechner entfernungsberechner = new Entfernungsberechner();
    private int guete;
    private int verbesserungen;
    private Random random;
    private int zufall1, zufall2;
    private static DecimalFormat f = new DecimalFormat("#0.00km");
 
    public AlgorithmusSchnell(CityList cityList) throws Exception {
        this.cityList = cityList;
        routeList = new RouteList();
        bildeStartroute();
        verbessereRoute();
        gebeRouteAus();
    }
 
    public void bildeStartroute() {
        guete = 10;
        for (int i = 0; i < cityList.size(); i++) {
 
            if (i < cityList.size() - 1) {
 
                entfernung = entfernungsberechner.berechneEntfernung(cityList
                        .getCity(i).getLongitude(), cityList.getCity(i)
                        .getLatitude(), cityList.getCity(i + 1).getLongitude(),
                        cityList.getCity(i + 1).getLatitude());
                gesamtEntfernung = gesamtEntfernung + entfernung;
                routeList.addRoute(cityList.getCity(i),
                        cityList.getCity(i + 1), entfernung, guete);
            }
 
            else {
                entfernung = entfernungsberechner.berechneEntfernung(cityList
                        .getCity(0).getLongitude(), cityList.getCity(0)
                        .getLatitude(), cityList.getCity(cityList.size() - 1)
                        .getLongitude(), cityList.getCity(cityList.size() - 1)
                        .getLatitude());
                gesamtEntfernung = gesamtEntfernung + entfernung;
                routeList.addRoute(cityList.getCity(cityList.size() - 1),
                        cityList.getCity(0), entfernung, guete);
            }
        }
    }
 
    public void verbessereRoute() throws Exception {
 
        verbesserungen = 1000;
        cityList2 = deepCopyCityList(cityList);
 
        for (int j = 0; j < verbesserungen; j++) {
 
            random = new Random();
            zufall1 = random.nextInt(cityList.size() - 3) + 1;
            zufall2 = random.nextInt(cityList.size() - 3) + 1;
            cityList2 = mutiereList(cityList, zufall1, zufall2);
            gesamtEntfernung2 = 0;
            routeList2 = new RouteList();
 
            if (j < 100) {
                guete = 10;
            } else if (j < 200) {
                guete = 9;
            } else if (j < 300) {
                guete = 8;
            } else if (j < 400) {
                guete = 7;
            } else if (j < 500) {
                guete = 6;
            } else if (j < 600) {
                guete = 5;
            } else if (j < 700) {
                guete = 4;
            } else if (j < 800) {
                guete = 3;
            } else if (j < 900) {
                guete = 2;
            } else if (j < 1000) {
                guete = 1;
            }
 
            for (int i = 0; i < cityList2.size(); i++) {
 
                if (i < cityList2.size() - 1) {
 
                    entfernung = entfernungsberechner.berechneEntfernung2(
                            cityList2.getCity(i), cityList2.getCity(i + 1));
 
                    routeList2.addRoute(cityList2.getCity(i), cityList2
                            .getCity(i + 1), entfernung, guete);
                    gesamtEntfernung2 = gesamtEntfernung2 + entfernung;
                }
 
                else {
                    entfernung = entfernungsberechner.berechneEntfernung2(
                            cityList2.getCity(0), cityList2.getCity(cityList2
                                    .size() - 1));
 
                    routeList2.addRoute(
                            cityList2.getCity(cityList2.size() - 1), cityList2
                                    .getCity(0), entfernung, guete);
                    gesamtEntfernung2 = gesamtEntfernung2 + entfernung;
                }
            }
            System.out.println(gesamtEntfernung2);
            if (gesamtEntfernung2 < gesamtEntfernung) {
                routeList = deepCopyRouteList(routeList2);
                gesamtEntfernung = gesamtEntfernung2;
            }
        }
    }
 
    public void gebeRouteAus() {
        Iterator<Route> it = routeList.iterator();
        while (it.hasNext()){
            Route r = it.next();
            r.setGuete(guete);
        }
        new FrameErgebnis(routeList, f.format(gesamtEntfernung));
    }
 
    private CityList mutiereList(CityList aendern, int index1, int index2) {
 
        if (index1 == index2) {
            return aendern;
        }
 
        City tmp1 = aendern.getCity(index1);
        System.out.println(tmp1.getName());
        System.out.println(aendern.getCity(index2).getName());
 
        aendern.set(index1, aendern.getCity(index2));
        aendern.set(index2, tmp1);
 
        System.out.println(aendern.getCity(index1).getName());
        System.out.println(aendern.getCity(index2).getName() + "\n" + "\n");
 
        return aendern;
    }
 
    private static CityList deepCopyCityList(CityList cityList)
            throws Exception {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        new ObjectOutputStream(baos).writeObject(cityList);
 
        ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
 
        return (CityList) new ObjectInputStream(bais).readObject();
    }
 
    private static RouteList deepCopyRouteList(RouteList routeList)
            throws Exception {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        new ObjectOutputStream(baos).writeObject(routeList);
 
        ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
 
        return (RouteList) new ObjectInputStream(bais).readObject();
    }
}

[Marco13]

Ich würd' sagen da fehlen zu viele Informationen über Kontext und andere Klassen. Aber nur nebenbei:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
            if (j < 100) {
                guete = 10;
            } else if (j < 200) {
                guete = 9;
            } else if (j < 300) {
                guete = 8;
            } else if (j < 400) {
                guete = 7;
            } else if (j < 500) {
                guete = 6;
            } else if (j < 600) {
                guete = 5;
            } else if (j < 700) {
                guete = 4;
            } else if (j < 800) {
                guete = 3;
            } else if (j < 900) {
                guete = 2;
            } else if (j < 1000) {
                guete = 1;
            }

->

1
guete = Math.max(1, 10 - (j/100));

[Armin0102]

ok ich werde mal alles kommentieren was man so wissen müsste:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
package Routenoptimierung.Algo1;
 
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.text.DecimalFormat;
import java.util.Iterator;
import java.util.Random;
import GUI.FrameErgebnis;
import Routenoptimierung.*;
 
public class AlgorithmusSchnell {
 
        //RouteList ist eine Klasse die in einer LinkedList Route - Objekte          verwaltet(Start,Ziel,Distance,Güte)
    private RouteList routeList, routeList2;
        //CityList ist eine Klasse die in einer LinkedList City - Objekte verwaltet(Name,Longitude,Latitude)
    private CityList cityList, cityList2;
    private double entfernung;
    private double gesamtEntfernung, gesamtEntfernung2;
//diese klasse beherbergt eine Methode(formel) die die Entfernung zwischen 2 Punkten errechnet basierend auf Longitude und latitude(geo Daten)
    private Entfernungsberechner entfernungsberechner = new Entfernungsberechner();
    private int guete;
    private int verbesserungen;
    private Random random;
    private int zufall1, zufall2;
    private static DecimalFormat f = new DecimalFormat("#0.00km");
 
    public AlgorithmusSchnell(CityList cityList) throws Exception {
        this.cityList = cityList;
        routeList = new RouteList();
        bildeStartroute();
        verbessereRoute();
        gebeRouteAus();
    }
//die übergebene Liste von City´s wird komplett durchlaufen und die einzelnen City´s werden in der Reihenfolge verbunden(zu einer Route) wie sie in der List stehen. Ausnahme ist die Anfangsstadt sie muss bestehen bleiben als Start und Ziel
    public void bildeStartroute() {
        guete = 10;
        for (int i = 0; i < cityList.size(); i++) {
 
            if (i < cityList.size() - 1) {
 
                entfernung = entfernungsberechner.berechneEntfernung(cityList
                        .getCity(i).getLongitude(), cityList.getCity(i)
                        .getLatitude(), cityList.getCity(i + 1).getLongitude(),
                        cityList.getCity(i + 1).getLatitude());
                gesamtEntfernung = gesamtEntfernung + entfernung;
                routeList.addRoute(cityList.getCity(i),
                        cityList.getCity(i + 1), entfernung, guete);
            }
 
            else {
                entfernung = entfernungsberechner.berechneEntfernung(cityList
                        .getCity(0).getLongitude(), cityList.getCity(0)
                        .getLatitude(), cityList.getCity(cityList.size() - 1)
                        .getLongitude(), cityList.getCity(cityList.size() - 1)
                        .getLatitude());
                gesamtEntfernung = gesamtEntfernung + entfernung;
                routeList.addRoute(cityList.getCity(cityList.size() - 1),
                        cityList.getCity(0), entfernung, guete);
            }
        }
    }
 
//diese methode soll die zunächst gebildete Route verbessern und "mutiert" dazu die übergebene CityList(es werden einfach 2 zufällig bestimmte Städte in der Liste getauscht)
    public void verbessereRoute() throws Exception {
 
        verbesserungen = 1000;
//deepcopy benutze ich um keine Referenzen zu erstellen sondern eigenständige objekte, die keinen einfluss aufeinander haben
        cityList2 = deepCopyCityList(cityList);
 
        for (int j = 0; j < verbesserungen; j++) {
 
            random = new Random();
            zufall1 = random.nextInt(cityList.size() - 3) + 1;
            zufall2 = random.nextInt(cityList.size() - 3) + 1;
            cityList2 = mutiereList(cityList, zufall1, zufall2);
            gesamtEntfernung2 = 0;
            routeList2 = new RouteList();
 
            guete = Math.max(1, 10 - (j/100));
 
            for (int i = 0; i < cityList2.size(); i++) {
 
                if (i < cityList2.size() - 1) {
 
                    entfernung = entfernungsberechner.berechneEntfernung2(
                            cityList2.getCity(i), cityList2.getCity(i + 1));
 
                    routeList2.addRoute(cityList2.getCity(i), cityList2
                            .getCity(i + 1), entfernung, guete);
                    gesamtEntfernung2 = gesamtEntfernung2 + entfernung;
                }
 
                else {
                    entfernung = entfernungsberechner.berechneEntfernung2(
                            cityList2.getCity(0), cityList2.getCity(cityList2
                                    .size() - 1));
 
                    routeList2.addRoute(
                            cityList2.getCity(cityList2.size() - 1), cityList2
                                    .getCity(0), entfernung, guete);
                    gesamtEntfernung2 = gesamtEntfernung2 + entfernung;
                }
            }
            System.out.println(gesamtEntfernung2);
            if (gesamtEntfernung2 < gesamtEntfernung) {
                routeList = deepCopyRouteList(routeList2);
                gesamtEntfernung = gesamtEntfernung2;
            }
        }
    }
 
    public void gebeRouteAus() {
        Iterator<Route> it = routeList.iterator();
        while (it.hasNext()){
            Route r = it.next();
            r.setGuete(guete);
        }
        new FrameErgebnis(routeList, f.format(gesamtEntfernung));
    }
 
    private CityList mutiereList(CityList aendern, int index1, int index2) {
 
        if (index1 == index2) {
            return aendern;
        }
 
        City tmp1 = aendern.getCity(index1);
        System.out.println(tmp1.getName());
        System.out.println(aendern.getCity(index2).getName());
 
        aendern.set(index1, aendern.getCity(index2));
        aendern.set(index2, tmp1);
 
        System.out.println(aendern.getCity(index1).getName());
        System.out.println(aendern.getCity(index2).getName() + "\n" + "\n");
 
        return aendern;
    }
 
    private static CityList deepCopyCityList(CityList cityList)
            throws Exception {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        new ObjectOutputStream(baos).writeObject(cityList);
 
        ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
 
        return (CityList) new ObjectInputStream(bais).readObject();
    }
 
    private static RouteList deepCopyRouteList(RouteList routeList)
            throws Exception {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        new ObjectOutputStream(baos).writeObject(routeList);
 
        ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
 
        return (RouteList) new ObjectInputStream(bais).readObject();
    }
}

[Marco13]

Ja, ich meinte solche Sachen wie dass man z.B. nicht weiß, was "RouteList" genau macht, und ob nicht vielleicht dort der Fehler liegt. Dass man das ganze nicht testen und nachvollziehen kann, und man nur eine sehr grobe Vorstellung von dem Problem bekommt ist... (ja, da gewöhnt man sich in solchen Foren dran )

Aber noch ein Punkt, der auch zur Lösungsfindung beitragen könnte:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
    public void bildeStartroute() {
        guete = 10;
        for (int i = 0; i < cityList.size(); i++) {
 
            if (i < cityList.size() - 1) {
 
                entfernung = entfernungsberechner.berechneEntfernung(cityList
                        .getCity(i).getLongitude(), cityList.getCity(i)
                        .getLatitude(), cityList.getCity(i + 1).getLongitude(),
                        cityList.getCity(i + 1).getLatitude());
                gesamtEntfernung = gesamtEntfernung + entfernung;
                routeList.addRoute(cityList.getCity(i),
                        cityList.getCity(i + 1), entfernung, guete);
            }
 
            else {
                entfernung = entfernungsberechner.berechneEntfernung(cityList
                        .getCity(0).getLongitude(), cityList.getCity(0)
                        .getLatitude(), cityList.getCity(cityList.size() - 1)
                        .getLongitude(), cityList.getCity(cityList.size() - 1)
                        .getLatitude());
                gesamtEntfernung = gesamtEntfernung + entfernung;
                routeList.addRoute(cityList.getCity(cityList.size() - 1),
                        cityList.getCity(0), entfernung, guete);
            }
        }
    }

->

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    public void bildeStartroute() 
    {
        guete = 10;
        for (int i = 0; i < cityList.size(); i++) 
        {
            City city0 = cityList.getCity(i);
            City city1 = cityList.getCity((i+1)%cityList.size());
 
            entfernung = entfernungsberechner.berechneEntfernung(
                city0.getLongitude(), city0.getLatitude(), 
                city1.getLongitude(), city1.getLatitude());
 
            gesamtEntfernung = gesamtEntfernung + entfernung;
 
            System.out.println("Füge hinzu: "+city0+" nach "+city1+", entfernung "+entfernung);
            routeList.addRoute(city0, city1, entfernung, guete);
 
            System.out.println("Route ist jetzt "+routeList);
        }
    }

In den Klassen "City" und "RouteList" sollte die Methode "toString" so überschrieben sein, dass sie hilfreiche Informationen ausgibt - bei "City" reicht vermutlich der Name (und ggf. die Position), bei "RouteList" wäre eine Ausgabe in der Form
Hamburg -> München -> Berlin -> Huntertupfing
vermutlich hilfreich, damit man durch die System.out.printlns schrittweise nachvollziehen kann, wie die Route sich ändert. Wenn man sieht, dass diese Klasse eigentlich alles richtig macht, und auf einmal doch die Route falsch ist, liegt der Fehler in der RouteList. Andernfalls erkennt man an den Debug-Ausgaben, zu welchem Zeitpunkt der Fehler auftritt, und kann den Fehler genauer eingrenzen.

[Armin0102]

danke dir für deine Mühe ich werd mir das mal so angucken und den fehler so suchen, wenn es nicht klappt stell ich auch mal alle beteiligten KLassen hier mit rein damit du auch weißt was los ist^^ aber eine frage noch, wie überschreibe ich denn eine toString methode in einer Klasse die ja nur eine linkedlist enthält und die dazugehörigen methoden?

[Armin0102]

ok schon erledigt^^ hab die toString() alle überschrieben und teste jetzt durch

[Armin0102]

also irgendwie finde ich den Fehler nicht. Mit deinen syso´s habe ich zwar erkannt das die klasse des Algorithmus selbst der schuldige ist, jedoch versteh ich beim besten willen nicht warum.

Hier also einmal alle Klassen die beteiligt sind der Reihe nach

Algo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package Routenoptimierung.Algo1;
 
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.text.DecimalFormat;
import java.util.Iterator;
import java.util.Random;
import GUI.FrameErgebnis;
import Routenoptimierung.*;
 
public class AlgorithmusSchnell {
 
    private RouteList routeList, routeList2;
    private CityList cityList, cityList2;
    private double entfernung;
    private double gesamtEntfernung, gesamtEntfernung2;
    private Entfernungsberechner entfernungsberechner = new Entfernungsberechner();
    private int guete;
    private int verbesserungen;
    private Random random;
    private int zufall1, zufall2;
    private static DecimalFormat f = new DecimalFormat("#0.00km");
 
    public AlgorithmusSchnell(CityList cityList) throws Exception {
        this.cityList = cityList;
        routeList = new RouteList();
        bildeStartroute();
        verbessereRoute();
        gebeRouteAus();
    }
 
    public void bildeStartroute() {
        guete = 10;
        for (int i = 0; i < cityList.size(); i++) {
            City city0 = cityList.getCity(i);
            City city1 = cityList.getCity((i + 1) % cityList.size());
 
            entfernung = entfernungsberechner.berechneEntfernung2(city0, city1);
 
            gesamtEntfernung = gesamtEntfernung + entfernung;
 
            // System.out.println("Füge hinzu: " + city0 + " nach " + city1
            // + ", entfernung " + entfernung);
            routeList.addRoute(city0, city1, entfernung, guete);
 
            // System.out.println("Route ist jetzt " + routeList);
        }
    }
 
    public void verbessereRoute() throws Exception {
 
        verbesserungen = 50;
        cityList2 = deepCopyCityList(cityList);
 
        for (int j = 0; j < verbesserungen; j++) {
 
            random = new Random();
            zufall1 = random.nextInt(cityList.size() - 2) + 1;
            zufall2 = random.nextInt(cityList.size() - 2) + 1;
            cityList2 = mutiereList(cityList2, zufall1, zufall2);
            gesamtEntfernung2 = 0;
            routeList2 = new RouteList();
 
            guete = Math.max(1, 10 - (j / 100));
 
            for (int i = 0; i < cityList2.size(); i++) {
 
                City city0 = cityList2.getCity(i);
                City city1 = cityList2.getCity((i + 1) % cityList2.size());
 
                entfernung = entfernungsberechner.berechneEntfernung2(city0,
                        city1);
 
                gesamtEntfernung2 = gesamtEntfernung2 + entfernung;
 
                // System.out.println("Füge hinzu: " + city0 + " nach " + city1
                // + ", entfernung " + entfernung);
                routeList2.addRoute(city0, city1, entfernung, guete);
 
                // System.out.println("Route ist jetzt " + routeList2);
            }
 
            if (gesamtEntfernung2 < gesamtEntfernung) {
                routeList = deepCopyRouteList(routeList2);
                gesamtEntfernung = gesamtEntfernung2;
            }
        }
    }
 
    public void gebeRouteAus() {
        Iterator<Route> it = routeList.iterator();
        while (it.hasNext()) {
            Route r = it.next();
            r.setGuete(guete);
        }
        new FrameErgebnis(routeList, f.format(gesamtEntfernung));
    }
 
    private CityList mutiereList(CityList aendern, int index1, int index2) {
 
        boolean erfolgreich;
        City tmp1 = aendern.getCity(index1);
        
        erfolgreich = aendern.set(index1, aendern.getCity(index2));
        
        if (erfolgreich == true) {
            aendern.set(index2, tmp1);
            return aendern;
        } else if (erfolgreich == false) {
            aendern.set(index1, tmp1);
        }
        return aendern;
    }
 
    private static CityList deepCopyCityList(CityList cityList)
            throws Exception {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        new ObjectOutputStream(baos).writeObject(cityList);
 
        ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
 
        return (CityList) new ObjectInputStream(bais).readObject();
    }
 
    private static RouteList deepCopyRouteList(RouteList routeList)
            throws Exception {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        new ObjectOutputStream(baos).writeObject(routeList);
 
        ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
 
        return (RouteList) new ObjectInputStream(bais).readObject();
    }
}

City:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package Routenoptimierung;
 
import java.io.Serializable;
 
public class City implements Serializable {
    
    private static final long serialVersionUID = 4066185919577241833L;
    private String name;
    private double longitude;
    private double latitude;
    
    public City(String name, double latitude, double longitude) {
        this.name = name;
        this.longitude = longitude;
        this.latitude = latitude;
    }
    
    public double getLongitude() {
        return longitude;
    }
    
    public double getLatitude() {
        return latitude;
    }
 
    public String getName() {
        return name;
    }
 
    @Override
    public String toString() {
        return name;
    }
}

CityList:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package Routenoptimierung;
 
import java.io.Serializable;
import java.util.Arrays;
import java.util.LinkedList;
 
import java.util.Iterator;
 
public class CityList implements Serializable {
 
    private static final long serialVersionUID = 6165974134529706482L;
    private LinkedList<City> list = new LinkedList<City>();
 
    public CityList() {
    }
 
    public void addCity(City c) {
        list.add(c);
    }
 
    public City getCity(int index) {
        City c = list.get(index);
        return c;
    }
 
    public City getCity(String name) {
        Iterator<City> it = list.iterator();
        while (it.hasNext()) {
            City c = it.next();
            if (c.getName().equals(name)) {
                return c;
            }
        }
        return null;
    }
 
    public double getLongitude(String name) {
        Iterator<City> it = list.iterator();
        while (it.hasNext()) {
            City c = it.next();
            if (c.getName().equals(name)) {
                return c.getLongitude();
            }
        }
        return 0;
    }
 
    public double getLatitude(String name) {
        Iterator<City> it = list.iterator();
        while (it.hasNext()) {
            City c = it.next();
            if (c.getName().equals(name)) {
                return c.getLatitude();
            }
        }
        return 0;
    }
 
    public int size() {
        return list.size();
    }
 
    public boolean set(int index, City city) {
        if (!list.get(index - 1).getName().equals(city.getName())
                && !list.get(index + 1).getName().equals(city.getName())) {
            list.set(index, city);
            System.out.println(list);
            return true;
        }
        else
        return false;
    }
 
    public Iterator<City> iterator(){
        return list.iterator();
    }
    
    @Override
    public String toString() {
        return Arrays.toString(list.toArray());
    }
}

Route:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package Routenoptimierung;
 
import java.io.Serializable;
 
public class Route implements Serializable {
 
    private static final long serialVersionUID = -397180462412241872L;
    private double distance;
    private City start;
    private City ziel;
    private int guete;
 
    public Route(City start,City ziel,double distance,int guete) {
        this.start = start;
        this.ziel = ziel;
        this.distance = distance;
        this.guete = guete;
    }
 
    public Route(City start,City ziel,double distance) {
        this.start = start;
        this.ziel = ziel;
        this.distance = distance;
    }
 
    public double getDistance() {
        return distance;
    }
    
    public City getStart(){
        return start;
    }
    
    public City getZiel(){
        return ziel;
    }
 
    public int getGuete() {
        return guete;
    }
 
    public void setDistance(double distance) {
        this.distance = distance;
    }
 
    public void setStart(City start) {
        this.start = start;
    }
 
    public void setZiel(City ziel) {
        this.ziel = ziel;
    }
 
    public void setGuete(int guete) {
        this.guete = guete;
    }
 
    @Override
    public String toString() {
        return start.toString() +"->" +ziel.toString();
    }
}

RouteList:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package Routenoptimierung;
 
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
 
import javax.swing.table.AbstractTableModel;
 
public class RouteList extends AbstractTableModel {
 
    private static final long serialVersionUID = 6485473667766723334L;
    private LinkedList<Route> list = new LinkedList<Route>();
    private String columnHeaders[] = { "Start", "Ziel", "Distance", "Güte" };
 
    public RouteList() {
 
    }
 
    public void addRoute(City start, City ende, double entfernung, int guete) {
        list.add(new Route(start, ende, entfernung, guete));
        this.fireTableDataChanged();
    }
 
    public void addRoute(Route r) {
        list.add(r);
        this.fireTableDataChanged();
    }
 
    public Route deleteRoute(int index) {
        Route tmp = list.remove(index);
        this.fireTableDataChanged();
        return tmp;
    }
 
    public Route get(int index) {
        Route r = list.get(index);
        return r;
    }
 
    public Route getRouteByStart(String StartCity) {
        Iterator<Route> it = list.iterator();
        while (it.hasNext()) {
            Route r = it.next();
            if (r.getStart().equals(StartCity)) {
                return r;
            }
        }
        return null;
    }
 
    public Route getRouteByZiel(String ZielCity) {
        Iterator<Route> it = list.iterator();
        while (it.hasNext()) {
            Route r = it.next();
            if (r.getStart().equals(ZielCity)) {
                return r;
            }
        }
        return null;
    }
 
    public int size() {
        return list.size();
    }
 
    public void set(int index, Route route) {
        list.set(index, route);
    }
 
    @Override
    public String getColumnName(int index) {
 
        return columnHeaders[index];
    }
 
    @Override
    public int getColumnCount() {
        return 4;
    }
 
    @Override
    public int getRowCount() {
        return list.size();
    }
 
    @Override
    public Object getValueAt(int row, int column) {
        Object tmp = new String("");
        switch (column) {
        case 0:
            tmp = list.get(row).getStart().getName();
            break;
        case 1:
            tmp = list.get(row).getZiel().getName();
            break;
        case 2:
            tmp = list.get(row).getDistance();
            break;
        case 3:
            tmp = list.get(row).getGuete();
            break;
        }
        return tmp;
    }
 
    public Iterator<Route> iterator() {
        return list.iterator();
    }
 
    @Override
    public String toString() {
        return Arrays.toString(list.toArray());
    }
}

Entfernungsberechner:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package Routenoptimierung;
 
public class Entfernungsberechner {
    
    private double Erdradius = 6267;
    private double Alon;
    private double Alat;
    private double Blon;
    private double Blat;
    
    public Entfernungsberechner(){
        
    }
    
    public double berechneEntfernung(double Alon, double Alat, double Blon, double Blat){
        double dLat = Math.toRadians(Blat-Alat);    
        double dLng = Math.toRadians(Blon-Alon); 
        double a = Math.sin(dLat/2) * Math.sin(dLat/2) +               
        Math.cos(Math.toRadians(Alat)) * Math.cos(Math.toRadians(Blat)) *               
        Math.sin(dLng/2) * Math.sin(dLng/2);    
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));    
        double dist = Erdradius * c;
        return dist;
    }
    
    public double berechneEntfernung2(City city1, City city2){
        Alon = city1.getLongitude();
        Alat = city1.getLatitude();
        Blon = city2.getLongitude();
        Blat = city2.getLatitude();
        double dLat = Math.toRadians(Blat-Alat);    
        double dLng = Math.toRadians(Blon-Alon); 
        double a = Math.sin(dLat/2) * Math.sin(dLat/2) +               
        Math.cos(Math.toRadians(Alat)) * Math.cos(Math.toRadians(Blat)) *               
        Math.sin(dLng/2) * Math.sin(dLng/2);    
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));    
        double dist = Erdradius * c;
        return dist;
    }
}

MainTest:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package Routenoptimierung.Algo1;
 
import Routenoptimierung.City;
import Routenoptimierung.CityList;
 
public class MainTest {
 
    public static void main(String[] args) throws Exception {
        CityList v = new CityList();
        v.addCity(new City("Hamburg", 53.5534074, 9.9921962));
        v.addCity(new City("Kiel", 54.322654, 10.13586));
        v.addCity(new City("Lübeck", 53.869563, 10.687579));
        v.addCity(new City("Rostock", 54.0901331, 12.1329562));
        v.addCity(new City("Bremen", 53.074981, 8.807081));
        v.addCity(new City("Hannover", 52.3720683, 9.7356861));
        v.addCity(new City("Naschendorf", 54.3720683, 8.7356861));
        v.addCity(new City("Lübeck", 53.869563, 10.687579));
        v.addCity(new City("Kiel", 54.322654, 10.13586));
        
        new AlgorithmusSchnell(v);
    }
}

danke für jede hilfe

[Marco13]

Und die Frage ist.... ?

[Armin0102]

immer noch das selbe Problem wie oben beschrieben! im ersten Post

[Marco13]

In deinen Eingabedaten kommen aber sowieso schon Städte mehrfach vor....

[Armin0102]

ja das soll ja auchso sein! aber bei meinem programm kommt es zu dem phenomen, dass doppelt verkommende städte einfach getauscht werden. Das soll heißen gebe ich wie oben Lübeck und Kiel 2 mal ein, so müssten diese im ergebnis auch 2 mal bereist werden! es kommt aber vor das in manchen ergebnissen statt kiel und lübeck plötzlich kiel hamburg oder lübeck bremen oder bremen hannover

[Marco13]

Ich bezweifle, dass mir in nächster Zeit so langweilig sein wird, dass ich deinen Code debugge. Schau' dir an, was der Routenoptimierer macht, und bei welchem Schritt das erste mal ein Fehler auftaucht...

[Armin0102]

naja danke für deine Hilfe soweit, ich werde mir das mal nochmal angucken und gegebenen falls das ganze umproggn. Hab da schon so eine idee. Aber sag mal könntest du mir wenn du so einfach mal über den code guckst sagen was man da hätte besser schreiben können? syntaktisch schöner und aussagekräftiger?

[Marco13]

Musst ja nicht "das ganze Umproggn" Mit der Ausgabe müßte man den Fehler doch eingrenzen können?!
Ansonsten sieht das IMHO schon ganz vernünftig aus. Statt der Serialization hätte ich zwar Copy-Konstruktoren verwendet, aber das ist nichts "strukturelles"....

[Armin0102]

habe das problem ohne umproggn gelöst^^ es lag an der Mutations - Methode! da wurde ja 2 mal .set aufgerufen und diese methode war in der klasse routeList definiert. hier fand bei jedem mal eine überprüfung statt und es konnte halt passieren, das ein .set() durch ging und der andere nicht^^ dadruch hat sich dann dieListe anders mutiert als gewollt. nun habe ich dies geändert und es läuft super. ich danke dir für deine denk anregungen^^ hat mir geholfen.

jetzt stehe ich aber dummerweise vor dem nächsten Problem. Mein nächster Algo soll ALLE möglichen Routen für eine gegebene Städteliste bilden und die beste(kürzeste) auswählen.Bis jetzt habe ich es erstmal so gemacht das 2 for schleifen jeweils 2 aufeinander folgende Städte aus der Liste holen und diese als Route in eine RouteList speichern. so bekomme ich Alle möglichkeiten auch 2mal die selbe stadt, wobei die distance zwischen diesen dann null ist hier der code dazu:

1
2
4
5
6
7
8
9
10
11
12
13
14
15
17
18
19
20
21
22
23
24
26
27
28
29
30
31
32
33
34
public void bildeAlleMoeglichenRouten() throws Exception {
 
routeList = new RouteList();
 
gesamtEntfernung1 = 1000000000;
 
guete = 1;
 
for (int j = 0; j < cityList.size() - 1; j++) {
 
City c = cityList.getCity(j);
 
gesamtEntfernung = 0;
 
for (int i = 1; i < cityList.size(); i++) {
 
City c1 = cityList.getCity(i);
 
entfernung = entfernungsberechner.berechneEntfernung2(c, c1);
 
gesamtEntfernung = gesamtEntfernung + entfernung;
 
routeList.addRoute(new Route(c, c1, entfernung, guete));
 
gesamtEntfernung1 = gesamtEntfernung;
 
}
 
}
 
}

so nun versuche ich aus dieser routeList alle sinnvollen und richtigen Lösungen zu generieren da hapert es noch ein wenig. wenn ich beispiels weiße aus der routeList hamburg -> kiel auswähle so muss ich auf jeden fall als nächstes alle möglichkeiten durchsuchen, wo kiel als start stadt steht und so weiter.

[Marco13]

Wenn ich das richtig sehe, brauchst zu zu einer gegebenen Menge von Städten
H Hamburg
B Berlin
M München
S Stuttgart

Alle möglichen Kombinationen:
HBMS, HMBS, HSBM, HSMB, BHMS...

Wenn dem so ist, schau dir mal das "PermutationIterable" aus Combinatorics an.

EDIT: Du weißt aber hoffentlich, dass das dann exponentielle Laufzeit hat, d.h. schon bei 6 oder 8 Städten oder so ziemlich lange dauern kann....

[Armin0102]

ja das weiß ich, das ist auch auf die aufgabe^^ ich bastel ja an einer Routenoptimierung. Es gibt zwei algo´s der eine berechnet genau(ist der, der potenziel ist) und einer bestimmt eine nährungslösung in dem mutationen des ergebnisses in einer bestimmten anzahl durchgeführt werden. Ich möchte das so bestimmen das abhängig von der anzahl der städte die der benutzer zu einer route amchen will ein algo ausgewählt wird. was würdest du sagen reicht die grenze von 10 städten für den genauen(exponentiellen) algo aus oder ist das noch zu gering, ich möchte eine möglichst geringe Wartezeithaben vlt so 2-3 sekunden.

ach und danke für den hinweis mit der combinatorik

[Marco13]

Bei 2 oder 3 Sekunden kannst du nur 3 Städte behandeln - auf einem 8086 mit 2 MHz. (Soll heißen: Das wirst du ausprobieren müssen )

[oldshoe]

Vielleicht hilft die auch der kürzeste-Wege-Algorithmus(Dijkstra) um deine Routenplanung zu optimieren