Logistics

(Main file name: logistics)

John is a truck driver. He needs to deliver a truckload of packages to different destination cities. In each city other truck drivers can help transport part of the packages with their trucks. So nobody is required to solve the traveling salesman problem. Also, no driver is required to return to his starting city. Nevertheless, John has to pay for the distances the trucks travel, and he wants to find routes for himself and the helpers such that the total travel distance is minimized.

The problem can be formulated as a graph problem as follows: Given an undirected weighted graph, a starting vertex, and a set of destination vertices, find a subgraph of the graph that has the minimum cost and covers the starting vertex and all of the destination vertices.

For example, for graph (a) shown below, assume the starting vertex is 1, and the set of destination vertices is {5,6}, then graph (b) shows a minimum covering tree.

- One fact of the form graph_size(N), which specifies the number of vertices N (4 ≤ N ≤ 20).
- One fact of the form start(V), which specifies the starting vertex (1 ≤ V ≤ N).
- A relation that consists of facts of the form dest(V), which specifies a destination vertex V (1 ≤ V ≤ N).
- A relation that consists of facts of the form edge(V1,V2,C), which indicates an edge between V1 and V2 with travel cost C (1 ≤ V1, V2 ≤ N, 1 ≤ C ≤ 100).

LP Input | Minizinc Input | Output |

graph_size(6). start(1). dest(6). edge(1,2,4). edge(1,3,2). edge(2,3,5). edge(2,4,10). edge(3,5,3). edge(4,5,4). edge(4,6,11). | graph_size = 6; start = 1; n_dests = 1; dest = [6]; n_edges = 7; from = [1,1,2,2,3,4,4]; to = [2,3,3,4,5,5,6]; cost = [4,2,5,10,3,4,11]; | min_cost(20). |

graph_size(6). start(1). dest(5). dest(6). edge(1,2,4). edge(1,3,2). edge(2,3,5). edge(2,4,10). edge(3,5,3). edge(4,5,4). edge(4,6,11). | graph_size = 6; start = 1; n_dests = 2; dest = [5,6]; n_edges = 7; from = [1,1,2,2,3,4,4]; to = [2,3,3,4,5,5,6]; cost = [4,2,5,10,3,4,11]; | min_cost(20). |

graph_size(6). start(1). dest(5). dest(6). edge(1,2,6). edge(1,3,1). edge(1,4,5). edge(2,3,5). edge(2,5,3). edge(3,4,5). edge(3,5,6). edge(3,6,4). edge(4,6,2). | graph_size = 6; start = 1; n_dests = 2; dest = [5,6]; n_edges = 9; from = [1,1,1,2,2,3,3,3,4]; to = [2,3,4,3,5,4,5,6,6]; cost = [6,1,5,5,3,5,6,4,2]; | min_cost(11). |