Class SearchSpace

pyvrp/cpp/search/SearchSpace.h:22–116

* SearchSpace(data: ProblemData, neighbours: list[list[int]]) * * Manages a search space for the local search. The search space is granular, * around the given neighbourhood, and uses the concept of promising clients * to determine which client's neighbourhoods to search. It can also be used * to define a (randomised) search ordering for clients, routes, and vehicle * types. */

 * types.
 */
class SearchSpace
{
public:
    using Neighbours = std::vector<std::vector<size_t>>;

private:
    // Neighborhood restrictions: list of nearby clients for each client (size
    // numLocations, but nothing is stored for the depots!).
    Neighbours neighbours_;

    // Tracks clients that can likely be improved by local search operators.
    DynamicBitset promising_;

    // Client order used for node-based search.
    std::vector<size_t> clientOrder_;

    // Route order used for route-based search.
    std::vector<size_t> routeOrder_;

    // Vehicle type order - pairs of [veh type, offset] - used for empty route
    // search.
    std::vector<std::pair<size_t, size_t>> vehTypeOrder_;

public:
    SearchSpace(ProblemData const &data, Neighbours neighbours);

    /**
     * Set the neighbourhood structure of this search space. For each client,
     * the neighbourhood structure is a vector of nearby clients. Depots have
     * no nearby clients.
     */
    void setNeighbours(Neighbours neighbours);

    /**
     * Returns the current neighbourhood structure.
     */
    Neighbours const &neighbours() const;

    /**
     * Returns the vector of neighbours for a given client.
     */
    std::vector<size_t> const &neighboursOf(size_t client) const;

    /**
     * Returns whether the given client is a promising evaluation candidate.
     */
    bool isPromising(size_t client) const;

    /**
     * Marks the given client as promising.
     */
    void markPromising(size_t client);

    /**
     * Convenient overload for route nodes. Since this is typically used during
     * insert and removals, this method marks the given node and its direct
     * client neighbours as promising. The node must currently be in a route.
     * Does not mark depots.