Van Trips from the Depot

A bakery delivers crates of bread from its depot with one small van. Customer c needs demand[c] crates, and the van holds at most capacity crates, so it makes several trips: each trip leaves the depot, visits some customers and drives back. Every customer is served by exactly one trip, and the crates of a trip must fit in the van. Plan the trips so the total distance is as short as possible.

Write plan_trips(points, demand, capacity) that returns the trips as a list of lists of customer numbers, in visiting order, for example [[3, 1], [2, 5, 4]]. points[0] is the depot and points[1..n] are the customers ((x, y) on a 1000 × 1000 map); distances are straight lines. Do not write the depot into the trips. Use as many trips as you like.

The tests build their maps with depot_map(n, seed), which returns (points, demand), and trips_length(points, trips) measures a plan. Both are available in your code.

How this problem is scored

The checker makes its own plan: from the depot the van always drives to the nearest customer whose crates still fit (the lowest number on a tie) and returns to the depot when none fits, starting a new trip; then each trip is shortened on its own by reversing stretches of it while that helps. Your plan passes if it is valid and no longer than that one. Its quality (0 to 100) says how much of the gap between that plan and the best plan we know you close.

Examples

Input:  points, demand = depot_map(20, 1); capacity = 25
Output: a list of trips such as [[7, 12, 3], [5, 18, 9, 1], ...]
        the checker's plan is 6669.6 long; the best known is 5319.2

Constraints

• 20 <= n <= 120 customers, 1 <= demand[c] <= 9, 25 <= capacity <= 40
• Each test must finish in well under a second in your browser. Limit your loops by a number of steps, not by the clock, and use random (the tests seed it) for random choices.

Goals

• Improve several routes at once with moves that carry customers between them
• Keep every intermediate solution feasible (capacity) while searching
• Escape the local optimum of a construct-then-2-opt heuristic