I’m trying to solve a variant of the TSP problem with “multiple salesmen". I have a series of n waypoints and m drones and I want to generate a result which sorts of balances the number of waypoints between drones and returns an acceptable shortest travelling time. At the moment, I'm not really too worried about finding an optimal solution, I just want something that works at this point. I've sort of distilled my problem to a traditional TSP run multiple times. My example is for a series of waypoints:
[0,1,2,3,4,5,6,7,8,9,10,11]
where 0 == 11 is the start and end point. Say I have 4 drones, I want to generate something like:
Drone A = [0,1,2,3,11]
Drone B = [0,5,6,7,11]
Drone C = [0,4,8,11]
Drone D = [0,9,10,11]
However, I’m struggling to generate a consistent output in my crossover function. My current function looks like this:
DNA DNA::crossover( DNA &parentB)
{
// sol holds the individual solution for
// each drone
std::vector<std::vector<std::size_t>> sol;
// contains the values in flattened sol
// used to check for duplicates
std::vector<std::size_t> flat_sol;
// returns the number of solutions
// required
int number_of_paths = this→getSolution().size();
// limits the number of waypoints required for each drone
// subtracting 2 to remove “0” and “11”
std::size_t max_wp_per_drone = ((number_of_cities-2)/number_of_drones) + 1;
for(std::size_t i = 0; i < number_of_paths; i++)
{
int start = rand() % (this->getSolution().at(i).size() -2) + 1;
int end = start + 1 + rand() % ((this->getSolution().at(i).size()-2) - start +1);
std::vector<std::size_t>::const_iterator first = this->getSolution().at(i).begin()+start;
std::vector<std::size_t>::const_iterator second = this- >getSolution().at(i).begin()+end;
// First Problem occurs here… Sometimes, newOrder can return nothing based on
//the positions of start and end. Tried to mitigate by putting a while loop
to regenerate the vector
std::vector<std::size_t> newOrder(first, second);
// RETURNS a vector from the vector of vectors sol
flat_sol = flatten(sol);
// compare new Order with solution and remove any duplicates..
for(std::size_t k = 0; k < newOrder.size(); k++ )
{
int duplicate = newOrder.at(k);
if(std::find(flat_sol.begin(), flat_sol.end(), duplicate) != flat_sol.end())
{
// second problem is found here, sometimes,
// new order might only return a vector with a single value
// or values that have already been assigned to another drone.
// In this case, those values are removed and newOrder is now 0
newOrder.erase(newOrder.begin()+k);
}
}
// attempt to create the vectors here.
for(std::size_t j = 1; j <=parentB.getSolution().at(i).size()-2; j++)
{
int city = parentB.getSolution().at(i).at(j);
if(newOrder.empty())
{
if(std::find(flat_sol.begin(), flat_sol.end(), city) == flat_sol.end())
{
newOrder.push_back(city);
}
}
else if((std::find(newOrder.begin(), newOrder.end(), city) == newOrder.end())
&&(std::find(flat_sol.begin(), flat_sol.end(), city) == flat_sol.end())
&& newOrder.size() < max_wp_per_drone )
{
newOrder.push_back(city);
}
}
sol.push_back(newOrder);
}
// waypoints and number_of drones are known,
//0 and 11 are appended to each vector in sol in the constructor.
return DNA(sol, waypoints, number_of_drones);
}
A sample output from my previous runs return the following:
[0,7,9,8, 11]
[0, 1,2,4,11]
[0, 10, 6, 11]
[0,3,11]
// This output is missing one waypoint.
[0,10,7,5, 11]
[0, 8,3,1,11]
[0, 6, 9, 11]
[0,2,4,11]
// This output is correct.
Unfortunately, this means in my subsequent generations of new children. and me getting the correct output seems to be random. For example, for one generation, I had a population size which had 40 correct children and 60 children with missing waypoints while in some cases, I've had more correct children. Any tips or help is appreciated.
Solved this by taking a slightly different approach. Instead of splitting the series of waypoints before perfoming crossover, I simply pass the series of waypoints
[0,1,2,3,4,5,6,7,8,9,10,11]
perform crossover, and when computing fitness of each set, I split the waypoints based on m drones and find the best solution of each generation. New crossover function looks like this:
DNA DNA::crossover( DNA &parentB)
{
int start = rand () % (this->getOrder().size()-1);
int end = getRandomInt<std::size_t>(start +1 , this->getOrder().size()-1);
std::vector<std::size_t>::const_iterator first = this->getOrder().begin() + start;
std::vector<std::size_t>::const_iterator second = this->getOrder().begin() + end;
std::vector<std::size_t> newOrder(first, second);
for(std::size_t i = 0; i < parentB.getOrder().size(); i++)
{
int city = parentB.getOrder().at(i);
if(std::find(newOrder.begin(), newOrder.end(), city) == newOrder.end())
{
newOrder.push_back(city);
}
}
return DNA(newOrder, waypoints, number_of_drones);
}