Problem 615055 · hard · Level 06 Heuristics & Optimization

Regional Depots for a Grocery Chain

gauntlet · facility location · local search · capacity constraints · greedy assignment

A grocery chain has m possible depot sites and n stores. Opening depot i costs open_cost[i] per week and lets it ship at most capacity[i] pallets. Store j needs demand[j] pallets and is supplied by exactly one depot; supplying it from depot i costs ship[i][j]. Stores that sell fresh goods cannot be supplied from far away: for them some entries of ship are None, and those depots may not supply them.

Write choose_depots(inst) that returns supplier, a list of length n where supplier[j] is the depot that supplies store j. A depot is open exactly when it supplies at least one store. The weekly cost is the opening cost of every open depot plus every store's supply cost; make it as low as you can. The loads of each depot must stay within its capacity.

inst is a dict with the keys "open_cost", "capacity", "demand" and "ship" (and "sites" and "stores", the map positions, only for drawing). The tests build their maps with depot_sites(m, n, seed), and network_cost(inst, supplier) computes the weekly cost (it does not check the rules). Both are available in your code.

How this problem is scored

The checker plans store by store: in index order, each store goes to the depot with enough room left that adds the least cost (its supply cost, plus the opening cost if that depot is not open yet; the smaller depot number on a tie). Your plan passes if it is valid and costs no more. Its quality (0 to 100) is the share of the gap between that plan and the optimum (proved by an exact solver) that you close.

Examples

Input:  inst = {"open_cost": [60, 100], "capacity": [40, 60], "demand": [20, 25, 15],
                "ship": [[5, 50, None], [30, 10, 5]]}
Output: [1, 1, 1]   (100 + 30 + 10 + 5 = 145, the optimum)
Explanation: store by store, store 0 opens depot 0 (60 + 5 = 65 beats 100 + 30).
             Store 1 does not fit in depot 0 any more (25 > 20 pallets left), so depot 1
             opens as well, and store 2 (fresh goods, depot 0 too far) joins depot 1:
             60 + 100 + 5 + 10 + 5 = 180. Depot 1 alone can carry all 60 pallets.

Input:  inst = depot_sites(20, 80, 7)
Output: any valid plan costing no more than store by store (79410 here)

Constraints

  • 10 <= m <= 40 depots, 40 <= n <= 150 stores, demands 5 to 40 pallets
  • Every store has at least one depot allowed to supply it, and the total capacity is several times the total demand.
  • Each test must finish in well under a second in your browser. Limit your loops by a number of rounds, not by the clock, so the result is the same on every run.

Goals

  • Decide which depots to open and which depot supplies each store, together
  • Assign stores to depots without breaking capacities or delivery limits
  • Search over the set of open depots with add and drop moves
Starting Python…