Method Solution

pyvrp/cpp/Solution.cpp:166–217

}

Solution::Solution(ProblemData const &data, RandomNumberGenerator &rng)
    : neighbours_(data.numLocations(), std::nullopt)
{
    // Add all required and randomly selected optional clients.
    std::vector<size_t> clients;
    clients.reserve(data.numClients());
    for (size_t idx = data.numDepots(); idx != data.numLocations(); ++idx)
    {
        ProblemData::Client const &clientData = data.location(idx);
        if (clientData.required || rng.rand() < 0.5)
            clients.push_back(idx);
    }

    // Shuffle clients to create random routes.
    rng.shuffle(clients.begin(), clients.end());

    // Distribute clients evenly over the routes: the total number of
    // clients per vehicle, with an adjustment in case the division is not
    // perfect and there are not enough vehicles for single-client routes.
    auto const numVehicles = data.numVehicles();
    auto const numClients = clients.size();
    auto const perVehicle = std::max<size_t>(numClients / numVehicles, 1);
    auto const adjustment
        = numClients > numVehicles && numClients % numVehicles != 0;
    auto const perRoute = perVehicle + adjustment;
    auto const numRoutes = (numClients + perRoute - 1) / perRoute;

    std::vector<std::vector<Client>> routes(numRoutes);
    for (size_t idx = 0; idx != numClients; ++idx)
        routes[idx / perRoute].push_back(clients[idx]);

    std::vector<size_t> vehTypes;
    vehTypes.reserve(data.numVehicles());
    for (size_t vehType = 0; vehType != data.numVehicleTypes(); ++vehType)
    {
        auto const numAvailable = data.vehicleType(vehType).numAvailable;
        std::fill_n(std::back_inserter(vehTypes), numAvailable, vehType);
    }

    if (data.numVehicleTypes() > 1)
        // Shuffle vehicle types when there is more than one. This ensures
        // some additional diversity in the initial solutions, which
        // sometimes (e.g. with heterogeneous fleet VRP) matters for
        // consistent convergence.
        rng.shuffle(vehTypes.begin(), vehTypes.end());

    routes_.reserve(numRoutes);
    for (size_t idx = 0; idx != routes.size(); idx++)
        routes_.emplace_back(data, routes[idx], vehTypes[idx]);

    *this = Solution(data, routes_);
}

Solution::Solution(ProblemData const &data,
                   std::vector<std::vector<Client>> const &routes)