Locating Distribution Centers

Overview

This project, implemented in C, uses an exhaustive search approach alongside Dijkstra’s algorithm to optimise the placement of distribution centers such that all cities in a logistics network are within a specified distance from the closest service point.

If multiple solutions exist with the same minimum number of placement, the program outputs all minimal solutions in alphabetical order of the distribution centres.

Compilation

Compile the program using make or the following commands:

gcc -c wgraph.c
gcc -c logistics.c
gcc -o logistics wgraph.o logistics.o

General Usage

Run the program with:

./logistics

The program will ask for a positive number n, and then prompt the user to input n city names. An example input is:

$ ./logistics
Enter the number of cities on the distribution network: 3
Berlin
Frankfurt
Hamburg

Next, the program will ask for the number of roads, m, and then prompt the user to input m roads. Each road requires the name of a city (from), the name of another city (to), and the distance (in km). An example input is:

Enter the number of roads: 2
Enter the name of a city: Hamburg
Enter the name of a city: Frankfurt
Enter the distance: 492
Enter the name of a city: Berlin
Enter the name of a city: Hamburg
Enter the distance: 289

Finally, the program will prompt for the required maximum distance to a distribution center:

Enter the required maximum distance: 350

An example output is:

Hubs: Berlin
Routes:
Berlin: Berlin 0
Frankfurt: Berlin - Hamburg - Frankfurt 781
Hamburg: Berlin - Hamburg 289

Test Cases

To provide test inputs to the program, use:

./logistics < data/test01.txt

A collection of 23 test cases is available in the data folder.

Limitations

• Only one distribution center can be placed in each city.
• City names are limited to 31 characters and do not contain spaces.
• City names are input in alphabetical order with no duplicates.
• Each road connects two distinct cities, and distances are positive integers.
• No two roads share the same start and end points.
• No city is equidistant from two distribution centers, and no two shortest routes from a hub to a city are identical.
• All numeric inputs have to be non-negative integers.

Implementation

1. The program begins by gathering the necessary inputs.

2. It then constructs a weighted directed graph representing the cities and roads.

3. The program searches for the optimal distribution center arrangement, starting with one center and increasing the number as needed. For each number of centers, it evaluates all possible city combinations.

4. For each combination, Dijkstra's algorithm is employed to compute the shortest routes from the potential distribution centers to all other cities, ensuring all cities fall within the maximum allowed distance.

5. If a valid arrangement is found, it is stored as a potential solution, and the program continues evaluating other arrangements with the same number of centers.

6. After identifying all valid arrangements with the minimum number of centers, the program sorts these solutions alphabetically by city names and prints all optimal solutions.

7. The program concludes by cleaning up memory usage and terminating.

Complexity

This project presents a straightforward attempt at the problem with limited focus on performance optimisation.

Time Complexity: O(2^n * n^2)

• The program generates all possible combinations of cities as potential distribution centers.
• In the worst case, it may need to check all subsets of cities, which is 2^n (where n is the number of cities).
• For each combination, it runs Dijkstra's algorithm, which has a time complexity of O(n^2) in this implementation.
• Therefore, the overall time complexity is O(2^n * n^2).

Space Complexity: O(n^2)

• The program uses several arrays of size n:
  • dist[], pred[], source[] each use O(n) space
  • The graph representation (adjacency matrix) uses O(n^2) space
• The solutions array can potentially store all combinations, but in practice, it only stores the minimal solutions, which is typically much smaller than 2^n.
• The recursive call stack in generateCombinations() can go up to depth n in the worst case.
• Therefore, the dominant factor in space complexity is the graph representation, making it O(n^2).

Additional Notes:

• The time complexity makes this algorithm impractical for large numbers of cities (e.g., more than 20-30).
• For larger datasets, heuristic algorithms or approximation methods would be more suitable.
• The space complexity is more manageable, allowing the program to handle larger numbers of cities before running out of memory.
• The actual performance may vary depending on the specific input and how quickly minimal solutions are found.