Discrete : add 05-vehicle-routing assignment

1 files changed, 83 insertions, 0 deletions

diff --git a/05-vehicle-routing/solver.py b/05-vehicle-routing/solver.py
new file mode 100644
index 0000000..98b1ab7
--- /dev/null
+++ b/05-vehicle-routing/solver.py
@@ -0,0 +1,83 @@
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+
+import math
+
+def length(customer1, customer2):
+    return math.sqrt((customer1[1] - customer2[1])**2 + (customer1[2] - customer2[2])**2)
+
+def solveIt(inputData):
+    # Modify this code to run your optimization algorithm
+
+    # parse the input
+    lines = inputData.split('\n')
+
+    parts = lines[0].split()
+    customerCount = int(parts[0])
+    vehicleCount = int(parts[1])
+    vehicleCapacity = int(parts[2])
+    depotIndex = 0
+
+    customers = []
+    for i in range(1, customerCount+1):
+        line = lines[i]
+        parts = line.split()
+        customers.append((int(parts[0]), float(parts[1]),float(parts[2])))
+
+    # build a trivial solution
+    # assign customers to vehicles starting by the largest customer demands
+
+    vehicleTours = []
+
+    customerIndexs = set(range(1, customerCount))  # start at 1 to remove depot index
+    
+    for v in range(0, vehicleCount):
+        # print "Start Vehicle: ",v
+        vehicleTours.append([])
+        capacityRemaining = vehicleCapacity
+        while sum([capacityRemaining >= customers[ci][0] for ci in customerIndexs]) > 0:
+            used = set()
+            order = sorted(customerIndexs, key=lambda ci: -customers[ci][0])
+            for ci in order:
+                if capacityRemaining >= customers[ci][0]:
+                    capacityRemaining -= customers[ci][0]
+                    vehicleTours[v].append(ci)
+                    # print '   add', ci, capacityRemaining
+                    used.add(ci)
+            customerIndexs -= used
+
+    # checks that the number of customers served is correct
+    assert sum([len(v) for v in vehicleTours]) == customerCount - 1
+
+    # calculate the cost of the solution; for each vehicle the length of the route
+    obj = 0
+    for v in range(0, vehicleCount):
+        vehicleTour = vehicleTours[v]
+        if len(vehicleTour) > 0:
+            obj += length(customers[depotIndex],customers[vehicleTour[0]])
+            for i in range(0, len(vehicleTour) - 1):
+                obj += length(customers[vehicleTour[i]],customers[vehicleTour[i + 1]])
+            obj += length(customers[vehicleTour[-1]],customers[depotIndex])
+
+    # prepare the solution in the specified output format
+    outputData = str(obj) + ' ' + str(0) + '\n'
+    for v in range(0, vehicleCount):
+        outputData += str(depotIndex) + ' ' + ' '.join(map(str,vehicleTours[v])) + ' ' + str(depotIndex) + '\n'
+
+    return outputData
+
+
+import sys
+
+if __name__ == '__main__':
+    if len(sys.argv) > 1:
+        fileLocation = sys.argv[1].strip()
+        inputDataFile = open(fileLocation, 'r')
+        inputData = ''.join(inputDataFile.readlines())
+        inputDataFile.close()
+        print 'Solving:', fileLocation
+        print solveIt(inputData)
+    else:
+
+        print 'This test requires an input file.  Please select one from the data directory. (i.e. python solver.py ./data/vrp_5_4_1)'
+