src/gsh.cpp
/*
 * This assumes that TPP instance is uncapacitated, i.e. each supplier (market)
 * has unlimited amount of a product or does not offer it at all.
 */
This assumes that TPP instance is uncapacitated, i.e. each supplier (market)
has unlimited amount of a product or does not offer it at all.
This assumes that TPP instance is uncapacitated i . e . each supplier ( market ) has unlimited amount of a product or does not offer it at all .
TPP::Solution calc_gsh_solution(const TPP::Instance& instance) {
    CHECK_F(instance.is_capacitated_ == false,
            "Uncapacitated TPP instance required");
    LOG_SCOPE_F(INFO, "calc_gsh_solution");
    int super_price = -1;
    const auto market_product_prices = calc_market_product_prices(instance, &super_price);
    TPP::Solution sol(instance);
    int max_products = 0;
    int min_total_cost = numeric_limits<int>::max();
    size_t chosen_market_id = 0;
    size_t market_id = 0;
    for (const auto &prices: market_product_prices) {
        int products_available = 0;
        int total_cost = 0;
        for (auto price : prices) {
            if (price != super_price) {
                ++products_available;
                total_cost += price;
            }
        }
        if (products_available > max_products
            || (products_available == max_products
                && min_total_cost > total_cost)) {
            max_products = products_available;
            min_total_cost = total_cost;
            chosen_market_id = market_id;
        }
        ++market_id;
    }
    LOG_F(INFO, "market: %zu, max_products: %d, min_total_cost: %d",
          chosen_market_id, max_products, min_total_cost);
    vector<size_t> unselected(instance.dimension_ - 1);
    iota(begin(unselected), end(unselected), 1u);  
    unselected.erase(find(begin(unselected), end(unselected), chosen_market_id));
    sol.push_back_market(chosen_market_id);
    vector<int> prices_in_sol{ market_product_prices.at(chosen_market_id) };
    auto improvement_found = false;
    do {
        improvement_found = false;
        auto best_i = 0u;
        auto best_h = 0u;
        auto best_savings = 0;
        auto i = sol.route_.back();
        for (auto j : sol.route_) {
            const auto c_ij = instance.edge_weights_.at(i).at(j);
            for (auto h : unselected) {
                auto c_ih = instance.edge_weights_.at(i).at(h);
                auto c_hj = instance.edge_weights_.at(h).at(j);
                const auto &h_prices = market_product_prices.at(h);
                auto diff_sum = Vec::calc_diff_max_0_sum(prices_in_sol, h_prices);
                auto savings = c_ij - c_ih - c_hj + diff_sum;
                if (savings > best_savings) {
                    best_i = i;
                    best_h = h;
                    best_savings = savings;
                }
            }
            i = j;
        }
        if (best_savings > 0) {
            LOG_F(INFO, "Savings found: %d for h: %u after i: %d", best_savings, best_h, best_i);
            improvement_found = true;
            auto it = find(begin(sol.route_), end(sol.route_), best_i);
            ++it;
            int index = distance(begin(sol.route_), it);
            sol.insert_market_at_pos(best_h, static_cast<size_t>(index));
            unselected.erase(find(begin(unselected), end(unselected), best_h));
            const auto &h_prices = market_product_prices.at(best_h);
            for (auto k =0u; k < instance.product_count_; ++k) {
                prices_in_sol.at(k) = min(prices_in_sol.at(k), h_prices.at(k));
            }
        }
    } while(improvement_found);
    assert(is_solution_valid(instance, sol.route_));
    LOG_F(INFO, "Autocalculated sol cost: %d", sol.cost_);
    auto cost = calc_solution_cost(instance, sol.route_);
    LOG_F(INFO, "Final GSH sol cost: %d", cost);
    LOG_F(INFO, "Final GSH sol: %s", container_to_string(sol.route_).c_str());
    sol.cost_ = cost;
    return sol;
}
TPP :: Solution calc_gsh_solution ( const TPP :: Instance & instance ) { CHECK_F ( instance . is_capacitated_ == false , " " ) ; LOG_SCOPE_F ( INFO , " " ) ; int super_price = -1 ; const auto market_product_prices = calc_market_product_prices ( instance , & super_price ) ; TPP :: Solution sol ( instance ) ; int max_products = 0 ; int min_total_cost = numeric_limits < int > :: max ( ) ; size_t chosen_market_id = 0 ; size_t market_id = 0 ; for ( const auto & prices : market_product_prices ) { int products_available = 0 ; int total_cost = 0 ; for ( auto price : prices ) { if ( price != super_price ) { ++ products_available ; total_cost += price ; } } if ( products_available > max_products || ( products_available == max_products && min_total_cost > total_cost ) ) { max_products = products_available ; min_total_cost = total_cost ; chosen_market_id = market_id ; } ++ market_id ; } LOG_F ( INFO , " " , chosen_market_id , max_products , min_total_cost ) ; vector < size_t > unselected ( instance . dimension_ - 1 ) ; iota ( begin ( unselected ) , end ( unselected ) , 1u ) ; unselected . erase ( find ( begin ( unselected ) , end ( unselected ) , chosen_market_id ) ) ; sol . push_back_market ( chosen_market_id ) ; vector < int > prices_in_sol { market_product_prices . at ( chosen_market_id ) } ; auto improvement_found = false ; do { improvement_found = false ; auto best_i = 0u ; auto best_h = 0u ; auto best_savings = 0 ; auto i = sol . route_ . back ( ) ; for ( auto j : sol . route_ ) { const auto c_ij = instance . edge_weights_ . at ( i ) . at ( j ) ; for ( auto h : unselected ) { auto c_ih = instance . edge_weights_ . at ( i ) . at ( h ) ; auto c_hj = instance . edge_weights_ . at ( h ) . at ( j ) ; const auto & h_prices = market_product_prices . at ( h ) ; auto diff_sum = Vec :: calc_diff_max_0_sum ( prices_in_sol , h_prices ) ; auto savings = c_ij - c_ih - c_hj + diff_sum ; if ( savings > best_savings ) { best_i = i ; best_h = h ; best_savings = savings ; } } i = j ; } if ( best_savings > 0 ) { LOG_F ( INFO , " " , best_savings , best_h , best_i ) ; improvement_found = true ; auto it = find ( begin ( sol . route_ ) , end ( sol . route_ ) , best_i ) ; ++ it ; int index = distance ( begin ( sol . route_ ) , it ) ; sol . insert_market_at_pos ( best_h , static_cast < size_t > ( index ) ) ; unselected . erase ( find ( begin ( unselected ) , end ( unselected ) , best_h ) ) ; const auto & h_prices = market_product_prices . at ( best_h ) ; for ( auto k = 0u ; k < instance . product_count_ ; ++ k ) { prices_in_sol . at ( k ) = min ( prices_in_sol . at ( k ) , h_prices . at ( k ) ) ; } } } while ( improvement_found ) ; assert ( is_solution_valid ( instance , sol . route_ ) ) ; LOG_F ( INFO , " " , sol . cost_ ) ; auto cost = calc_solution_cost ( instance , sol . route_ ) ; LOG_F ( INFO , " " , cost ) ; LOG_F ( INFO , " " , container_to_string ( sol . route_ ) . c_str ( ) ) ; sol . cost_ = cost ; return sol ; }
This assumes that TPP instance is uncapacitated, i.e.
This assumes that TPP instance is uncapacitated i . e .
// Find a market with most products at the lowest total price // 1, 2, ..., dimension - 1 // Remove chosen_market_id // [i] = price for product i // Look for customer h that can be inserted between (i, j) //auto diff_sum = 0; //for (auto k = 0ul, end = prices_in_sol.size(); k < end; ++k) { //diff_sum += max(0, prices_in_sol.at(k) - h_prices.at(k)); //} // route.insert(pos, best_h);