0

I'm programming Clarke and Wright's savings algorithm to design vehicle routes from a depot to a set of customers. Right now, the code gets stuck in the final if statement if none of the conditions is met. What I want is that if ALL the cust_pairs have been checked and there is NO unserved cust_pair left which is either at the start or end of the previous route The code should break out of the second for loop. And then, go back to the first for loop to find a customer pair for starting a new route.

I've tried some things with 'break' and 'continue' but can not get it working.

def inPrevious(new,existing):
    start = existing[0]
    end = existing[len(existing)-1]
    if new == start:
        return 1
    elif new == end:
        return 0
    else:
        return -1

idx = -1

while not(allCustomersServed):

    for c in cust_pairs: 

        # find initial cust_pair with high savings
        idx += 1
        routes[idx] = ([c[0],c[1]]) 
        break

    #finding a cust that is either at the start or end of previous route

    for c in cust_pairs:
        # find feasible cust_pair that is either at the start or end of previous route    

        res = inPrevious(c[0], routes[idx])
        if res == 0:          
             # append c[1] to route          
        elif res == 1:
             # insert c[1] at position 0 in route   
        elif res == -1:
            res = inPrevious(c[1], routes[idx])
            if res == 0:
                # append c[0] to route   
            elif res == 1:
                # insert c[0] at position 0 in route
Marc
  • 29
  • 2
  • 1
    Why does the first for loop break after only one iteration? – Sam Chats Sep 26 '19 at 13:41
  • 1
    Could you provide a [MCVE](https://stackoverflow.com/help/minimal-reproducible-example)? Explain us what is `cust_pairs` exactly. Seems to me that `inPrevious` always return 0, 1 o -1. So you should always get a match. – Valentino Sep 26 '19 at 13:42
  • @Valentino cust_pairs is a sorted list with pairs of customers who are sorted based on the saving you get when you combine them in one route. inPrevious indeed always returns 0, 1, or -1. But if it returns -1 it means that the cust_pair does not have a customer in it which is either the starting or ending point of the current route. I check this using the if statements in the second for loop. However, if all cust_pairs have been checked and no match has been found, the code should get back to the first for loop in order to find the starting point for a new route. – Marc Sep 26 '19 at 13:51
  • @SamChats that's because in the first for loop, the starting point for a new route is found and using the second for loop, customers are iteratively added to the route if feasible. – Marc Sep 26 '19 at 13:52
  • 2
    I strongly recommend not to use `break` or `continue` to control nested loops, even if the language supports it (e.g., bash does). Put the loop into a function and return from it. With that technique, you can handle arbitrarily deeply nested structures in a readable fashion easily. See also https://stackoverflow.com/questions/653509/breaking-out-of-nested-loops – pasbi Sep 26 '19 at 14:12

0 Answers0