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:
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:
Java:
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();
}
}
)
