Vehicle Routing Nearest Neighbor

Problem

Build vehicle routes from depot 0 with the nearest-neighbor rule and a capacity limit.

While customers remain, start at the depot and repeatedly drive to the nearest unvisited customer whose demand fits the remaining capacity (ties by smallest index); when no customer fits, return to the depot and start a new route. dist is a symmetric matrix, demands[c] is the demand of customer c, and capacity is the vehicle limit. Return [routes, total_distance] or [[], -1] when some demand exceeds capacity.

Hint

Greedy routing ignores global structure but is fast and easy to reason about.

Test cases

case 1

in: [[[0,2,9,10],[2,0,6,4],[9,6,0,8],[10,4,8,0]],3,[0,1,2,1]]

expected: [[[0,1,3,0],[0,2,0]],34]

case 2

in: [[[0,2,9,10],[2,0,6,4],[9,6,0,8],[10,4,8,0]],5,[0,2,2,2]]

expected: [[[0,1,3,0],[0,2,0]],34]

case 3

in: [[[0,2,9,10],[2,0,6,4],[9,6,8,0],[10,4,8,0]],3,[0,5,2,1]]

expected: [[],-1]

Starter codePython

def vehicle_route_nearest(dist, capacity, demands):
    # Your code here
    pass

3 test cases · run your code against them in the editor