Os limites inferiores para o SARP apresentados nesta sec¸c˜ao encontram-se nas Ta- belas 4.15, 4.16 e 4.17, respectivamente para os conjuntos de instˆancias smval, slpr e slpr-01. Os v´arios limites inferiores apresentados foram obtidos a partir: i) da formula¸c˜ao RF ; ii) da formula¸c˜ao ARF ; e iii) do MCARP. Os dois ´ultimos s˜ao, portanto, provenientes de relaxa¸c˜oes do SARP.
um MCARP, raz˜ao pela qual os limites inferiores para este ´ultimo problema s˜ao tamb´em limites inferiores para o SARP. Sendo assim, s˜ao aqui referidos limites inferiores obtidos para as instˆancias do MCARP associadas `as instˆancias do SARP em estudo.
Os limites inferiores designados por BBLP s˜ao os publicados em Belenguer et al. (2006) e os limites GMP s˜ao provenientes de Gouveia et al. (2009). Os valores BBLP resultaram da aplica¸c˜ao de um algoritmo de planos de corte desenvolvido a partir de uma formula¸c˜ao relaxada para o MCARP, tendo os autores feito a implementa¸c˜ao em Visual C++, chamando rotinas da biblioteca de fun¸c˜oes do CPLEX, num computador pessoal Pentium IV, a 2 GHz, com Windows 2000. Os limites GMP resultaram da aplica¸c˜ao do algoritmo de pesquisa em ´arvore do CPLEX com limite de tempo de uma hora – num computador pessoal Pentium (R) D, a 2.8 GHz, com 500 MB de RAM – e usando v´arias formula¸c˜oes de fluxos para o MCARP.
No entanto, os limites inferiores BBLP e GMP n˜ao est˜ao dispon´ıveis para as instˆancias
slpr-01, pelo que foram deduzidos limites GMP2, obtidos de forma semelhante aos
GMP, usando formula¸c˜oes idˆenticas e tamb´em com uma hora de tempo limite para a pesquisa em ´arvore no CPLEX 11.0.
As formula¸c˜oes RF e ARF s˜ao referidas nas tabelas pelas respectivas designa¸c˜oes. Para cada uma destas formula¸c˜oes, para al´em do valor da solu¸c˜ao da relaxa¸c˜ao em programa¸c˜ao linear (RF ou ARF nas tabelas) ´e ainda considerado o minorante, LB, que se obt´em aplicando o algoritmo de pesquisa em ´arvore do CPLEX 11.0 com limite de tempo de uma hora. N˜ao s˜ao apresentados resultados relativos a F porque, de acordo com testes preliminares (vd. Sec. 4.5.4), e para as instˆancias em estudo, ficou confirmada vantagem na utiliza¸c˜ao de RF .
Nas Tabelas 4.15 e 4.16, a primeira coluna indica o nome da instˆancia. As duas colunas seguintes referem o valor (LB) e o tempo de execu¸c˜ao (tempo) dos limites inferiores GMP e as quarta e quinta colunas s˜ao idˆenticas mas para os limites inferiores BBLP. As restantes colunas contˆem, para a formula¸c˜ao RF e para a relaxa¸c˜ao ARF , o valor da solu¸c˜ao da relaxa¸c˜ao em programa¸c˜ao linear (RF ou ARF ) – e respectivo tempo de execu¸c˜ao (tempo) – e o limite inferior (LB) obtido aplicando a pesquisa em ´arvore do
CPLEX – e respectivo tempo de execu¸c˜ao (tempo).
Nas colunas GMP e BBLP, os valores sublinhados s˜ao ´optimos para o MCARP, repre- sentando minorantes para o SARP. No caso dos limites inferiores BBLP, tendo estes sido obtidos a partir de uma relaxa¸c˜ao do MCARP, a conclus˜ao sobre a optimalidade do valor foi conseguida por compara¸c˜ao com os limites superiores dispon´ıveis em Belenguer et al. (2006) – obtidos atrav´es de algoritmos mem´eticos. Quanto aos limites inferiores GMP, os valores ´optimos foram deduzidos, ou directamente a partir de uma formula¸c˜ao v´alida para o MCARP, ou ent˜ao, no caso de serem provenientes de uma relaxa¸c˜ao, por compara¸c˜ao com os limites superiores j´a referidos ou com os limites superiores produzidos pelo CPLEX.
No caso das colunas RF e ARF , os limites inferiores sublinhados s˜ao os valores ´optimos dos respectivos problemas, ou seja, no caso de RF trata-se do valor ´optimo do SARP, enquanto que em ARF corresponde ao valor ´optimo da relaxa¸c˜ao sem individualiza¸c˜ao de viagens.
Ainda nas mesmas tabelas, o melhor limite inferior para cada instˆancia (ou seja, por linha) salienta-se a negro cheio. A designa¸c˜ao tle indica que foi excedido o limite de tempo (1 hora) sem que tenha sido obtido o valor ´optimo da relaxa¸c˜ao em programa¸c˜ao linear correspondente ou a solu¸c˜ao ´optima do problema, dependendo dos casos, e a palavra erro assinala que houve um erro no CPLEX aquando da resolu¸c˜ao desta mesma relaxa¸c˜ao.
A Tabela 4.17 ´e semelhante `as anteriores, mas em vez das quatro colunas relativas aos limites BBLP e GMP tem duas colunas para os limites GMP2.
A partir das Tabelas 4.15, 4.16 e 4.17, verifica-se que, usando a formula¸c˜ao RF , o valor ´optimo do SARP foi obtido, em menos de uma hora: para trˆes instˆancias smval, com at´e 30 nodos e 96 liga¸c˜oes; para quatro slpr, de dimens˜oes at´e 53 nodos e 169 liga¸c˜oes; e para 17 slpr-01, de dimens˜oes at´e 18 nodos e 58 liga¸c˜oes.
Quanto `a relaxa¸c˜ao ARF , o seu valor ´optimo foi alcan¸cado, em menos de uma hora de execu¸c˜ao no CPLEX, para 24 das 34 instˆancias smval, para cinco slpr (em 15) e para
Tabela 4.15: Limites inferiores – smval
GMP GMP BBLP BBLP RF RF RF RF ARF ARF ARF ARF Instˆancia LB tempo LB tempo RF tempo LB tempo ARF tempo LB tempo smval1a 230 0.17 230 0.11 203.0 0.20 214 tle 203.0 0.01 230 1.78 smval1b 261 0.03 261 0.11 248.0 1.11 259 tle 248.0 0.03 261 0.94 smval1c 309 0.16 309 0.11 282.0 35.13 283 tle 282.0 0.16 306 tle smval2a 324 0.03 324 0.44 314.1 0.16 324 24.72 314.1 0.02 324 0.28 smval2b 395 0.05 395 0.05 368.9 1.36 385 tle 368.9 0.03 395 4.34 smval2c 521 0.69 521 0.11 481.8 39.66 482 tle 481.8 0.08 505 tle smval3a 115 0.02 115 0.33 110.1 0.27 115 472.31 110.1 0.03 115 0.09 smval3b 142 0.03 141 0.16 130.8 0.63 137 tle 130.8 0.02 142 0.28 smval3c 163 0.06 166 0.17 146.8 9.36 147 tle 146.8 0.03 161 tle smval4a 580 0.03 580 0.87 551.4 6.08 566 tle 551.4 0.02 580 0.61 smval4b 650 0.05 650 0.27 630.2 15.75 631 tle 630.2 0.11 650 250.20 smval4c 630 0.05 630 4.12 607.5 98.59 608 tle 607.5 0.41 630 664.83 smval4d 746 0.45 746 0.82 727.4 1221.17 728 tle 727.4 0.67 739 tle smval5a 597 0.05 597 0.22 575.0 2.22 592 tle 575.0 0.02 597 0.20 smval5b 613 0.20 613 0.39 577.4 13.31 579 tle 577.4 0.11 608 tle smval5c 697 0.03 697 0.38 691.8 25.50 692 tle 691.8 0.09 697 7.20 smval5d 718 0.89 719 0.49 684.5 226.84 685 tle 684.5 0.41 706 tle smval6a 326 0.03 326 0.11 295.0 1.16 297 tle 295.0 0.02 326 0.55 smval6b 317 0.05 317 0.22 296.0 4.53 297 tle 296.0 0.05 317 6.11 smval6c 355 0.78 365 0.44 339.5 82.84 340 tle 339.5 0.14 349 tle smval7a 364 0.05 364 0.99 338.0 1.39 339 tle 338.0 0.02 364 2.78 smval7b 412 0.03 412 0.44 406.0 6.58 406 tle 406.0 0.09 412 7.64 smval7c 417 0.84 424 1.53 397.8 169.92 398 tle 397.8 0.27 411 tle smval8a 581 0.03 581 0.16 566.0 1.89 581 1964.02 566.0 0.03 581 0.11 smval8b 531 0.06 531 0.22 508.0 5.97 509 tle 508.0 0.09 531 19.63 smval8c 617 0.12 617 0.39 589.9 142.44 590 tle 589.9 0.22 611 tle smval9a 458 0.05 458 0.38 436.0 4.00 445 tle 436.0 0.06 458 4.89 smval9b 453 0.08 453 0.71 427.1 22.50 428 tle 427.1 0.27 453 26.09 smval9c 428 0.13 428 24.17 396.0 33.20 396 tle 396.0 0.20 428 53.59 smval9d 514 0.14 514 9.99 485.9 491.69 486 tle 485.9 0.58 509 tle smval10a 634 0.05 634 3.30 613.0 5.45 626 tle 613.0 0.05 634 1.88 smval10b 661 0.08 661 1.93 635.0 18.62 636 tle 635.0 0.25 661 26.67 smval10c 623 0.08 623 2.74 594.0 37.09 594 tle 594.0 0.26 622 tle smval10d 642 0.28 643 2.31 609.8 496.83 610 tle 609.8 0.28 635 tle
Sublinhado, colunas GMP e BBLP: valor ´optimo para o MCARP.
Sublinhado, colunas RF e ARF : valores ´optimos dos respectivos problemas. Negro cheio: melhor limite inferior, por instˆancia.
tle: tempo limite excedido (1 hora).
Tabela 4.16: Limites inferiores – slpr
GMP GMP BBLP BBLP RF RF RF RF ARF ARF ARF ARF Instˆancia LB tempo LB tempo RF tempo LB tempo ARF tempo LB tempo slpr-a-01 13484 0.13 13484 0.11 13484.0 0.25 13484 4.27 13484.0 0.03 13484 0.08 slpr-a-02 28052 0.16 28052 0.93 28036.3 4.95 28052 2461.14 28036.3 0.06 28052 1.77 slpr-a-03 76115 0.92 76108 58.44 tle tle tle tle 75965.9 8.45 76094 tle slpr-a-04 126946 83.21 126941 339.28 tle tle tle tle 126654.3 166.72 126799 tle slpr-a-05 202723 tle 202735 2424.46 erro - erro - tle tle tle tle slpr-b-01 14835 0.14 14835 0.11 14813.0 0.31 14835 2.50 14813.0 0.01 14835 0.01 slpr-b-02 28654 0.16 28654 0.88 28618.0 3.23 28654 1683.91 28618.0 0.03 28654 1.14 slpr-b-03 77859 0.22 77837 56.80 tle tle tle tle 77684.0 8.42 77826 tle slpr-b-04 126932 10.69 126932 412.66 tle tle tle tle 126753.9 210.09 126755 tle slpr-b-05 209840 2267.56 209791 3032.00 erro - erro - tle tle tle tle slpr-c-01 18639 0.23 18639 0.11 18444.6 0.52 18638 tle 18444.6 0.03 18639 2.63 slpr-c-02 36339 7.73 36339 1.48 35898.5 11.25 35899 tle 35898.5 0.11 36321 tle slpr-c-03 110959 tle 111117 181.59 tle tle tle tle 109966.6 204.72 110681 tle slpr-c-04 168340 tle 168441 848.38 tle tle tle tle 167083.8 1944.72 167114 tle slpr-c-05 257819 tle 257890 3557.80 erro - erro - tle tle tle tle
Sublinhado, colunas GMP e BBLP: valor ´optimo para o MCARP.
Sublinhado, colunas RF e ARF : valores ´optimos dos respectivos problemas. Negro cheio: melhor limite inferior, por instˆancia.
tle: tempo limite excedido (1 hora). erro: erro no CPLEX.
Tabela 4.17: Limites inferiores – slpr-01
GMP2 GMP2 RF RF RF RF ARF ARF ARF ARF Instˆancia LB tempo RF tempo LB tempo ARF tempo LB tempo slpr-a-01-l21 5864 0.00 6164.0 0.03 6164 0.09 6164.0 0.02 6164 0.16 slpr-a-01-r21 8382 0.00 8682.0 0.01 8682 0.20 8682.0 0.02 8682 0.09 slpr-b-01-l21 6103 0.00 6381.0 0.00 6403 0.09 6381.0 0.00 6403 0.02 slpr-b-01-r21 9495 0.02 9795.0 0.02 9795 0.45 9795.0 0.00 9795 0.00 slpr-c-01-l21 8356 0.00 8618.0 0.03 8700 0.61 8618.0 0.00 8700 0.06 slpr-c-01-r21 11625 0.00 11880.0 0.02 11965 1.63 11880.0 0.02 11965 0.56 slpr-a-01-l23 6542 0.00 6531.8 0.22 6910 334.05 6531.8 0.02 6910 1.59 slpr-a-01-r23 9042 763.22 9022.0 0.33 9400 1124.16 9022.0 0.02 9400 4.33 slpr-b-01-l23 6783 0.00 6708.4 0.09 7083 469.97 6708.4 0.00 7083 0.28 slpr-b-01-r23 10135 0.00 10135.0 0.23 10475 74.44 10135.0 0.00 10475 0.41 slpr-c-01-l23 9108 0.06 9015.7 0.36 9403 tle 9015.7 0.02 9488 1511.56 slpr-c-01-r23 12380 0.03 12286.3 1.19 12542 tle 12286.3 0.02 12806 47.41 slpr-a-01-l34 6944 0.00 6906.3 0.76 7262 tle 6906.3 0.01 7288 172.97 slpr-a-01-r34 9433 0.02 9399.2 2.36 9751 tle 9399.2 0.03 9814 1406.61 slpr-b-01-l34 7167 0.02 7092.6 0.44 7140 tle 7092.6 0.02 7247 205.27 slpr-b-01-r34 10475 0.00 10475.0 1.47 10815 1977.47 10475.0 0.03 10815 5.72 slpr-c-01-l34 9524 0.83 9414.5 0.95 9486 tle 9414.5 0.01 9826 tle slpr-c-01-r34 12807 0.02 12715.5 7.98 12723 tle 12715.5 0.03 13217 tle slpr-a-01-25%l21 2739 0.02 3038.2 0.00 3120 0.69 3038.2 0.02 3120 0.19 slpr-a-01-25%r21 4591 0.00 4891.0 0.03 4933 4.31 4891.0 0.00 4933 0.50 slpr-b-01-25%l21 2496 0.01 2778.0 0.00 2840 0.25 2778.0 0.00 2840 0.09 slpr-b-01-25%r21 2916 0.00 3216.0 0.00 3252 0.13 3216.0 0.00 3252 0.03 slpr-c-01-25%l21 2775 0.00 3086.7 0.02 3194 2.16 3086.7 0.00 3194 1.37 slpr-c-01-25%r21 3033 0.03 3325.1 0.00 3475 1.25 3325.1 0.00 3475 0.50
Sublinhado, colunas GMP2: valor ´optimo para o MCARP.
Sublinhado, colunas RF e ARF : valores ´optimos dos respectivos problemas. Negro cheio: melhor limite inferior, por instˆancia.
tle: tempo limite excedido (1 hora).
todas as slpr-01. Atendendo a que as instˆancias smval est˜ao agrupadas em conjuntos de trˆes ou quatro, cuja diferen¸ca mais relevante reside na capacidade dos ve´ıculos, ´e poss´ıvel observar que aquelas para as quais n˜ao se alcan¸cou o valor ´optimo de ARF correspondem, em geral, a menores valores da capacidade, ou seja, a valores superiores para a propor¸c˜ao entre a procura m´edia por tarefa e a capacidade do ve´ıculo.
Comparando os limites inferiores obtidos a partir de RF e ARF , verifica-se que, para os trˆes conjuntos de instˆancias estudadas, os segundos s˜ao sempre melhores ou iguais. Estes resultados podem dever-se a dois factores. O primeiro resulta da observa¸c˜ao de que o valor ´optimo de ARF , sempre que conhecido, ´e igual ao valor ´optimo do problema, sugerindo que possa existir uma grande maleabilidade das instˆancias testadas em formar viagens de custo total igual ao valor ´optimo de ARF , onde as viagens n˜ao est˜ao definidas – na Proposi¸c˜ao 4.8, mostrou-se que estes valores ´optimos nem sempre s˜ao iguais. Por outro lado, sendo ARF uma relaxa¸c˜ao de RF em que se omitem as viagens, ARF beneficia de uma redu¸c˜ao de dimens˜ao que pode permitir, no mesmo tempo de execu¸c˜ao
da pesquisa em ´arvore do CPLEX, chegar a melhores limites inferiores que RF . Estabelecendo agora a rela¸c˜ao com os minorantes GMP e BBLP, os resultados mostram que os limites inferiores produzidos atrav´es das formula¸c˜oes RF e ARF para o SARP s˜ao iguais aos limites GMP para cinco instˆancias slpr (em 15) e para 22 smval (em 34). No entanto, para estes dois conjuntos de instˆancias, os limites inferiores obtidos com RF ou ARF nunca s˜ao melhores do que os GMP. Quanto aos limites BBLP, estes s˜ao tamb´em sempre de valor superior para todas as instˆancias slpr e quase todas as smval, exceptuando a smval3b.
Sendo os limites GMP e BBLP provenientes do MCARP – que ´e uma relaxa¸c˜ao do SARP em que n˜ao existe constru¸c˜ao de sectores –, e `a semelhan¸ca do que foi exposto acima em rela¸c˜ao a RF e ARF , os resultados sugerem, para as instˆancias smval e
slpr, uma relativa capacidade de “arrumar” tarefas em sectores de dura¸c˜ao limitada
mantendo o custo da solu¸c˜ao do MCARP.
Para as instˆancias slpr-01, contrariamente ao que sucede para as smval e slpr, verifica-se uma clara vantagem dos limites inferiores provenientes de RF e de ARF , relativamente aos que se obtˆem a partir do MCARP. Quando comparados com os limites GMP2, os de RF s´o n˜ao s˜ao melhores para trˆes instˆancias (em 24), sendo sempre superiores os ARF . Mesmo o valor da relaxa¸c˜ao em programa¸c˜ao linear de RF e ARF j´a ´e superior ao limite GMP2, para 15 destas instˆancias.
O facto de os limites inferiores para o SARP poderem ser de melhor qualidade quando obtidos a partir das formula¸c˜oes RF e ARF do que aqueles que provˆem do MCARP est´a relacionado com a estrutura das instˆancias. As instˆancias slpr-01 foram geradas de forma a terem um determinado n´umero esperado de viagens na solu¸c˜ao ´optima do MCARP (vd. Sec. 3.4.3). No caso das instˆancias com dois sectores e uma viagem na solu¸c˜ao ´optima do MCARP, slpr-01-21 e slpr-01-25%21, sucedeu que, na solu¸c˜ao ´optima do SARP foi necess´ario considerar uma viagem adicional para que fosse poss´ıvel respeitar o limite de dura¸c˜ao dos sectores e a capacidade dos ve´ıculos. Situa¸c˜ao semelhante ocorreu tamb´em para as instˆancias com dois sectores e trˆes viagens no MCARP, slpr-01-23, e com trˆes sectores e quatro viagens no MCARP, slpr-01-34.
Sendo necess´ario considerar uma viagens adicional na solu¸c˜ao ´optima do SARP, relati- vamente ao MCARP, o custo vai ser acrescido, pelo menos, do custo de uma descarga (λ = 300 no caso das instˆancias slpr-01 ). Al´em disso, pode dar-se o caso de ter de ser necess´ario escolher percursos mais dispendiosos. ´E o que se passa em 17 das instˆancias
slpr-01. Das restantes, em cinco delas o aumento no custo ´e exactamente igual ao custo
da descarga adicional.
Os resultados apresentados sugerem que as formula¸c˜oes RF e ARF para o SARP podem ser vantajosas na determina¸c˜ao de limites inferiores para este problema, face aos provenientes do MCARP, nos casos em que as caracter´ısticas da instˆancia obriguem `a cria¸c˜ao de viagens adicionais no SARP. Como foi poss´ıvel verificar, o acr´escimo ao custo pode n˜ao se dever apenas ao evidente custo acrescido com descargas, mas tamb´em `a necessidade de realizar percursos mais onerosos.
Como nota final, salienta-se que, idealmente, na formula¸c˜ao do SARP deveriam estar presentes condi¸c˜oes que estabelecessem a contiguidade dos sectores. No entanto, estas condi¸c˜oes n˜ao s´o n˜ao s˜ao f´aceis de formalizar matematicamente, tal como focado por v´arios autores (Labelle et al., 2002; Perrier et al., 2008), como podem dificultar ainda mais a obten¸c˜ao de solu¸c˜oes e limites inferiores.