% % Warehouse location problem % from P. van Hentenryck: Constraint Satisfaction in Logic Programming % % A factory has to deliver goods to it customers and has at its disposal % a finite number of locations where it is possible to build warehouses. % For the construction of a warehouse we have a cost, referred to as a % fixed cost. Also, there are variable costs for the transportation of % goods to the customers. These costs are variable since they are % dependent on the warehouse locations, because of the distance. The % problem is to determine the number and the locations of the warehouses % that minimize the (fixed and variable) costs. % % Code by Joachim Schimpf, IC-Parc % This solution uses a set to model the set of the warehouses % that are actually built. % % Sample run: % % ?- solve(Suppliers, Warehouses, N). % [1] % Found a solution with cost 890949 % [1, 5] % Found a solution with cost 745132 % [1, 7] % Found a solution with cost 737310 % [1, 8] % Found a solution with cost 730567 % Found no solution with cost 528983.0 .. 730566.0 % % Suppliers = [8, 1, 1, 1, 8, 8, 8, 8, 1, 8, 8, 1, 1, 1, 1, 1, 1, 1, 1, ...] % Warehouses = [1, 8] % N = 2 % Yes (0.03s cpu) % :- lib(ic). :- lib(ic_sets). :- lib(branch_and_bound). :- import minimize/2 from branch_and_bound. solve(SuppliedBys, BuiltWarehouses, NumBuiltWarehouses) :- % get the data setup_cost(SetupCost), supply_cost_matrix(SupplyCostMatrix), dim(SupplyCostMatrix, [NCustomers, NWareHouses]), % model intset(BuiltWarehouses, 1, NWareHouses), #(BuiltWarehouses, NumBuiltWarehouses), ( for(CustomerId, 1, NCustomers), foreach(SuppliedBy, SuppliedBys), foreach(CustCost, CustCosts), param(BuiltWarehouses,SupplyCostMatrix) do arg(CustomerId, SupplyCostMatrix, CustCostTable), element(SuppliedBy, CustCostTable, CustCost), SuppliedBy in BuiltWarehouses ), % objective TotalCost #= NumBuiltWarehouses*SetupCost + sum(CustCosts), % search minimize(( % try an increasing set of warehouses insetdomain(BuiltWarehouses, increasing, _, _), % try the smallest supply-costs first search(CustCosts, 0, smallest, indomain_min, complete, []), % label remaining supplier choices, if any search(SuppliedBys, 0, input_order, indomain, complete, []), writeln(BuiltWarehouses) ), TotalCost). % sample data with 19 warehouses and 20 customers supply_cost_matrix([]( [](68948, 68948, 68948, 68948, 35101, 68948, 24524, 24524, 35101, 68948, 26639, 35101, 68948, 68948, 68948, 68948, 68948, 26639, 35101), [](15724, 8634, 17850, 17850, 23520, 16433, 46200, 46200, 23520, 17850, 46200, 46200, 17850, 17850, 17850, 15724, 16433, 17850, 23520), [](24300, 24300, 12600, 24300, 60300, 24300, 60300, 60300, 60300, 60300, 60300, 60300, 31500, 31500, 31500, 24300, 24300, 60300, 60300), [](4852, 4852, 4852, 2817, 4852, 6104, 10486, 10486, 10486, 10486, 10486, 10486, 4852, 10486, 6104, 4852, 4539, 6104, 4852), [](40950, 40950, 78390, 31590, 16380, 40950, 40950, 31590, 40950, 78390, 31590, 31590, 29250, 78390, 40950, 31590, 40950, 29250, 28080), [](66330, 66330, 66330, 66330, 34650, 66330, 13860, 24750, 26730, 34650, 26730, 34650, 34650, 66330, 34650, 34650, 66330, 26730, 34650), [](39698, 39698, 39698, 39698, 15998, 39698, 14813, 8295, 20738, 39698, 14813, 15998, 20738, 39698, 20738, 20738, 39698, 15998, 15998), [](45895, 23975, 45895, 45895, 23975, 45895, 18495, 23975, 9590, 18495, 23975, 45895, 45895, 23975, 18495, 23975, 45895, 18495, 45895), [](5519, 4387, 9481, 9481, 9481, 4387, 5519, 9481, 4387, 2547, 9481, 9481, 5519, 4104, 4387, 4387, 5519, 5519, 9481), [](53433, 53433, 53433, 53433, 21533, 53433, 21533, 19938, 27913, 53433, 11165, 19938, 27913, 53433, 53433, 53433, 53433, 21533, 21533), [](47235, 47235, 47235, 47235, 19035, 47235, 24675, 19035, 47235, 47235, 17625, 9870, 24675, 47235, 47235, 47235, 47235, 24675, 19035), [](13125, 13125, 14175, 18375, 18375, 7350, 35175, 35175, 35175, 14175, 35175, 35175, 18375, 14175, 14175, 14175, 14175, 18375, 35175), [](138176, 159783, 181390, 181390, 239008, 166985, 469480, 469480, 239008, 239008, 469480, 469480, 181390, 181390, 181390, 166985, 166985, 239008, 239008), [](106993, 123723, 140454, 140454, 185069, 129300, 363528, 363528, 185069, 140454, 363528, 363528, 140454, 140454, 140454, 129300, 129300, 185069, 185069), [](55408, 47915, 62900, 62900, 82880, 57905, 162800, 162800, 82880, 82880, 162800, 162800, 62900, 62900, 62900, 57905, 57905, 62900, 82880), [](55786, 93864, 106556, 106556, 140403, 98095, 275792, 275792, 140403, 140403, 275792, 275792, 106556, 106556, 106556, 98095, 98095, 140403, 140403), [](16847, 16847, 19125, 19125, 25200, 17607, 49500, 49500, 25200, 19125, 49500, 49500, 19125, 19125, 19125, 17607, 19125, 25200, 25200), [](27780, 24308, 31253, 31253, 31253, 28938, 77553, 77553, 40513, 40513, 77553, 77553, 31253, 31253, 31253, 28938, 28938, 31253, 40513), [](4278, 3983, 4573, 4573, 4573, 4573, 5753, 5753, 5753, 4573, 9883, 9883, 4573, 4573, 4278, 2655, 4573, 4573, 5753), [](9672, 9005, 12340, 12340, 9672, 9672, 12340, 12340, 9672, 9672, 22345, 22345, 9672, 9672, 8671, 8671, 9672, 9672, 12340) )). setup_cost(50000).