# 5th Homework

This homework is to be prepared in teams of two students. Find your partner on http://moodle.uni-graz.at/. Download hw_5.tar.gz and extract it. Then add your homework solutions to the files contained in the directory. Rename the directory according to the rules in the syllabus before submitting it as compressed archive. Don't forget to add the correct subject to the email when submitting.

Properly document the files you hand in to receive full credit. Each module (file) and function needs a docstring. The purpose of each function needs to be summarized as a single sentence and then, if required, your intent and the behavior of the function can be described in more detail.

Furthermore - provide doctests for all functions but main(). Each of the modules needs to include a main() function which calls the other functions and prints appropriate output to stdout.
main() itself must be called by the ifmain pattern at the end of the file.

1. Reading VRPTW instances (2 points)
Input files for vehicle routing problems generally include a depot and some customers. Both the depot and the customers are referred to as nodes. Storing vrptw instances as JSON files makes the meaning of the data easier to understand and eases the task of parsing such files.
Implement a function read_json(filename) that takes the name of a JSON file and returns all data as a dictionary. In this dictionary, the value containing the customers should be a list of dictionaries. Use the same keys as in the input file.
2. Distance matrix (2 points)
Write a function called calc_distance_matrix(node_list) that returns a matrix of euclidean distances between all given nodes. The first index to the matrix must refer to the row, the second to the column. All nodes' ids must correspond to the row/ column relevant to that node. The expected argument is a list that contains all nodes as dictionaries (the depot and all customers). The function needs to assert that the lowest id is 0, that all ids are unique and that they are consecutive (0, 1, 2, ...).
Building on the above, write a function that takes a customer dictionary, a list of customer dictionaries and a distance matrix as arguments. get_closest(.) should return the customer (dictionary) from the passed list that is closest to the given customer. Assert that the passed list is not empty.
Think about how many comparison operations are required by this function in relation to the number of customers "n" in the list?
First, write a detailed textual description of your heuristic. Explain the steps in detail so that it is enough to "translate" your description to Python. Store your description in a separate file called heuristic.txt. Implement the heuristic you came up with. Represent a route as a simple list of customer dictionaries. Write a function solve_vrp(.) that takes a dictionary with all required data as returned by the function in the first task. solve_vrp(.) must return a list of routes (that is, a list of customer lists where each customer still is a dictionary). Pay extra attention to the source code documentation of this function (the code can only say what you do, not why you do it).
Write an additional function print_routes(.) that takes a list of routes with customer dictionaries and prints the routes to stdout. The output format must be one route (truck) per line with all the customer ids on the route. The output should resemble the following
[0,  28,  12,  79,   3,  24,  80,   0]