<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>10.2 Example: Locating Warehouses</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node44.html#section.bab.align"><< Prev</A></TD><TD><A href="node43.html">- Up -</A></TD></TR></TABLE><DIV id="section.bab.warehouses"><H2><A name="section.bab.warehouses">10.2 Example: Locating Warehouses</A></H2><P> This example features branch and bound to compute an optimal solution, a non-trivial distribution strategy and symbolic constraints. </P><DIV class="unnumbered"><H3><A name="label122">Problem Specification</A></H3><P>Assume a company which wants to construct warehouses to supply stores with goods. Each warehouse to be constructed would have a certain capacity defining the largest number of stores which can be supplied by this warehouse. For the construction of a warehouse we have fixed costs. The costs for transportation from a warehouse to a store vary depending on the location of the warehouse and the supplied store. The aim is to determine which warehouses should be constructed and which stores should be supplied by the constructed warehouses such that the overall costs are minimized. </P><P>We assume the fixed costs of building a warehouse to be 50. We furthermore assume 5 warehouses W1 through W5 and 10 stores Store1 through Store10. The capacities of the warehouses are shown in <A href="node45.html#table.bab.caps">Figure 10.2</A>. The costs to supply a store by a warehouse are shown in <A href="node45.html#table.bab.costs">Figure 10.3</A>. </P><DIV id="table.bab.caps"><HR><P><A name="table.bab.caps"></A></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TD><P> </P></TD><TD><P><IMG alt="W_1" src="latex231.png"></P></TD><TD><P><IMG alt="W_2" src="latex232.png"></P></TD><TD><P><IMG alt="W_3" src="latex233.png"></P></TD><TD><P><IMG alt="W_4" src="latex234.png"></P></TD><TD><P><IMG alt="W_5" src="latex235.png"></P></TD></TR><TR valign="top"><TD><P>Capacity</P></TD><TD><P>1</P></TD><TD><P>4</P></TD><TD><P>2</P></TD><TD><P>1</P></TD><TD><P>3</P></TD></TR></TABLE><P class="caption"><STRONG>Figure 10.2:</STRONG> Capacities of warehouses.</P><HR></DIV><P> </P><DIV id="table.bab.costs"><HR><P><A name="table.bab.costs"></A></P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TD><P> </P></TD><TD><P><IMG alt="W_1" src="latex231.png"></P></TD><TD><P><IMG alt="W_2" src="latex232.png"></P></TD><TD><P><IMG alt="W_3" src="latex233.png"></P></TD><TD><P><IMG alt="W_4" src="latex234.png"></P></TD><TD><P><IMG alt="W_5" src="latex235.png"></P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_1" src="latex236.png"></P></TD><TD><P>36</P></TD><TD><P>42</P></TD><TD><P>22</P></TD><TD><P>44</P></TD><TD><P>52</P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_2" src="latex237.png"></P></TD><TD><P>49</P></TD><TD><P>47</P></TD><TD><P>134</P></TD><TD><P>135</P></TD><TD><P>121</P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_3" src="latex238.png"></P></TD><TD><P>121</P></TD><TD><P>158</P></TD><TD><P>117</P></TD><TD><P>156</P></TD><TD><P>115</P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_4" src="latex239.png"></P></TD><TD><P>8</P></TD><TD><P>91</P></TD><TD><P>120</P></TD><TD><P>113</P></TD><TD><P>101</P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_5" src="latex240.png"></P></TD><TD><P>77</P></TD><TD><P>156</P></TD><TD><P>98</P></TD><TD><P>135</P></TD><TD><P>11</P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_6" src="latex241.png"></P></TD><TD><P>71</P></TD><TD><P>39</P></TD><TD><P>50</P></TD><TD><P>110</P></TD><TD><P>98</P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_7" src="latex242.png"></P></TD><TD><P>6</P></TD><TD><P>12</P></TD><TD><P>120</P></TD><TD><P>98</P></TD><TD><P>93</P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_8" src="latex243.png"></P></TD><TD><P>20</P></TD><TD><P>120</P></TD><TD><P>25</P></TD><TD><P>72</P></TD><TD><P>156</P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_9" src="latex244.png"></P></TD><TD><P>151</P></TD><TD><P>60</P></TD><TD><P>104</P></TD><TD><P>139</P></TD><TD><P>77</P></TD></TR><TR valign="top"><TD><P><IMG alt="{\it Store}_{10}" src="latex245.png"></P></TD><TD><P>79</P></TD><TD><P>107</P></TD><TD><P>91</P></TD><TD><P>117</P></TD><TD><P>154</P></TD></TR></TABLE><P class="caption"><STRONG>Figure 10.3:</STRONG> Costs for supplying stores.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label123">Model</A></H3><P>We assume that the costs are given in the matrix <IMG alt="CostMatrix" src="latex246.png"> defined by <A href="node45.html#table.bab.costs">Figure 10.3</A>. For the model of this problem we introduce the following variables.</P><P></P><UL><LI><P><IMG alt="{\it Open}_i, 1 \leq i \leq 5" src="latex247.png">, with domain <IMG alt="0\#1" src="latex169.png"> such that <IMG alt="{\it Open}_i=1" src="latex248.png"> if warehouse <IMG alt="W_i" src="latex249.png"> does supply at least one store. </P></LI><LI><P><IMG alt="{\it Supplier}_i, 1 \leq i \leq 10" src="latex250.png">, with domain <IMG alt="1\#5" src="latex251.png"> such that <IMG alt="{\it Supplier}_i = j" src="latex252.png"> if store <IMG alt="{\it Store_i}" src="latex253.png"> is supplied by warehouse <IMG alt="W_j" src="latex254.png">. </P></LI><LI><P><IMG alt="{\it Cost}_i, 1 \leq i \leq 10" src="latex255.png">, such that the domain of <IMG alt="{\it
Cost}_i" src="latex256.png"> is defined by the row <IMG alt="{\it CostMatrix}_i" src="latex257.png">. The variable <IMG alt="{\it
Cost}_i" src="latex256.png"> denotes the costs of supplying store <IMG alt="{\it Store}_i" src="latex258.png"> by warehouse <IMG alt="W_{{\it Supplier}_i}" src="latex259.png">, i. e., <IMG alt="{\it Cost}_i = {\it
CostMatrix}_{i,{\it Supplier}_i}" src="latex260.png">.</P></LI></UL><P> </P><P>We have the additional constraint that the capacity of the warehouses must not be exceeded. To this aim we introduce auxiliary variables <IMG alt="{\it
Supplies}_{i,j}" src="latex261.png"> with the domain <IMG alt="0\#1" src="latex169.png"> as follows. </P><BLOCKQUOTE><P><IMG alt="\forall i \in \{1,\ldots,5\} \forall j \in \{1,\ldots, 10\}:\ ({\it Supplies}_{i,j} = 1)
\leftrightarrow ({\it Supplier_j} = i)" src="latex262.png"></P></BLOCKQUOTE><P> The capacity constraints can then be stated with </P><BLOCKQUOTE><P><IMG alt="\forall i \in \{1, \ldots, 5\}:\ {\it Cap}_i \geq
\sum\limits_{j=1}^{10}{\it Supplies}_{i,j}" src="latex263.png"></P></BLOCKQUOTE><P> where <IMG alt="{\it Cap}_i" src="latex264.png"> is defined according to <A href="node45.html#table.bab.caps">Figure 10.2</A>. </P></DIV><DIV class="unnumbered"><H3><A name="label124">Distribution Strategy</A></H3><P>There are several possibilities to define a distribution strategy for this problem. </P><DIV class="apropos"><P class="margin">least regret</P><P> We choose to determine the variables <IMG alt="{\it Cost}_i" src="latex265.png"> by distribution. Because no entry in a row of the cost matrix occurs twice, we immediately know which store is supplied by which warehouse. We select the variable <IMG alt="{\it Cost}_i" src="latex265.png"> first for which the difference between the smallest possible value and the next higher value is maximal. Thus, decisions are made early in the search tree where the difference between two costs by different suppliers are maximal. The distribution strategy will try the minimal value in the domain of <IMG alt="{\it
Cost}_i" src="latex256.png"> first. In Operations Research this strategy is known as the principle of <A name="label125"></A><EM>least regret</EM>. </P></DIV></DIV><DIV class="unnumbered"><H3><A name="label126">Script</A></H3><P>The script in <A href="node45.html#program.warehouse">Figure 10.4</A> constrains its root variable to a record containing the supplying warehouse for each store, the costs for each store to be supplied by the corresponding warehouse and the total costs. </P><P>The statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>element Supplier<SPAN class="keyword">.</SPAN>St CostMatrix<SPAN class="keyword">.</SPAN>St Cost<SPAN class="keyword">.</SPAN>St}</CODE></BLOCKQUOTE><P> connects the costs to supply a store with the supplier. Because no element in a row of the cost matrix occurs twice, the supplier for a store is known if its costs are determined and vice versa. Through this statement the constraint <IMG alt="{\it Cost}_i = {\it
CostMatrix}_{i,{\it Supplier}_i}" src="latex260.png"> is imposed. </P><P>A propagator for the constraint that the capacity of a warehouse is not exceeded can be created by the statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>atMost Capacity<SPAN class="keyword">.</SPAN>S Supplier S}</CODE></BLOCKQUOTE><P> </P><P>The statement </P><BLOCKQUOTE class="code"><CODE>Open<SPAN class="keyword">.</SPAN>S = {FD<SPAN class="keyword">.</SPAN>reified<SPAN class="keyword">.</SPAN>sum {Map Stores <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> St} <BR> Supplier<SPAN class="keyword">.</SPAN>St <SPAN class="keyword">=:</SPAN> S <SPAN class="keyword">end</SPAN>} <SPAN class="string">'>:'</SPAN> 0}</CODE></BLOCKQUOTE><P> guarantees that a variable <IMG alt="{\it Open}_i" src="latex266.png"> in the model is constrained to 1 if warehouse <IMG alt="W_i" src="latex249.png"> supplies at least one store. </P><P>The first solution of the problem can be found with the statement </P><DL class="anonymous"><DD class="code"><CODE>{ExploreOne WareHouse}</CODE></DD></DL><P> </P><P>To compute the solution with minimal costs we define the following ordering relation. </P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Order</SPAN> Old New} <BR> Old<SPAN class="keyword">.</SPAN>totalCost <SPAN class="keyword">>:</SPAN> New<SPAN class="keyword">.</SPAN>totalCost <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P> </P><P>The optimal solution with total cost 604 can now be computed with </P><DL class="anonymous"><DD class="code"><CODE>{ExploreBest WareHouse Order}</CODE></DD></DL><P> </P><DIV id="program.warehouse"><HR><P><A name="program.warehouse"></A></P><P> </P><DL class="anonymous"><DD class="code"><CODE>Capacity = supplier(3 1 4 1 4)<BR>CostMatrix = store(supplier(36 42 22 44 52) <BR> supplier(49 47 134 135 121) <BR> supplier(121 158 117 156 115) <BR> supplier(8 91 120 113 101) <BR> supplier(77 156 98 135 11) <BR> supplier(71 39 50 110 98) <BR> supplier(6 12 120 98 93) <BR> supplier(20 120 25 72 156) <BR> supplier(151 60 104 139 77) <BR> supplier(79 107 91 117 154))<BR>BuildingCost = 50<BR><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Regret</SPAN> X}<BR> M = {FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>min X} <BR><SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>reflect<SPAN class="keyword">.</SPAN>nextLarger X M} <SPAN class="keyword">-</SPAN> M<BR><SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">WareHouse</SPAN> X}<BR> NbSuppliers = {Width Capacity}<BR> NbStores = {Width CostMatrix}<BR> Stores = {List<SPAN class="keyword">.</SPAN>number 1 NbStores 1}<BR> Supplier = {FD<SPAN class="keyword">.</SPAN>tuple store NbStores 1<SPAN class="keyword">#</SPAN>NbSuppliers}<BR> Open = {FD<SPAN class="keyword">.</SPAN>tuple supplier NbSuppliers 0<SPAN class="keyword">#</SPAN>1}<BR> Cost = {FD<SPAN class="keyword">.</SPAN>tuple store NbStores 0<SPAN class="keyword">#</SPAN>FD<SPAN class="keyword">.</SPAN>sup}<BR> SumCost = {FD<SPAN class="keyword">.</SPAN>decl} = {FD<SPAN class="keyword">.</SPAN>sum Cost <SPAN class="string">'=:'</SPAN>}<BR> NbOpen = {FD<SPAN class="keyword">.</SPAN>decl} = {FD<SPAN class="keyword">.</SPAN>sum Open <SPAN class="string">'=:'</SPAN>}<BR> TotalCost = {FD<SPAN class="keyword">.</SPAN>decl}<BR><SPAN class="keyword">in</SPAN> <BR> X = plan(supplier:Supplier cost:Cost totalCost:TotalCost)<BR> TotalCost <SPAN class="keyword">=:</SPAN> SumCost <SPAN class="keyword">+</SPAN> NbOpen<SPAN class="keyword">*</SPAN>BuildingCost<BR> {For 1 NbStores 1<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> St}<BR> Cost<SPAN class="keyword">.</SPAN>St <SPAN class="keyword">::</SPAN> {Record<SPAN class="keyword">.</SPAN>toList CostMatrix<SPAN class="keyword">.</SPAN>St}<BR> {FD<SPAN class="keyword">.</SPAN>element Supplier<SPAN class="keyword">.</SPAN>St CostMatrix<SPAN class="keyword">.</SPAN>St Cost<SPAN class="keyword">.</SPAN>St}<BR> <SPAN class="keyword">end</SPAN>}<BR> {For 1 NbSuppliers 1<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> S} <BR> {FD<SPAN class="keyword">.</SPAN>atMost Capacity<SPAN class="keyword">.</SPAN>S Supplier S}<BR> Open<SPAN class="keyword">.</SPAN>S = {FD<SPAN class="keyword">.</SPAN>reified<SPAN class="keyword">.</SPAN>sum {Map Stores <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> St} <BR> Supplier<SPAN class="keyword">.</SPAN>St <SPAN class="keyword">=:</SPAN> S <BR> <SPAN class="keyword">end</SPAN>} <SPAN class="string">'>:'</SPAN> 0}<BR> <SPAN class="keyword">end</SPAN>}<BR> {FD<SPAN class="keyword">.</SPAN>distribute<BR> generic(order: <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> X Y} {Regret X} <SPAN class="keyword">></SPAN> {Regret Y} <SPAN class="keyword">end</SPAN>)<BR> Cost}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P></P><P class="caption"><STRONG>Figure 10.4:</STRONG> A script for the warehouse problem.</P><HR></DIV><P></P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node44.html#section.bab.align"><< Prev</A></TD><TD><A href="node43.html">- Up -</A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1220
