Vans From One Depot

A bakery delivers to n shops from one depot with a fleet of identical vans (there are as many vans as you need). Each van leaves the depot, visits some shops and drives back. A van carries at most capacity crates, and a driver's shift allows a trip of at most shift units of distance. Shop c needs demand[c] crates and is visited by exactly one van.

Write plan_vans(inst) that returns a list of trips, each a list of shop indices in the order the van visits them (the depot is not listed). Every shop 0..n-1 appears in exactly one trip. The total distance of all trips should be as small as you can make it. Distances are straight lines (math.dist).

inst is a dict:

• "depot": the (x, y) of the depot
• "customers": a list of n shop positions (x, y)
• "demand": a list of n crate counts
• "capacity": the most crates one van carries (100 in the tests)
• "shift": the longest allowed trip, depot to depot (2000 in the tests)

The tests build their instances with van_orders(n, seed). route_length(inst, trip) measures one trip and plan_length(inst, trips) the total. All three are available in your code.

How this problem is scored

The checker makes its own plan, the sweep plan: it sorts the shops by their direction from the depot, counter-clockwise starting due east (closer shops first on a tie). A van takes the shops in that order until the next shop would overload it or make its trip longer than the shift; then the next van starts. Finally each trip is shortened by reversing a stretch of it while that helps. Your plan passes if every trip respects both limits and the total is no longer than the sweep plan. Its quality (0 to 100) is the share of the gap between the sweep plan and the best plan we know that you close.

Examples

Input:  inst = {"depot": (500, 500),
                "customers": [(500, 800), (800, 500), (500, 200), (200, 500)],
                "demand": [40, 30, 50, 20], "capacity": 100, "shift": 2000}
Output: [[1, 0, 3], [2]]   (lengths 1448.5 and 600.0: total 2048.5)
Explanation: going round from due east the shops come in the order 1, 0, 3, 2. The first
             van takes 1, 0 and 3 (30 + 40 + 20 = 90 crates); shop 2 would make 140, so a
             second van takes it. [[0, 1, 2, 3]] is not allowed: 140 crates in one van.
             [[0, 1], [2, 3]] is also 2048.5; [[0, 2], [1, 3]] is 2400.0.

Input:  inst = van_orders(40, 3)
Output: any valid plan no longer than the sweep plan (6981.1 here); lower totals score higher

Constraints

• 12 <= n <= 100, coordinates from 0 to 1000, 1 <= demand[c] <= 25
• Every shop on its own trip fits the shift, so a valid plan always exists.
• 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

• Split customers into trips that respect both a load limit and a length limit
• Improve the order inside a trip and the choice of trip for each customer
• Keep every hard limit satisfied after every move