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.
    Name the module: vrptw_reader.py
  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, ...).
    Feel free to write any number of additional functions (as you deem appropriate) to help you getting this task done.
    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?
    Name the module: vrptw_reader.py
  3. Simple VRP solver (5 points)
    Figure out any very simple heuristic to put all the customers on a series of routes. Each route starts and ends at the depot and is serviced by a single truck. Each customer must be on exactly one route. The goal of the heuristic is to assign the customers to these trucks while using as little trucks as possible. None of the trucks is allowed to exceed its capacity or range. The capacity and the customer's demands use the same units. The range uses the same distance units as the distance matrix.
    Don't think out a complicated method as you'll have to implement it (however... assigning one customer per truck is too simple).
    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]
    [0,  11,  19,  49,  48,   0]
    ...
    
    and end with a final newline. Use as many additional functions as you deem useful.
    Name the program file: vrp_solver.py