Projeto:

SOLUAO DE PROBLEMAS DE LOCALIZAO E ROTEAMENTO EM REDES COM SISTEMA DE INFORMAES GEOGRFICAS

RELATRIO FINAL DE ATIVIDADES

Resumo Este projeto visa desenvolver uma ferramenta para o processo de tomada de deciso envolvendo problemas de localizao de facilidades e roteamento de veculos em redes. Pretende-se desenvolver tal ferramenta com base na plataforma computacional do sistema de informaes geogrficas TransCAD. Os problemas de localizao de facilidades e de roteamento de veculos justificam a ateno por serem comuns em diversas aplicaes e serem considerados de difcil soluo. Para a soluo desses problemas pretende-se utilizar procedimentos j disponveis no sistema TransCAD, assim como procedimentos j desenvolvidos pelo orientador. Pretende-se dar nfase a aplicaes no ambiente urbano, levando em considerao dados e mapas digitalizados j disponveis.

Relatrio de Bolsa de Iniciao Cientfica rea: Engenharia de Produo

FAPESP Fundao de Amparo Pesquisa do Estado de So Paulo

SOLUAO DE PROBLEMAS DE LOCALIZAO E ROTEAMENTO EM REDES COM SISTEMA DE INFORMAES GEOGRFICAS Processo FAPESP 01/02786-4

Mariana Quissak Bartelega Peixoto Bolsista

Prof. Dr. Edson Luiz Frana Senne Orientador

Unesp - Campus de Guaratinguet Faculdade de Engenharia Maio, 2002

1. Resumo do Projeto Aprovado 1.1. Introduo Problemas de localizao tratam de decises sobre onde localizar facilidades em uma rede, considerando que existem clientes a serem atendidos, de forma a otimizar um determinado critrio (Love et al., 1988; Mirchandani and Francis, 1990; Francis et al., 1992; Drezner, 1995). O termo facilidades pode se referir a fbricas, depsitos, escolas, etc., enquanto clientes pode se referir a depsitos, unidades de vendas, estudantes, etc.

As aplicaes de localizao, em geral, so divididas para os setores pblico e privado. No caso do setor pblico, as aplicaes procuram maximizar a satisfao dos clientes. So exemplos de aplicaes para o setor pblico, a localizao de escolas, postos de sade, corpo de bombeiros, centrais de ambulncias, viaturas de polcia, pontos de nibus, entre outros. No caso do setor privado, as aplicaes envolvem, em geral, fbricas, depsitos, torres de transmisso, lojas de franquias, dentre outras.

Problemas de roteamento aparecem em uma srie de servios, como entrega bancria, entrega postal, entrega de mercadorias, rotas de nibus escolar, coleta de lixo, servio de entregas noturnas, operaes de frete, dentre outros. A soluo destes problemas pode diminuir bastante o custo de distribuio, causando uma grande economia tanto para o setor pblico como para o setor privado. No entanto, muitos destes problemas so difceis de resolver. Estas duas caractersticas fazem com que haja uma extensa literatura sobre problemas de roteamento (Christofides et al., 1979; Bodin et al., 1983; Gendreau et al., 1997).

No problema clssico de roteamento de veculos, consideram-se n clientes espacialmente distribudos, cada um com uma demanda de mercadorias. As mercadorias so entregues a partir de um depsito por uma frota de veculos homogneos. Cada veculo realiza um percurso saindo do depsito e entregando as mercadorias para um subconjunto de clientes, satisfazendo as necessidades de demanda de cada um e retornando ao depsito. A rota de cada veculo deve obedecer a algumas restries como: a quantidade de mercadoria entregue no deve exceder a capacidade do veculo e o tempo limite para realizar uma rota no deve ser ultrapassado. O problema de roteamento de ve culos pretende traar rotas para os veculos, determinando para quais clientes deve-se fornecer a mercadoria, de forma a no violar as restries e otimizar alguma funo-objetivo. Normalmente, trs funes-objetivo podem ser consideradas: 3

 minimizar a distncia total percorrida (ou o tempo gasto) por todos os veculos; minimizar o nmero de veculos; minimizar uma combinao de custo de veculos e distncia percorrida.

Estas reas localizao de facilidades e roteamento de veculos tm despertado crescente interesse por parte de planejadores, principalmente quando uma base de dados geograficamente referenciada pode ser usada. O uso de SIG Sistema de Informaes Geogrficas (Fischbeck, 1994) para resolver problemas de localizao e roteamento, levandose em conta a capacidade de armazenar, exibir e manipular dados espacialmente distribudos e a possibilidade de integrao de novos algoritmos aos SIGs, iniciou-se h poucos anos. O ESRI (Environmental Systems Research Institute), por exemplo, integrou alguns problemas de localizao no-capacitados a seu sistema de informaes geogrficas ARC/INFO (ESRI, 1997). A integrao baseou-se na heurstica de Teitz & Bart (1968) para soluo do problema das p-medianas. Outro exemplo ocorre com o sistema TransCAD que utiliza heursticas gulosas e heursticas de troca para resolver alguns problemas de localizao, dispondo tambm de procedimentos para a soluo de problemas de roteamento de veculos, inclusive problemas com restries de tempo, mltiplos depsitos e frotas heterogneas (Caliper, 1999b). 1.2. Objetivos do Projeto Os objetivos deste projeto so os seguintes: Estudar o sistema de informaes geogrficas TransCAD (Caliper, 1999c) no que se refere soluo de problemas de localizao de facilidades e roteamento de veculos; Promover integraes de algoritmos de localizao de facilidades e roteamento de veculos j desenvolvidos ao sistema de informaes geogrficas TransCAD, de modo que a interao do usurio com as solues dos problemas possa ser feita diretamente sobre mapas que representem redes urbanas, e comparar as solues obtidas por esses novos algoritmos com as solues obtidas pelos procedimentos disponveis no sistema TransCAD; Construir prottipos de Sistemas de Apoio Deciso para problemas de localizao de facilidades e roteamento de veculos usando dados geo-referenciados j disponveis para redes urbanas e o sistema TransCAD. Pretende-se a soluo dos seguintes problemas com o sistema TransCAD:

 p-medianas capacitado e no-capacitado; localizao considerando custos fixos e os casos capacitado e no-capacitado; roteamento de veculos (caso clssico e variaes). 1.3. Atividades e Cronograma de Desenvolvimento

As seguintes atividades sero desenvolvidas no projeto:

(a) Levantamento bibliogrfico sobre problemas de localizao e roteamento. (b) Estudo do sistema de informaes geogrficas TransCAD. (c) Estudo da linguagem de desenvolvimento GISDK (Caliper, 1999a). (d) Utilizao de algoritmos j existentes e integrao de novos algoritmos de localizao e roteamento ao TransCAD, visando a construo de Sistemas de Apoio Deciso. (e) Desenvolvimento de aplicaes-piloto considerando dados e mapas j existentes. (f) Elaborao de relatrios e divulgao de resultados.

Pretende-se que tais atividades sejam executadas no perodo de 1 ano, segundo o cronograma:

Meses Atividade a b c d e f X 01 X 02 X X X X X X X X X X X X X X X X X X X X 03 04 05 06 07 08 09 10 11 12

2. Desenvolvimento das Atividades do Projeto As atividades (a) e (b) - Levantamento bibliogrfico sobre problemas de localizao e roteamento, e Estudo do Sistema de Informaes Geogrficas TransCAD propostas no item 1.3 deste relatrio foram tratadas no relatrio parcial, e portanto, no sero 5

detalhadamente explicadas neste relatrio. Sero citados apenas os tpicos que sero de fato utilizados nesta segunda etapa do projeto. 2.1. Problemas de Localizao e Roteamento Resumo 2.1.1. Geoprocessamento Geoprocessamento o uso automatizado de informao que de alguma forma est vinculada a um determinado lugar no espao, seja por meio de um simples endereo ou por coordenadas. Vrios sistemas fazem parte do Geoprocessamento dentre os quais o GIS o sistema que rene maior capacidade de processamento e anlise de dados espaciais. Estes sistemas se aplicam a qualquer tema que manipule dados ou informaes vinculadas a um determinado lugar no espao e que possam ser representados em um mapa, como casas, escolas, hospitais, etc. A utilizao destes sistemas produz informaes que permitem tomar decises sobre problemas espaciais, como os problemas de localizao e roteamento em redes. 2.1.2. Problemas de Localizao Em um problema de localizao, uma ou mais facilidades servem clientes espacialmente distribudos. O objetivo na soluo de um problema deste tipo determinar a melhor localizao para as facilidades a fim de otimizar uma funo de custo (tempo, distncia, valor financeiro...) previamente determinada, ou ento determinar o nmero de facilidades necessrias para que uma funo de custo seja otimizada. A funo de custo (ou funo-objetivo) pode ser, por exemplo, minimizar a distncia mdia entre as facilidades e os clientes ou minimizar o tempo mdio gasto para visitar um certo nmero de clientes a partir de uma ou mais facilidades. 2.1.3. Problemas de Roteamento O problema de roteamento de veculos (PRV) o mais comum dentre os problemas de roteamento. Consiste basicamente em estabelecer e organizar rotas ou itinerrios eficientes para veculos realizarem entregas de mercadorias. Em outras palavras, dispe-se de uma frota de k veculos, idnticos ou no, e deseja-se atender um conjunto de n clientes, cada um com uma demanda especfica. Todos os veculos devem partir e retornar a uma mesma origem (normalmente denominada depsito) e cada cliente deve ser visitado uma nica vez. O objetivo geral minimizar o custo total de transporte no atendimento aos clientes, isto , minimizar custos fixos, custos operacionais e o nmero de veculos envolvidos no transporte.

Alguns fatores importantes dificultam a construo e soluo dos problemas de roteamento: - Frota heterognea: veculos com diferentes capacidades de carga; - Janelas de tempo: representam o intervalo de tempo no qual a entrega da mercadoria deve ocorrer. Um exemplo tpico deste problema ocorre na distribuio de bebidas para restaurantes. Por exemplo, no seria conveniente para o restaurante receber suas mercadorias no horrio do almoo. Portanto, janelas de tempo em um PRV possuem valores limites para iniciar a entrega. - Viagens longas: a circulao entre cidades geralmente fora os veculos a circularem mais de um dia. Devem ento ser estabelecidas regras especiais na formao da rota que tornam o problema muito mais complexo. - Horrios de incio e fim das atividades: Alguns dos problemas requerem que todos os veculos devam comear e terminar na mesma hora. Outros permitem diferentes especificaes de horrio de incio e final para as rotas de cada um dos veculos, o que os tornam mais realistas, pois na prtica, nem sempre possvel que todos os veculos deixem o depsito simultaneamente. - Questo de assimetria: em um PRV, a questo de assimetria um fator muito importante. Um problema assimtrico quando o caminho para ir de i at j diferente do caminho de j at i. Um exemplo prtico disso ocorre com ruas de mo nica e locais separados por uma serra.

2.2. Estudo do Sistema de Informaes Geogrficas TransCAD Foi feito um estudo detalhado sobre o Sistema de Informaes Geogrficas TransCAD, e os resultados preliminares obtidos foram mostrados no relatrio parcial de atividades. A seguir, sero re-apresentados e detalhadamente explicados alguns tpicos e funes com maior importncia nesta etapa do projeto. 2.2.1 Selees Selections Sets Criar uma seleo apenas destacar, com cores e padres diferentes, determinadas entidades no mapa. Alm dos trs botes na Toolbox, pode-se fazer seleo atravs do boto . Com

este boto possvel criar uma seleo usando uma condio com os dados dos campos de uma tabela. Por exemplo, deseja-se selecionar todos os trechos de ruas com o nmero de milhas superior a 1.35, numa seleo que iremos chamar de Teste, o usurio deve proceder da seguinte maneira:

 aqui que coloca-se a condio desejada para se fazer a seleo Neste local, coloca-se o nome da seleo

Com Create Set especificado que a seleo vai ser criada

Isto so listas, dos campos, dos operadores, das funes e dos valores, que ajudam na formao da condio.
Figura 1 Trabalhando com selees

Aqui aparece as condies usadas anteriormente

importante salientar que a condio deve utilizar informaes contidas nos campos que existem na tabela. Neste caso, o nmero de milhas para cada trecho da rua fornecido pelo campo Miles . A seleo Teste destacar todos os trechos de ruas com um comprimento maior que 1.35 milhas. Em Selection Method existem outras opes de mtodos de seleo, como: Add to Set , usada quando se deseja que a condio seja adicionada a uma seleo que j existe e que est especificada em Set Name; Remove from Set , usada quando se quer remover da seleo especificada em Set Name os trechos que satisfazem a condio digitada; e Subset , quando se deseja criar uma subseleo. As condies podem utilizar operadores lgicos como or (ou) e and (e). Assim, quando se deseja selecionar todos os trechos de ruas com o nmero de milhas iguais a 1.00 ou 2.00, pode-se usar a seguinte condio: Miles = 1 or Miles = 2. Caso seja desejado selecionar os trechos que tenham nmero de milhas igual a 3.00, mas que tenham o nome George Parks, a condio ser : Miles = 3 and Name = George Parks. Com a ferramenta de seleo, disponvel em Selection no menu Tools, pode-se visualizar, criar, remover ou alterar caractersticas de selees de um determinado layer.

Apaga a seleo

Renomeia a seleo.

Adiciona labels somente na seleo.

Ao clicar este boto, o TransCAD mostra a seleo inteira no mapa. Com um clique neste boto, consegue-se visualizar somente a seleo corrente. Para voltar ao normal, clique de novo. Com um clique neste boto possvel visualizar as selees existentes para este layer. Muda estilo da seleo.

Adiciona uma nova seleo

Seleo corrente, de nome Teste Este nmero fornece a quantidade de entidades selecionadas nesta seleo, no caso Teste.
Figura 2 Selees

No necessrio que nada de especial seja feito para salvar uma seleo. Elas so salvas automaticamente sempre que o mapa onde elas estiverem presentes for salvo. Para executar uma seleo em uma camada, baseada em outra camada, utiliza-se o comando Select by Location no menu Dataview. Por exemplo, caso o usurio queira selecionar numa camada de rodovias os trechos contidos num determinado estado, ele dever primeiramente criar uma seleo com o estado desejado e mudar a camada de trabalho para a de rodovias; em seguida, no menu Dataview escolher o item Select by Location e finalmente preencher a janela como pode ser visto abaixo:
Nome do layer e da seleo em que ser baseada seleo. No exemplo, o layer Estados e a seleo Selection contm o estado desejado.

Aqui, determine o modo como a seleo dever ser feita, isto , qual o critrio a ser utilizado para execuo da seleo. No caso, so selecionados os trechos de rodovias que esto tocando (touching) o estado selecionado. Nome da seleo que est sendo criada, com os trechos que tocam o estado desejado.

Figura 3 Selec by Location

A seguir, encontra-se um exemplo de selees criadas a partir de um mapa disponvel no TransCAD. Os tringulos verdes indicam uma seleo e os quadrados vermelhos outra.

Figura 4 Exemplo de Selees

Este recurso ser bastante utilizado na soluo dos problemas de localizao de facilidades e de roteamento de veculos, tratados mais adiante neste relatrio.

2.2.2 Redes e Obteno de Menores Caminhos Uma rede (network) uma estrutura especial de dados que armazena importantes caractersticas de um sistema de transporte. O TransCAD utiliza-se dos arquivos geogrficos para construir os mapas dos sistemas de transporte e as redes para resolver os problemas relacionados a estes sistemas. Menores caminhos (Shortest paths) so rotas, sobre uma rede de transportes, nas quais o custo geral o menor possvel. Este custo se refere a qualquer combinao de fatores como distncia, tempo, ou at custo financeiro de uma viagem. Encontrar os menores caminhos em uma rede o principal bloco de construo de muitos algo ritmos e modelos sofisticados, e ser, portanto, bastante citado neste trabalho. 2.2.2.1. - Redes Redes so utilizadas para analisar a maneira como pessoas e mercadorias fluem de uma localidade at outra. Elas so representadas atravs de grafos (representaes abstratas de um sistema de transporte). Uma rede definida como um conjunto de ns e ligaes. Ns so as localidades de onde o fluxo comea, termina ou se ramifica. Ligaes so percursos que transportam o fluxo, de n para n. 10

Cada n e cada ligao em uma rede possuem um nmero de identificao (ID). No TransCAD, as ligaes e os ns geralmente correspondem s caractersticas de, respectivamente, linhas e pontos (endpoints) de um arquivo geogrfico. Uma camada de linhas em um mapa consiste em um conjunto de linhas, cada qual tendo incio e fim em pontos denominados endpoints, cada um dos quais definido por coordenadas. Criando uma Rede: Uma rede sempre criada a partir de uma camada de linhas. Para tanto, aps selecionar a camada de linhas com a qual deseja-se construir a rede, deve-se selecionar a opo Networks/Paths-Create a partir do menu de opes. aberta ento, uma caixa de dilogos referentes criao da rede:

Figura 5 Criando uma Rede

Nesta caixa de dilogos, o usurio deve escolher as caractersticas a serem includas na rede. Deve tambm informar o nome do campo correspondente ao comprimento de cada percurso. Caso seja necessrio, mais de um campo pode ser adicionado rede. Utilizando uma rede: O TransCAD permite que qualquer nmero de diferentes redes sejam criadas. Porm, para ativar uma das redes criadas, basta abri- la a partir do menu de opes: File/Open. 2.2.2.2. Encontrando o Menor Caminho em uma Rede O TransCAD capaz de encontrar o menor (ou o melhor) caminho na movimentao de um ponto at outro em uma rede. O menor caminho aquele que minimiza o valor total do custo de um determinado atributo, como distncia, tempo ou custo financeiro. 11

O algoritmo utilizado pelo TransCAD no clculo do menor caminho pressupe que a ordem na qual as localidades devem ser visitadas dada. Considerando o mapa mostrado na figura abaixo, deseja-se calcular o menor percurso a ser percorrido, partindo do ponto PARTIDA, passando pelos PONTOS 1, 2 e 3, e chegando ao ponto CHEGADA.

Figura 6 Teste do algoritmo do Menor Caminho

Para solucionar um problema como este, o TransCAD utiliza-se da ferramenta Shortest Path, no meu de opes (Network/Paths Shortest Path). A execuo deste comando simples, bastando clicar nos pontos de partida, de passagem e de chegada, na ordem em que eles devem ser visitados. O programa mostra o resultado obtido desenhando, no mapa, o caminho a ser percorrido, levando em conta a rede que conecta esses pontos. Utilizando-se ento do comando Shortest-Path, obtm-se para o exemplo anterior o seguinte resultado:

Figura 7 Resultado encontrado pelo algoritmo do Menor Caminho

12

2.2.2.3. Problema do Caixeiro Viajante Traveling Salesman Problem (TSP) Muitos dos problemas de transporte consistem em determinar a melhor maneira de realizar uma seqncia de paradas ou entregas. o que acontece, por exemplo, com nibus escolares que devem, todo dia, buscar as crianas em suas residncias e lev- las escola, ou ento com vendedores que planejam visitar seus clientes em lugares diferentes. Problemas como estes apresentam o mesmo tipo de estrutura minimizar os custos quando se deseja realizar visitas em um grupo de paradas (stops), no importando a seqncia com que estas paradas sejam visitadas. Estes tipos de problemas recebem o nome de Problemas do Caixeiro Viajante, tratado tambm neste relatrio como TSP (Traveling Salesman Problem) . O TransCAD soluciona este tipo de problema, encontrando o caminho de menor custo a partir de uma rede. Para tanto, o ponto de partida deve ser especificado. Este ponto denominado de depsito (depot), e os pontos a serem visitados de paradas (stops). O resultado do percurso denominado de percurso (tour). O percurso sempre comea e termina em um depsito. Para soluo de um problema do Caixeiro Viajante, uma rede deve ser criada (com as caractersticas que sero utilizadas). Em seguida, deve ser preparada uma Seleo (a partir dos comandos de seleo previamente explicados) contendo o depsito e as paradas a serem visitadas. O depsito deve ser sempre o primeiro elemento da seleo. O resultado de um problema como este pode ser mostrado pelo programa de algumas formas diferentes: O percurso desenhado no mapa; O custo do percurso mostrado na tela; As direes a serem seguidas so mostradas pelo Note Pad.

Considere como exemplo o mapa mostrado na Figura 8. Supe-se que um nibus escolar deve, toda manh, buscar um certo nmero de crianas e lev-las escola, percorrendo a menor distncia possvel. No mapa, esto identificadas a escola e as residncias das crianas (tringulos verdes).

13

Figura 8 Mapa para teste do algoritmo do Problema do Caixeiro Viajante

Utilizando o comando Traveling Salesman Problem, a partir do menu de opes (Networks/Paths-Traveling Salesman Problem) o programa fornece graficamente o percurso a ser percorrido, e tambm um arquivo com as direes a serem seguidas (figuras 9 e 10):

Figura 9 Resultado obtido para o problema do Caixeiro Viajante

14

Start

East on PEARL ST North on BROAD ST

0.14 Kilometers 0.39 Kilometers 0.35 Kilometers 0.08 Kilometers 0.06 Kilometers 0.45 Kilometers 0.29 Kilometers 0.08 Kilometers 0.11 Kilometers 0.08 Kilometers 0.13 Kilometers 0.28 Kilometers 0.42 Kilometers 0.37 Kilometers 0.06 Kilometers 0.04 Kilometers 0.30 Kilometers 0.20 Kilometers 0.04 Kilometers 0.04 Kilometers 0.47 Kilometers 0.06 Kilometers 0.10 Kilometers

(0.14 Kilometers). (0.53 Kilometers). (0.88 Kilometers). (0.96 Kilometers). (1.02 Kilometers). (1.47 Kilometers). (1.76 Kilometers). (1.84 Kilometers). (1.95 Kilometers). (2.03 Kilometers). (2.16 Kilometers). (2.44 Kilometers). (2.86 Kilometers). (3.23 Kilometers). (3.30 Kilometers). (3.34 Kilom eters). (3.64 Kilometers). (3.84 Kilometers). (3.88 Kilometers). (3.93 Kilometers). (4.40 Kilometers). (4.46 Kilometers). (4.56 Kilometers).

Continue

Turn Right East on WALL ST Turn Right West on WATER ST Turn Left South on GOUVERNEUR LN Turn Left East on FRONT ST Turn Left North on FULTON ST Turn Right North on GOLD ST Turn Left North on BEEKMAN ST Turn Left South on WILLIAM ST Turn Right West on ANN ST Turn Left West on NASSAU ST Turn Right West on LIBERTY ST Turn Left South on WASHINGTON ST Turn Right West on JOSEPH P WARD ST Continue West on (unknown)

Turn Left South on S ST VIADUCT Turn Right North on BATTERY PL Sharp Right East on 1ST PL Backtrack West on 1ST PL Sharp Left South on BATTERY PL Turn Right South on BROADWAY Continue South on WHITEHALL ST

Figura 10 Direes a serem seguidas

2.3 Estudo da linguagem de desenvolvimento GISDK 2.3.1 Introduo

O TransCAD foi criado para permitir aos usurios desenvolverem e integrarem seus prprios modelos e estabelecer conexes com outros sistemas de informaes. Usando o GISDK (Geographic Information System Developers Kit) programas externos podem ser conectados ao TransCAD para solucionar problemas de roteamento, logstica, ou localizao. Isto permite construir aplicaes personalizadas utilizando mapeamento, visualizao, ou qualquer outra ferramenta de anlise do TransCAD.

15

Figura 11 Adicionando modelos personalizados ao TransCad

A linguagem GISDK permite que sejam criados programas que auxiliem na resoluo de problemas geogrficos. Estes programas so criados a partir de uma interface personalizada contendo menus, barras de fe rramentas e caixas de dilogos programados para responder s aes do usurio da maneira desejada. Existem trs modos diferentes de utilizao da linguagem GISDK: - Criando add- ins, que permitem estender a capacidade do programa TransCAD, permitindo, por exemplo, criar atalhos para operaes que so sempre executadas; - Construindo custom applications, utilizando uma interface totalmente personalizada, permitindo uma maior simplicidade da utilizao do TransCAD pelos clientes; - Criando server applications, que permitem adicionar mapas e anlises a outros programas. Add-Ins so criados a partir da escrita, compilao e instalao de macros ou caixas de dilogos. Uma vez instaladas, o usurio pode execut- las a partir do menu de opes Tools Add-Ins. Este tipo de aplicao pode ser bastante simples, como por exemplo a criao de macros que so executados apenas quando so selecionados, sem nenhuma interao do usurio, ou muito complexos, onde mostram, por exemplo, uma caixa de dilogos que possib ilita ao usurio escolher as configuraes e opes desejadas para executar a macro (so geralmente barras de ferramentas personalizadas, constitudas de botes). O GISDK permite que sejam criadas aplicaes do programa utilizando uma interface prpria Custom Applications, na qual o programador especifica os menus, barras de ferramentas, caixas de dilogos e faz com que a aplicao responda da maneira desejada. No so todos os algoritmos do TransCAD que esto disponveis para serem utilizados em uma Custom Applications. Os algoritmos da soluo de problemas de localizao de facilidades 16

e de roteamento de veculos, por exemplo, no podem ser adicionados em uma Custom Application. Uma Server Application uma aplicao do GISDK que fornece servios a outros programas. Uma Server Application utiliza os recursos grficos e as capacidades de anlise do TransCAD como parte do prprio programa. Ela pode ser utilizada, por exemplo, para mostrar mapas em outros programas (sistemas de apoio a decises, aplicaes de marketing, aplicaes na internet). Estes programas (cliente), podem ser escritos em Visual Basic, C, C++, ou qualquer outra linguagem de programao. Uma Server Application no possui uma interface grfica, pois ela apenas fornece servios a outros programas. Elas so criadas a partir da escrita de macros que contenham as tarefas requeridas pelo programa cliente e so inicializadas sempre que forem requisitadas pelo servidor. 2.3.2 A Plataforma e a Interface

Para um usurio, o TransCAD um programa como outro programa qualquer do ambiente Windows. Para um programador da linguagem GISDK, entretanto, o TransCAD deve ser dividido em duas partes distintas: a plataforma e a interface com o usurio (UI User Interface). A plataforma o centro do sistema de informaes geogrficas (GIS) e do sistema de gerenciamento de dados (DBMS), que so utilizados para construir mapas e realizar as anlises destes mapas e dados. A interface com o usurio o conjunto de menus, caixas de dilogos e ferramentas, que permitem o acesso do usurio s capacidades do programa. A plataforma est armazenada em um arquivo executvel (TCW.EXE) e em vrias bibliotecas (DLLs). As UIs esto armazenadas em um banco de dados, denominados de Banco de Dados da Interface com o Usurio (UI Database). A plataforma e o banco de dados da interface so inseparveis; um no pode ser utilizado sem o outro. 2.3.3 A Compilao

Quando programas em GISDK so escritos, eles so armazenados em arquivos textos, conhecidos como resour ce files. Estes arquivos possuem extenso .RSC. Todos os programas escritos em GISDK devem ser compilados antes de serem executados. O programa responsvel em compilar os resource files chamado de resource compiler. Este compilador est armazenado no Bando de Dados da Interface com o Usurio. O compilador pode compilar um simples arquivo ou um grupo de arquivos de uma vez. Para que um grupo de arquivos seja compilado, deve ser criada uma lista contendo o nome dos arquivos a serem compilados. Esta lista deve ser um arquivo texto com extenso .LST, que contenha o nome de todos os arquivos a serem compilados, um por linha. 17

Os compiladores buscam nos arquivos escritos pelo programador erros de vrios tipos, incluindo erros de sintaxe, pontuao, erros de declarao, dentre outros. Se erros so detectados, o compilador cria um arquivo listando os erros encontrados, localizando-os pela linha em que so encontrados. Este arquivo de erro possui o mesmo nome do resource file, e uma extenso .ERR, e sempre armazenado no mesmo diretrio que o prprio resource file. A compilao pode ser feita de trs maneiras: - Atravs dos botes da barra de ferramentas do GISDK; - Atravs do programa RSCC.EXE; - Atravs da funo LoadResourceFile( ) presente na linguagem GISDK. 2.3.3.1 - Compilao atravs da Barra de Ferramentas: A barra de ferramentas do GISDK um add- in que contm as ferramentas utilizadas para compilar e acessar as aplicaes do GISDK. Ela acessada a partir do menu de opes do TransCAD: Tools Add-Ins...
(2) (1) (4) (3)

Figura 12 Barra de Ferramentas GISDK

(1) (2) (3) (4)

Compila o resource file Testa a macro ou a caixa de dilogos Compile resource file(s) to a stand-alone UI database Executa um ou mais comandos imediatamente

2.3.3.2 - Compilao atravs do Stand-alone Resource Compiler: Os programas podem ser compilados atravs do prompt de comandos do DOS ou a partir do Gerenciador de Programas do Windows, utilizando a verso stand-alone do compilador (RSCC.EXE). Este programa aceita a linha de comando da seguinte maneira: rscc {-c} -u uidbname fname1.rsc fname2.rsc... onde: - O sinalizador u indica que a entrada seguinte na linha de comando (uidbname) o atalho e o nome do arquivo (sem extenso) do Banco de Dados da Interface (UI database);

18

fname1.rsc, fname2.rsc, etc. so os nomes dos resource files a serem compilados; O sinalizador opcional c indica que o UI database deve ser limpo antes da compilao.

2.2.3.3 - Compilao atravs da funo LoadResourceFile( ): Os prprios programas escritos pelo programador podem usar a funo LoadResourceFile( ) para compilar arquivos. A funo permite que o programador escolha qual resource file deseja compilar e qual UI database deseja usar. 2.3.4. Recursos da Linguagem GISDK: Os recursos da linguagem GISDK correspondem aos blocos de construo de add- ins e de aplicaes. Podem ser de cinco tipos: macros, caixa de dilogos, caixa de ferramentas, barra de ferramenta e menus. 2.3.4.1. Macros Macros funcionam como subrotinas que so executadas quando um usurio escolhe um item do menu ou clica em algum cone da barra de ferramentas. Uma macro possui um nome, argumentos opcionais e uma srie de condies que estabelecem sua funo. Sua estrutura bsica pode ser escrita como:
Macro "Nome_Macro" {(argumento1, argumento2, ...)} <condies> endMacro

O nome das macros podem conter qualquer combinao de letras, nmeros e espaos. Caso seja requerido pelo programador, elas podem retornar um valor, atravs da funo Return( ). 2.3.4.2. Caixa de Dilogos: Este recurso define a aparncia e a operao de uma caixa de dilogo, como normalmente so encontradas nas aplicaes Windows. Uma caixa de dilogos contm controles atravs dos quais os usurios podem interagir com o programa, e macros que indicam a lgica que deve ser executada. Caixas de dilogos so mostradas na tela quando so selecionadas pelo usurio a partir de um item do menu de opes ou de um boto da barra de ferramentas. 19

As caixas de dilogos paralisam qualquer aplicao: enquanto elas esto visveis, o usurio no pode clicar em menus, mapas, dataviews, etc. Elas podem ser removidas da tela quando executada a funo Return(). Estas geralmente respondem quando o usurio seleciona os botes com opo OK ou CANCELAR. A estrutura de uma caixa de dilogos apresentada a seguir:
Dbox "Dbox_Nome" {(argumento1, argumento2...)} {{{{posio_horizontal} , posio_vertical} , largura} , altura} {opes} <itens da caixa de dilogos> endDbox

2.3.4.3. Caixas e Barras de Ferramentas: Caixas de ferramentas so caixas de dilogos que permanecem na tela enquanto o usurio interage com mapas, menus, dataviews, etc. Uma caixa de ferramentas, diferentemente da caixa de dilogos, no paralisa a aplicao. A estrutura de uma caixa de ferramentas apresentada a seguir:
Dbox "Dbox_Nome" {(argumento1, argumento2...)} {{{{posio_horizontal} , posio_vertical} , largura} , altura} {opes} ToolBox <itens da caixa de dilogos> endDbox

As barras de ferramentas possuem formato horizontal e se localizam sob a barra do menu contendo os itens da caixa de dilogos. Somente uma barra de ferramentas pode ser utilizada por vez, mas diversas barras de ferramentas podem ser ativadas e desativadas alternadamente, atravs das funes ShowDbox() e HideDbox(). A definio de uma barra de ferramentas :
Toolbar "toolbar nome" {(argumento1, argumento2...)} <itens da caixa de dilogos> endToolbar

2.3.4.4. Menus:

20

O recurso Menu utilizado para definir menus ou sub- menus em uma aplicao. O formato dado por:
Menu "menu nome" {opes} <itens do menu> endMenu

2.3.5. Elementos da Linguagem GISDK: Quando um usurio escolhe um item de um menu, ou seleciona um boto de uma caixa de dilogos, estes devem desenvolver alguma ao. Estas aes so descritas usando uma seqncia de declaraes que devem satisfazer determinadas condies. Estas condies podem ser estabelecidas por constantes, variveis, operadores, etc. 2.3.5.1. Constantes: As constantes na linguagem GISDK podem ser nmeros (inteiros e reais), strings, ou constantes booleanas (Verdadeiro/Falso). 2.3.5.2. Variveis: Na linguagem GISDK no necessrio que as variveis sejam declaradas antes de serem utilizadas. O nome das variveis deve comear com uma letra, porm pode conter letras, nmeros e o smbolo sublinhado (underscore ). As variveis podem ser do tipo: Inteiro (valores entre 2.147.482.648 e 2.147.482.647) - Real (valores entre -3.4E-38 e -3.4E+38) - String (mximo de 512 caracteres) - Array (qualquer nmero de ele mentos de tipos diferentes) - Compound (variveis compostas) - Boolean (Verdadeiro/Falso) - Null 2.3.5.3. Operadores: Operadores Aritmticos: Os operadores aritmticos combinam expresses de nmeros inteiros e reais. So quatro operadores: + adio subtrao, negao 21

* /

multiplicao diviso

Operadores Lgicos: Os operadores lgicos realizam operaes booleanas e retornam valores booleanos (Verdadeiro ou Falso). So eles: & (ou AND) conjuno | (ou OR) disjuno ! (ou NOT) negao lgica Operadores Relacionais: Os operadores relacionais retornam valores booleanos (Verdadeiro ou Falso). So eles: = (ou eq) igualdade <> (ou ne) desigualdade > (ou gt) maior que < (ou lt) menor que >= (ou ge) maior que ou igual a <= (ou le) menor que ou igual a contains contm a seqncia de caracteres. 2.3.6. Exemplos desenvolvidos Nesta etapa do projeto, visando uma melhor familiarizao com a linguagem, foram criados exemplos de programas utilizando a linguagem de desenvolvimento GISDK. Para os programas elaborados, foi utilizado como exemplo o mapa da cidade de Nova Iorque, disponvel no ambiente TransCAD.

22

Figura 13 Mapa da cidade de Nova Iorque

1 Programa: . Neste primeiro programa elaborado em GISDK, foi criado um atalho para abrir o mapa em questo. Deste modo, ao executar a macro ABRIR (ver programa a seguir), o mapa desejado aberto. Outras macros teis foram tambm construdas neste programa, as quais, quando executadas, fecham o mapa em questo ou efetuam o trmino do TransCAD.
//******************************************************************** //Objetivo Abrir o mapa "nycity" a ser utilizado Macro "ABRIR" SetMapUnits("Miles") SetSearchPath("tutorial\\") // Abre o mapa a ser utilizado OpenMap("c:\\Mariana\\TransCad\\Gisdk\\nycity.map",) // Muda o tamanho do mapa mostrado SetWindowSizePixels(, 600, 450) //Largura - Comprimento // Muda a camada para "Streets" SetLayer("Streets") EndMacro //******************************************************************** //Objetivo: O macro FECHAR utilizado para fechar mapas (File-Close) Macro "FECHAR"

23

Name=GetMapNames() For i = 1 to name.length do CloseMap(name[i]) End Return(0) // Qualquer valor no nulo impede que o mapa seja fechado endMacro //******************************************************************** // Objetivo: Sair do TransCad Macro "SAIR" Exit() EndMacro

2 Programa: - Objetivo: Mostrar na tela do programa, os bairros da cidade de Nova Iorque com mais de 60.000 habitantes, verificando se o usurio deseja imprimi- los.
// nome do arquivo: prog2.rsc // mapa utilizado: c:\mariana\transcad\gisdk\nycity.map // layer ativa: 5-Digit Zip // Objetivo: Mostra na tela os bairros com mais de 60.000 habitantes, // verificando se o usurio deseja imprim-los. // MACRO Macro "Imprimir maiores bairros" curr_map = GetMap() lyr = GetLayer() // A varivel bairro_id recebe os dados da primeira linha do dataview do // layer em uso, onde a populao foi organizada em ordem decrescente em // relao ao nmero de habitantes. bairro_id = GetFirstRecord(lyr + "|", {{"Population","Descending"}})

while bairro_id <> null do pop = lyr.Population If pop > 60000 then do // A varivel bairro_scope encontra no mapa a rea correspondente ao bairro // em questo (armazenado pela varivel bairro_id. bairro_scope = GetRecordScope(bairro_id) // Seta a rea em questo do mapa, e redesenha-o. SetMapScope(curr_map, bairro_scope) RedrawMap() name = lyr.Name Answer = RunDbox("Imprimir", name) If Answer = "Sim" then PrintMap()

24

end // Encontra o prximo estado. Caso tenha terminado, a varivel bairro_id // recebe "null" bairro_id = GetNextRecord(lyr + "|", bairro_id, {{"Population","Descending"}}) end endMacro // CAIXA DE DILOGOS dBox "Imprimir" (bairro_name) title: "Imprimir Bairro" //Prepara o texto a ser mostrado init do str = "Voc deseja imprimir o bairro " + bairro_name +"?" enditem text 1,1,40,3 // localizao e tamanho do texto na caixa de dilogos variable: str // A varivel str contm um texto a ser mostrado align: center framed // Coloca uma margem ao redor do texto // Boto "Sim". Deve ser clicado para imprimir o mapa do bairro // correspondente button "Sim" 1, 5, 9 // A localizao e o tamanho do boto do Return("Sim") enditem // Boto "No". Deve ser clicado para no imprimir o mapa do bairro // correspondente button "No" 31, 5, 9 do Return("Nao") enditem endDbox

Resultado: Ao executar o programa, o TransCad mostra na tela, um a um, os bairros do mapa que contenham mais de 60.000 habitantes, e pergunta ao usurio se deseja imprimir cada um dos bairros.

25

Figura 14 Resultado do Programa: Imprimir bairros com mais de 60.000 habitantes?

3 Programa: - Objetivo: Calcular a distncia retilnea entre dois pontos quaisquer de um mapa. Para tanto, ao executar o programa, o usurio deve clicar nos dois pontos desejados.
//************************************************************* // Nome do arquivo: distancia.rsc //Objetivo: Calcular a distncia entre 2 pontos quaisquer //************************************************************* dbox "DISTANCIA" toolbox init do SetMapUnits("Kilometers") m1 = GetMapUnits("Plural") LayerPt="Localidades" setLayer(LayerPt) lyr = GetLayer() ShowMessage("Clique nos 2 pontos desejados: ") // Os ns. indicam a largura de cada uma das 4 divises da barra de status SetStatusBar({30, 30, 20, 20}) SetStatus(1, lyr + "-" + m1,) Enditem //************************************************ Tool 25, 2 Icons: "bmp\\help_m.bmp" Cursor: "bmp\\stop2_2.bmp"do

26

SetStatus(2, "Calculo da distncia - Ponto 1",) // A varivel C1 armazena a cordenada do mapa digitada pelo usurio C1 = ClickCoord() //Cria-se uma seleo de nome "Origem", com os pontos distantes // at 100Km da varivel C1 N = SelectbyCoord("Origem","Several",C1,100) // A varivel PONT armazena o primeiro dado da camada de pontos // da seleo "Origem" criada PONT=GetFirstRecord(LayerPt + "|Origem",) ShowMessage("1 Registro: - ID= " + PONT) //A varivel ID1 armazena os dados (latitude, longitude e nome //referentes ao primeiro registro. ID1 = GetRecordValues(LayerPt,PONT,{"Longitude","Latitude","Name"}) //[1 elemento] a posio da varivel armazenada (1=Longitude, 2=Latitude //3=Name, [2 elemento] se for [1] corresponde ao nome do campo // se for [2] corresponde ao registro do campo showmessage (ID1[3][2]) //Cood espera os resultados da latitude e longitude C1= Coord(ID1[1][2],ID1[2][2]) // [1][2]=longitude, [2][2]=latitude if N>1 then showmessage(string(N)) showmessage("Clique no 2o ponto desejado:") SetStatus(2, "Distncia entre capitais-pto 2",) C2 = ClickCoord() setview(LayerPt) N = selectbycoord("Destino","Several",C2,100) PONT=getfirstrecord(LayerPt+"|Destino",) ID2 = getrecordvalues(LayerPt,PONT,{"Longitude","Latitude","Name"}) SetStatus(4, ID2[3][2],) SetStatus(2, ID1[3][2]+" - "+ID2[3][2],) //coord espera os argumentos em Long, Lat C2= Coord(ID2[1][2],ID2[2][2]) // [1][2]=longitude, [2][2]=latitude if N>1 then showmessage(string(N)) dist=getdistance (C1,C2) dist=Format(dist,",*.0") //Calcula a distncia entre os pontos //Distncia em string

showmessage("A distncia entre " + ID1[3][2] + " e " + ID2[3][2] + " : " + dist + m1) enditem close do return() enditem enddbox //tool

Resultado: O programa informa ao usurio a distncia entre os dois pontos desejados.

27

 4 Programa: - Objetivo: Mostrar todas as informaes referentes aos mapas abertos no TransCAD.
//************************************************************** // Nome do arquivo: informaes.rsc // Objetivo: Mostrar as informaes sobre os mapas abertos. // Executar Dialog Box: "INFORMACOES" //************************************************************** dbox "INFORMACOES" title: "Informaes sobre os mapas" init do mapas_disponiveis = GetWindows("map") mapa_escolhido = 1 camada_escolhida = 1 //Verifica se h mapas abertos no programa if mapas_disponiveis = null then do ShowMessage("Este comando s funciona se algum mapa estiver aberto") Return() end //Pega o nome de todas as camadas for k = 1 to ArrayLength(mapas_disponiveis[1]) do camadas = GetMapLayers(mapas_disponiveis[1][k], "all") lista = lista + {camadas[1]} end RunMacro("MOSTRAR DADOS") Enditem Frame "Dados do Mapa" 1.5, .5, 56, 10.5 Prompt: "Dados do Mapa" Text "Mapa..." 3, 1.5 Scroll List "Mapas disponveis" 3, 2.7, 25, 8 List: mapas_disponiveis[1] Variable: mapa_escolhido do camada_escolhida = 1 RunMacro("MOSTRAR DADOS") Enditem Text "Camadas..." 31, 1.5 Scroll List "Camadas Ativas" 31, 2.7, 25, 8 List: lista[mapa_escolhido] Variable: camada_escolhida do RunMacro("MOSTRAR DADOS") enditem Button "Fechar" 60, 1, 10 do Return() EndItem

Frame "Dados da Camada" 1.5, 11.5, 56, 9.3 Prompt: "Dados da Camada" Text"Nome..." 13, 12.5, 19 Prompt: "Nome:" Variable: lista[mapa_escolhido][camada_escolhida] Framed Text"Tipo..." 44, same, 12 Prompt: "Tipo:" Variable: tipo_camada Framed Text"Diretrio..." 13, 14, 43 Prompt: "Diretrio:" Variable: diretorio Framed Text"Arquivo..." 13, 15.5, 19 Prompt: "Arquivo:" Variable: nome_arquivo1 Framed

28

Text"Tamanho..." 44, same, 12 Prompt: i2s(filestat[6]) + " bytes" Framed Text"Criado em..." 13, 17, 19 Prompt: filestat[7] Framed Text"Campos..." 44, same, 12 Prompt: Framed Text"Mapas..." 13, 18.5, 43, 2 Prompt: Framed

"Tamanho:" "Criado em:" "Campos:"

Variable: Variable: Variable: recs

"Arquivo:" Variable: mapas

Macro "MOSTRAR DADOS" do camadas = GetLayerInfo(lista[mapa_escolhido][camada_escolhida]) tmp = SplitPath(camadas[10]) diretorio = tmp[1] + tmp[2] nome_arquivo1 = tmp[3] + tmp[4] // verificar se a camada est em outros mapas mapas = null for i = 1 to mapas_disponiveis[1].length do if ArrayPosition(lista[i], {lista[mapa_escolhido][camada_escolhida]}, ) > 0 then do mapas = mapas + mapas_disponiveis[1][i] + ", " end end mapas = Left(mapas, Len(mapas) - 2) tipo_camada = GetLayerType(lista[mapa_escolhido][camada_escolhida]) filestat = GetFileInfo(camadas[10]) recs = GetRecordCount(lista[mapa_escolhido][camada_escolhida], ) enditem endDBox

Resultado: aberta uma caixa de dilogos, informando ao usurio as informaes referentes aos mapas em uso, conforme mostra a figura 15.

Figura 15 Informaes sobre os mapas em uso

29

2.4 Construo de Sistemas de Apoio Deciso Esta etapa do projeto teve como objetivo realizar um interfaceamento entre algoritmos de localizao e roteamento j criados pelo orientador e o TransCAD. Para tanto, foram estudadas maneiras para que este interfaceamento pudesse ser realizado. Estudando a linguagem GISDK, constatou-se que a funo RunProgram(), ao ser chamada, executa programas de qualquer tipo, e espera que a execuo do programa seja finalizada. O interfaceamento entre o algoritmo e o TransCAD foi realizado via criao e leitura de arquivos texto (.TXT). 2.4.1. Os Algoritmos Caixa Preta Os algoritmos criados pelo orientador foram considerados como uma caixa preta, ou seja, seu contedo e informaes no foram de importncia no desenvolvimento do projeto. As informaes de importncia para que o interfaceamento fosse realizado foram os dados de entrada e de sada do algoritmo, ou seja, quais dados eram necessrios serem fornecidos para que o programa fosse executado, e que dados ele retornaria ao TransCAD. O problema foi resumido ento em fornecer os dados necessrios ao programa, executlo, atravs da funo RunProgram(), e interpretar os dados fornecidos por ele. 2.4.2. Problemas de Localizao Para os problemas de localizao (capacitado e no capacitado), os algoritmos exigem como entrada a matriz de custos (geralmente, a matriz de distncias), armazenada no arquivo matriz.txt, e um arquivo de dados (dados.txt) do mapa a ser utilizado, e retornam, como sada, um arquivo texto result.txt informando os c lusters encontrados. Para a determinao da matriz de custos foi utilizada a funo prpria do TransCAD, acessada a partir do menu de opes Routing/Logistics Cost Matrix . Para a criao desta matriz, foi necessrio que, antes, fosse criada uma rede para o mapa em questo (Networks/Paths Create). O arquivo de dados foi tambm criado pelo TransCAD, o qual utilizou os dados dos mapas j existentes. Este arquivo contm: o nmero de ns associados rede, o nmero de clusters a serem formados, e a capacidade e a demanda de cada n. O arquivo result.txt apresenta uma linha para cada cluster encontrado. Cada linha contm o nmero de identificao (ID) do cluster, o nmero de ns associados quele cluster, e os nmeros de identificao destes ns. Exemplos de arquivos de entrada e sada podem ser encontrados a seguir:

30

A distncia entre os ns 1 e 2 de 13.32 Km.

Figura 16 Dados de Entrada: Matriz de distncias

Nmero de clusters a serem formados

Nmero de ns associados

Demanda do n

Capacidade do n

Figura 17 Dados de Entrada: Arquivo dados.txt

Cluster n 5 Mediana corresponde ao n n 700, com 5 ns associados, sendo eles os ns 701, 702, 703, 704, 705.

Figura 18 Dados de Sada Clusters

31

Foram fornecidos pelo orientador dois programas: um deles para a soluo de problema de localizao no capacitado (pmed.exe), e o outro para a soluo de problema capacitado (pmedcap.exe). Ambos exigiam como entrada o arquivo de dados e a matriz de custos, porm para o caso no capacitado, no era necessrio que o arquivo de dados contivesse a capacidade e a demanda dos ns. Assim, foi criada, utilizando as funes da linguagem GISDK, uma macro responsvel por executar os programas criados pelo orientador e interpretar os dados fornecidos por eles.

/* Objetivo: Executar o programa de soluo de problemas de localizao no capacitado e interpretar os dados fornecidos por ele. Para a soluo de problemas capacitados, substituir o arquivo Pmed.exe pelo arquivo PmedCAP.exe. O arquivo "c:\\Bolsistas\\Fapesp\\Mariana\\matriz.txt e c:\\Bolsistas\\Fapesp\\Mariana\\dados.txt armazenam os dados de entrada do programa. */

Macro "PMEDIANAS" ShowMessage ("Certifique-se de que os dados de entrada do programa esto armazenados no arquivo matriz.txt e dados.txt") //Para o problema capacitado, utilizar o arquivo Pmedcap.exe status = RunProgram("c:\\Bolsistas\\Fapesp\\Mariana\\Pmed.exe", ) //L a network j criada net_h = ReadNetwork("c:\\Bolsistas\\Fapesp\\Mariana\\network.net") layer=SetLayer("Endpoints") arquivolinha = OpenFile("c:\\Bolsistas\\Fapesp\\Mariana\\result.txt", "r") dim linha[100] nlinha=0 While !FileAtEOF(arquivolinha) do Nlinha=1+nlinha nlinha_s=IntToString(nlinha) linha[nlinha]=ReadLine(arquivolinha) end ShowMessage ("O nmero total de clusters : " +nlinha_s) CloseFile(arquivolinha) arquivolinha=OpenFile("c:\\Bolsistas\\Fapesp\\Mariana\\ result.txt", "r") map_name=GetMap() icon=45 cor_red=1000 cor_green=3528 cor_blue=7520 dim pieces [nlinha] teste=0 var1=0 for i=1 to nlinha do linha[i]=ReadLine(arquivolinha) pieces[i] = ParseString(linha[i], " ")

32

//Medianas medianas = Subarray(pieces[i],1,1) mediana_i=S2I(medianas[1]) teste=1+teste teste2=String(teste) selec_med="Mediana_" + teste2 SelectByIDs(selec_med, "more", {mediana_i}) //Nmero de ns n_nos= SubArray(pieces[i],2,1) n_nos2=S2I(n_nos[1]) //Ns Associados nos= SubArray(pieces[i],3,n_nos2) var1=var1+1 var2=String(var1) selec_nos="Ns_" + var2 selec_cluster= "Cluster_" + var2 dim nos_int [n_nos2+1] for j=1 to n_nos2 do nos_i=S2I(nos[j]) SelectByIDs(selec_nos, "more", {nos_i}) SelectByIDs(selec_cluster, "more", {nos_i,mediana_i}) cor_red=cor_red+50000 cor_green=cor_green+1000 cor_blue=cor_blue+3000 nos_int[1]=mediana_i nos_int[j+1]=S2I(nos[j]) end SetDisplayStatus(selec_nos, "Active") SetIcon(selec_nos, "Font Character", "Caliper Cartographic|Bold|9", icon) SetIconColor(selec_nos, ColorRGB(cor_red,cor_green,cor_blue)) SetDisplayStatus(selec_med, "Active") SetIcon(selec_med, "Font Character", "Caliper Cartographic|Bold|9", 40) SetIconColor(selec_med, ColorRGB(cor_red,cor_green,cor_blue)) end EndMacro

2.4.3. Problemas de Roteamento Considerou-se como problemas de roteamento a determinao de clusters referentes a cada um dos veculos disponveis (atendendo suas capacidades) e a determinao de trajetos para cada um dos clusters, no qual o veculo parte de um n de origem, visita todos os demais ns do seu cluster e retorna ao n de origem. Assim, para a soluo de problemas de roteamento foi utilizado, primeiramente, o programa de localizao capacitada (pmedcap.exe) e, em seguida, por meio da linguagem GISDK, utilizou-se a funo TSP, que resolve o Problema do Caixeiro Viajante, para fornecer as rotas e as distncias a serem percorridas em cada um dos clusters. 33

Portanto, foram acrescentadas as seguintes linhas no algoritmo GISDK de soluo de problemas de localizao:

// Problemas de Roteamento tsp = TSP(net_h, nos_int, 1) ShowMessage("A distncia total percorrida na viagem " +String(i) + " : " + String(tsp[1]) )

2.4.4. Construo de um Prottipo de Sistema de Apoio Deciso Para a criao de um prottipo de sistema de apoio deciso, foi criada uma Custom Application, a qual permite uma fcil interao entre o usurio e o programa. Nesta Custom Application permite-se que o usurio escolha os mapas com os quais deseja trabalhar. A figura 19 permite visualizar a interface principal da aplicao.

Figura 19 Interface da Aplicao

Os menus permitem que o usurio realize funes como abrir, fechar e obter informaes sobre os mapas, conforme ilustra a figura 20.

34

Figura 20 Menus de opes da aplicao

A seguir, encontra-se o cdigo fonte do prottipo desenvolvido.

/* ****************************************************************** Projeto FAPESP - Interface - Custom Application Nome: Mariana Quissak Bartelega Peixoto Arquivo: ca_2.rsc Objetivo: Interface para a soluo de problemas de p-medianas, Localizao e roteamento, capacitado e no capacitado. ******************************************************************* */ Macro "INTERFACE" var1=RunDbox("INICIO") SetDefaults({{"Menu", "Menu Principal"}}) EndMacro Menu "Menu Principal" MenuItem "Arquivos" text: "Arquivo" MenuItem "Mapa" text: "Mapa" MenuItem "Opes" text: "Opes" MenuItem "Ferramentas" text: "Ferramentas" EndMenu Menu "Arquivos" Menuitem "Abrir Mapa" Menuitem "Fechar Mapa" Separator Menuitem "Sair" EndMenu Macro "abre um mapa" Macro "fecha um mapa" do Exit() enditem

Menu "Arquivos" Menu "Mapas" Menu "Opcao" Menu "Ferramentas"

Menu "Mapas" Menuitem "Nmero de Mapas" Menuitem "Lista de Mapas" Menuitem "Propriedades" EndMenu

Macro "contar mapas" Dbox "lista de mapas" Dbox "INFORMACOES"

Menu "Opcao" MenuItem "P-Medianas no Capacitado" Macro "FUNCAO1" MenuItem "P-Medianas Capacitado" Macro "FUNCAO2"

35

Separator MenuItem "Localizao" Dbox "AVISO" MenuItem "Localizao Capacitado" Dbox "AVISO" Separator MenuItem "Roteamento no Capacitado" Macro "FUNCAO3" MenuItem "Roteamento Capacitado" Macro "FUNCAO4" EndMenu Menu "Ferramentas" MenuItem "Mostrar barra de ferramentas" Dbox "TOOLBOX" MenuItem "Recursos GISDK" Macro "Dbox Sampler" EndMenu Macro "FUNCAO1" RunMacro("PMEDIANAS",1,1) EndMacro Macro "FUNCAO2" RunMacro("PMEDIANAS",2,1) EndMacro Macro "FUNCAO3" RunMacro("PMEDIANAS",1,2) EndMacro Macro "FUNCAO4" RunMacro("PMEDIANAS",2,2) EndMacro Macro "abre um mapa" On escape do Return() end fnm = ChooseFile({{"Mapas", "*.map"}}, "Abrindo mapa", ) on error do ShowMessage("Impossvel abrir o mapa " + fnm + ".") Return() end map = OpenMap(fnm, {{"Menu", "Menu Principal"}}) on error default endMacro Macro "fecha um mapa" typ = GetWindowType() if typ <> "Map" then do ShowMessage("Voc no pode fechar essa janela!") Return() end CloseMap() EndMacro Macro "contar mapas" map_names = GetMapNames() n_maps = ArrayLength(map_names) output = "Existem " + string(n_maps) + " mapas abertos no momento." ShowMessage(output) EndMacro Dbox "lista de mapas" title: "Mapas abertos:" init do map_names = GetMapNames() map_idx = 1 if map_names = null then do ShowMessage("No existe nenhum mapa aberto no momento!") Return() end enditem scroll list 10, 1, 24, 8 prompt: "Mapas" list: map_names variable: map_idx button "OK" 36, 1, 9 do

36

SetMap(map_names[map_idx]) Return() enditem button "Cancelar" 36, 3, 9 do Return() enditem button "Fechar Mapa" 36, 5, 12 do CloseMap(map_names[map_idx]) map_names = GetMapNames() map_idx = 1 enditem endDbox dBox "INICIO" title: "Custom Application - Mariana" init do str = "Custom Application elaborada por *Mariana*" enditem text 1, 1, 40, 3 variable: str align: center framed button "Continuar" 20, 5 , 14 do Return() enditem endDbox dBox "TOOLBOX" right,center,27,17 title: "Opes" Toolbox Button "Abrir Mapa" 2, 1, 23 do RunMacro("ABRIR") enditem button "P-Medianas no Capacitado" 2, 3, 23 do RunMacro("PMEDIANAS",1,1) enditem button "P-Medianas Capacitado" 2, 5, 23 do RunMacro("PMEDIANAS",2,1) enditem button "Localizao" 2, 7, 23 do RunDbox("AVISO") enditem button "Localizao Capacitado" 2, 9, 23 do RunDbox("AVISO") enditem button "Roteamento no Capacitado" 2, 11, 23 do RunMacro("PMEDIANAS",1,2) enditem button "Roteamento Capacitado" 2, 13, 23 do RunMacro("PMEDIANAS",2,2) enditem button "X" 23, 15, 1 do Return() enditem endDbox Macro "ABRIR" SetMapUnits("Miles") SetSearchPath("tutorial\\") // Abre o mapa a ser utilizado OpenMap("c:\\Bolsistas\\Fapesp\\Mariana\\mapa.map",) // Muda o tamanho do mapa mostrado SetWindowSizePixels(, 600, 450) //Largura - Comprimento EndMacro Macro "PMEDIANAS" (argumento1, argumento2) /* O arquivo "c:\\Bolsistas\\Fapesp\\Mariana\\matriz.txt e c:\\Bolsistas\\Fapesp\\Mariana\\dados.txt armazenam os dados de entrada do programa. */

37

ShowMessage ("Certifique-se de que os dados de entrada do programa esto armazenados no arquivo matriz.txt e dados.txt") if argumento1=1 then do ShowMessage("Problema no capacitado") status = RunProgram("c:\\Bolsistas\\Fapesp\\Mariana\\Pmed.exe", ) end if argumento1=2 then do ShowMessage("Problema Capacitado") status = RunProgram("c:\\Bolsistas\\Fapesp\\Mariana\\Pmedcap.exe", ) end //L a network j criada net_h = ReadNetwork("c:\\Bolsistas\\Fapesp\\Mariana\\network.net") ShowMessage("Net Lida!") ShowMessage("Verificar se o arquivo result.txt est na pasta correta") Layer=SetLayer("Endpoints") arquivolinha = OpenFile("c:\\Bolsistas\\Fapesp\\Mariana\\ localizacao.txt", "r") dim linha[100] nlinha=0 While !FileAtEOF(arquivolinha) do nlinha=1+nlinha nlinha_s=IntToString(nlinha) linha[nlinha]=ReadLine(arquivolinha) end ShowMessage ("O nmero total de clusters : " +nlinha_s) CloseFile(arquivolinha) Arquivolinha = OpenFile("c:\\Bolsistas\\Fapesp\\Mariana\\ localizacao.txt", "r") map_name=GetMap() icon=45 cor_red=1000 cor_green=3528 cor_blue=7520 dim pieces [nlinha] teste=0 var1=0 for i=1 to nlinha do linha[i]=ReadLine(arquivolinha) pieces[i] = ParseString(linha[i], " ") //Medianas medianas = Subarray(pieces[i],1,1) mediana_i=S2I(medianas[1]) teste=1+teste teste2=String(teste) selec_med="Mediana_" + teste2 SelectByIDs(selec_med, "more", {mediana_i}) //Nmero de ns n_nos= SubArray(pieces[i],2,1) n_nos2=S2I(n_nos[1]) //Ns Associados nos= SubArray(pieces[i],3,n_nos2) var1=var1+1 var2=String(var1) selec_nos="Ns_" + var2

38

selec_cluster= "Cluster_" + var2 dim nos_int [n_nos2+1] for j=1 to n_nos2 do nos_i=S2I(nos[j]) SelectByIDs(selec_nos, "more", {nos_i}) SelectByIDs(selec_cluster, "more", {nos_i,mediana_i}) cor_red=cor_red+50000 cor_green=cor_green+1000 cor_blue=cor_blue+3000 nos_int[1]=mediana_i nos_int[j+1]=S2I(nos[j]) end SetDisplayStatus(selec_nos, "Active") SetIcon(selec_nos, "Font Character", "Caliper Cartographic|Bold|9", icon) SetIconColor(selec_nos, ColorRGB(cor_red,cor_green,cor_blue)) SetDisplayStatus(selec_med, "Active") SetIcon(selec_med, "Font Character", "Caliper Cartographic|Bold|9", 40) SetIconColor(selec_med, ColorRGB(cor_red,cor_green,cor_blue)) //Problemas de Roteamento if argumento2=2 then do tsp = TSP(net_h, nos_int, 1) ShowMessage("A distncia total percorrida na viagem " +String(i) + " : " + String(tsp[1]) ) end end endMacro Dbox "AVISO" Title: "AVISO" Toolbox Init do texto = "Este programa ainda est em construo." Enditem Text 1, 1, 40, 3 variable: texto align: center framed button "OK" 20, 5, 5 do Return ( ) enditem endDbox Dbox "INFORMACOES" title: "Informaes sobre os mapas" init do mapas_disponiveis = GetWindows("map") mapa_escolhido = 1 camada_escolhida = 1 //Verifica se h mapas abertos no programa if mapas_disponiveis = null then do ShowMessage("Este comando s funciona se algum mapa estiver aberto") Return() end //Pega o nome de todas as camadas for k = 1 to ArrayLength(mapas_disponiveis[1]) do camadas = GetMapLayers(mapas_disponiveis[1][k], "all") lista = lista + {camadas[1]} end RunMacro("MOSTRAR DADOS")

39

Enditem Frame "Dados do Mapa" 1.5, .5, 56, 10.5 Prompt: "Dados do Mapa" Text "Mapa..." 3, 1.5 Scroll List "Mapas disponveis" 3, 2.7, 25, 8 List: mapas_disponiveis[1] Variable: mapa_escolhido do camada_escolhida = 1 RunMacro("MOSTRAR DADOS") Enditem Text "Camadas..." 31, 1.5 Scroll List "Camadas Ativas" 31, 2.7, 25, 8 List: lista[mapa_escolhido] Variable: camada_escolhida do RunMacro("MOSTRAR DADOS") Enditem Button "Fechar" 60, 1, 10 Do Return() EndItem Frame "Dados da Camada" 1.5, 11.5, 56, 9.3 Prompt: "Dados da Camada" Text"Nome..." 13, 12.5, 19 Prompt: "Nome:" Variable: lista[mapa_escolhido][camada_escolhida] Framed Text"Tipo..." 44, same, 12 Prompt: "Tipo:" Variable: tipo_camada Framed Text"Diretrio..." 13, 14, 43 Prompt: "Diretrio:" Variable: diretorio Framed Text"Arquivo..." 13, 15.5, 19 Prompt: "Arquivo:" Variable: nome_arquivo1 Framed Text"Tamanho..." 44, same, 12 Prompt: "Tamanho:" Variable: i2s(filestat[6]) + " bytes" Framed Text"Criado em..." 13, 17, 19 Prompt: "Criado em:" Variable: filestat[7] Framed Text"Campos..." 44, same, 12 Prompt: "Campos:" Variable: recs Framed Text"Mapas..." 13, 18.5, 43, 2 Prompt: "Arquivo:" Variable: mapas Framed Macro "MOSTRAR DADOS" do camadas = GetLayerInfo(lista[mapa_escolhido][camada_escolhida]) tmp = SplitPath(camadas[10]) diretorio = tmp[1] + tmp[2] nome_arquivo1 = tmp[3] + tmp[4] // verificar se a camada est em outros mapas mapas = null for i = 1 to mapas_disponiveis[1].length do if ArrayPosition(lista[i], {lista[mapa_escolhido][camada_escolhida]}, ) > 0 then do mapas = mapas + mapas_disponiveis[1][i] + ", " end end mapas = Left(mapas, Len(mapas) - 2) tipo_camada = GetLayerType(lista[mapa_escolhido][camada_escolhida]) Filestat = GetFileInfo(camadas[10]) recs = GetRecordCount(lista[mapa_escolhido][camada_escolhida], ) Enditem EndDBox

2.4.5. Aplicao

40

O programa foi testado para diversos mapas de cidades pequenas, porm optou-se por apresentar neste relatrio os resultados obtidos utilizando o mapa da cidade de Ribeiro Preto (figura 21), uma vez que este apresenta uma rede de mdio porte (cerca de 800 ns), para os problemas no-capacitados. Os dados de entrada do programa foram gerados pelo TransCAD.

Figura 21 Mapa da cidade de Ribeiro Preto

Executando as funes da aplicao desenvolvida para a soluo dos problemas de localizao no-capacitado, obteve-se os resultados mostrados pela figura 22.

41

Figura 22 Soluo do problema de localizao no capacitado

A figura 22 mostra a soluo de um problema de localizao de 4 medianas. Os quatro clusters encontrados esto representados na figura em cores distintas, sendo o n mediana de cada cluster representado por um tringulo. Para efeito de comparao, apresenta-se a seguir (figura 23), a soluo obtida executando o algoritmo prprio do TransCAD.

Figura 23 Soluo do problema de localizao no capacitado pelo TransCAD

42

Os custos das solues apresentadas nas figuras 22 e 23 so mostradas na tabela a seguir. Algoritmo TransCAD P-Medianas (Senne e Lorena, 2000) Custo da Soluo 368.24 343.72

Para o problema no-capacitado de roteamento de veculos (ou seja, problemas de roteamento que cons ideram a capacidade dos veculos como ilimitada), o programa forneceu a distncia total a ser percorrida por um veculo, saindo do ponto correspondente mediana, passando por todos os ns associados e retornando ela. As rotas obtidas encontram-se na figura 24. As figuras 25, 26, 27 e 28 mostram de forma detalhada os resultados obtidos. fornecido tambm pelo programa, um arquivo .TXT informando a ordem das ruas pela qual o veculo deve viajar. Apresenta-se, a seguir, um exemplo de tal arquivo, referente ao primeiro cluster.

Figura 24 Soluo do problema de roteamento no capacitado

43

Figura 25 Roteamento no capacitado CLUSTER 1

44

Figura 26 Roteamento no capacitado CLUSTER 2

Figura 27 Roteamento no capacitado CLUSTER 3

45

Figura 28 Roteamento no capacitado CLUSTER 4

Para os problemas capacitados, foi utilizado o mapa de algumas rodovias brasileiras, por apresentar uma rede de pequeno porte (cerca de 100 ns). Os resultados obtidos so mostrados nas figuras 29, 30, 31 e 32.

46

Figura 29 Soluo do problema de localizao capacitado

De forma anloga soluo do problema de roteamento no capacitado, foram obtidas as rotas a serem percorridas por um veculo, saindo do ponto correspondente mediana, e visitando todos os ns associados ao cluster, e retornando ela.

47

Figura 30 Soluo do problema de roteamento capacitado

48

Figura 31 Roteamento capacitado CLUSTER 1

49

Figura 32 Roteamento capacitado CLUSTER 2

Para efeito de comparao mostra-se a seguir (figura 33) o resultado obtido executando o algoritmo prprio do TransCAD.

50

Figura 33 Soluo do problema de localizao capacitado pelo TransCAD

Os custos das solues apresentadas nas figuras 29 e 33 so mostradas na tabela a seguir. Algoritmo TransCAD P-Medianas (Senne e Lorena, 2000) Custo da Soluo 753.21 751.57

2.5 Comentrios Finais O projeto foi desenvolvido de acordo com o cronograma proposto. Na primeira etapa do projeto foi feito um levantamento bibliogrfico sobre problemas de localizao, os quais foram posteriormente utilizados na execuo dos algoritmos utilizados pelo TransCAD. Este levantamento bibliogrfico foi feito atravs da consulta em artigos, fornecidos pelo orientador, e pesquisas em sites na Internet. Foi feito tambm um estudo aprofundado do software TransCAD, e de todos os recursos por ele oferecidos. Este estudo baseou-se nas explicaes fornecidas pelo Manual do Usurio do TransCAD bem como informaes extras fornecidas pelo comando Help no meu de opes do programa. 51

Na segunda etapa do projeto, foi realizado um estudo aprofundado da linguagem de desenvolvimento GISDK, a fim de acoplar novos algoritmos ao sistema de informaes geogrficas TransCAD e criar interfaces grficas que permitam, de forma simples, interao do usurio com o programa. Para tal estudo, foi utilizado o manual de programao GISDK Geographic Information System Developers Kit e, principalmente, o sistema de ajuda fornecido pelo programa. Neste estudo foram criados pequenos programas para facilitar a interao do usurio com o TransCAD. Aps a assimilao da linguagem, foi possvel que programas mais complexos, utilizando as mais variadas funes da linguagem GISDK, fossem criados, e que um sistema de apoio deciso fosse construdo. Por apresentar inmeras funes, compreender e assimilar a linguagem GISDK no foram tarefas fceis, uma vez que o nico recurso disponvel foi o comando Help do programa, o qual apenas mostra como cada funo deve ser utilizada, no dando uma viso geral de quais so os recursos disponveis na linguagem. No desenvolvimento do projeto encontrou-se dificuldade em obter mapas de grandes cidades que pudessem ser utilizados, pois, alm de serem compatveis com o TransCAD, estes mapas deveriam conter as informaes necessrias para a soluo dos problemas (demanda e capacidade de cada n). Outro problema surgiu em funo das limitaes oferecidas pela linguagem GISDK. Conforme comentado anteriormente, algumas funes disponveis no TransCAD no esto disponveis na linguagem GISDK, o que limita a construo de Customs Applications. Por este motivo, no foi possvel, por exemplo, que a matriz de custos fosse gerada dentro da Custom Application, uma vez que a linguagem GISDK no apresenta nenhuma funo que execute tal tarefa. Como o sistema TransCAD apresenta um ambiente geral de desenvolvimento, em vez de utilizar uma Custom Application para desenvolver sistemas de apoio deciso, os programas de soluo de problemas de localizao e roteamento poderiam ser a cessados dentro do TransCAD, desde que fossem previamente compilados como add-ins. A desvantagem, neste caso, que o usurio no ir dispor de um ambiente especfico para a soluo de seus problemas de localizao e roteamento, devendo se habituar com a interface (bem mais complexa) do TransCAD. O Sistema de Apoio Deciso criado permite que o usurio estabelea a aplicao desejada, bem como escolher os mapas pertinentes a esta aplicao.

3. Referncias Bibliogrficas Bodin, L.; Golden, B.; Assad, A.; Ball, M. Routing and scheduling of vehicles and crews: the state of the art. Computers and Operations Research, 10(2): 65-211, 1983.

52

Brandeau, M.L.; Chiu, S.S. An overview of representative problems in location research. Management Science, vol 35 p.645 673, 1989 Caliper. GISDK Programmers Guide. Caliper Corporation, Newton, MA, 1999(a). Caliper. Routing and Logistics with TransCAD 3.6. Caliper Corporation, Newton, MA, 1999(b). Caliper. TransCAD Users Guide. Caliper Corporation, Newton, MA, 1999(c). Christofides, N.; Mingozzi, A.; Toth, P. The vehicle routing problem. In: Combinatorial Optimization, Christofides, N.; Mingozzi, A.; Toth P. and Sandi C. (eds.). John Wiley, 1979. Drezner, Z. (ed.) Facility Location: A Survey of Applications and Methods, Springer-Verlag, NY, 1995. ESRI. Understanding GIS: The ARC/INFO Method. Environmental Systems Research Institute, Inc., Redlands, CA, 1997. Fischbeck P. GIS: More than a Map. OR/MS Today, 42-45, Aug. 1994. Francis, R.L.; McGinnis, L.F.; White, J.A. Facility Layout and Location: An Analytical Approach, Prentice Hall, NJ, 1992. Gendreau, M.; Laporte G.; Potvin, J.Y. Vehicle routing: modern heuristics. In: Local Search in Combinatorial Optimization. E. Aarts and J.K. Lenstra (eds.), p. 311-336. John Wiley, 1997. Lorena, L.A.N.; Senne, E.L.F. A Lagrangean/Surrogate Heuristic for Uncapacitated Facility Location Problems. In: VIII CLAIO - Latin-Iberian-American Congress on Operations Research and System Engineering e XXVIII SBPO - Simpsio Brasileiro de Pesquisa Operacional, Rio de Janeiro, Ago. 1996. Lorena, L.A.N.; Senne, E.L.F. Improving traditional subgradient scheme for Lagrangean relaxation: an application to location problems, International Journal of Mathematical Algorithms, 1: 133-151, 1999. Lorena, L.A.N.; Senne, E.L.F. Local search heuristics for capacitated p- median problems. In: 17th European Conference on Operational Research, Budapest, Hungary, July, 2000. Lorena, L.A.N.; Senne, E.L.F.; Paiva, J.A.C.; Marcondes, S.P.B. Integrao de um Modelo de p-Medianas a Sistemas de Informaes Geogrficas. In: 31 Simpsio Brasileiro de Pesquisa Operacional, Juiz de Fora, MG, Out. 1999. Anais, p. 635-647. Love, R.F.; Morris, J.G.; Wesolowsky, G.O. Facilities Location: Models and Methods, North Holland, NY, 1988.

53

Mirchandani, P.B.; Francis, R.L. (eds.) Discrete Location Theory, Wiley Interscience, NY, 1990. Pinto, A.A.; Senne, E.L.F. Utilizao de Sistema de Informaes Geogrficas para Anlise de Redes. In: 11 Congresso de Iniciao Cientfica da Unesp, Araraquara, SP, Out. 1999. Resumos, p. 36. Senne, E.L.F.; Lorena, L.A.N. Lagrangean/Surrogate Heuristics for Facility Location Problems. In: EURO XV - INFORMS XXXIV Joint International Meeting. Barcelona, Espanha, Jul. 1997. Abstracts, p. 128. Senne, E.L.F.; Lorena, L.A.N. Lagrangean/Surrogate Heuristics for p-Median Problems. In: Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, M. Laguna and J.L. Gonzalez-Velarde (eds.), Kluwer Academic Publishers, p. 115-130, 2000. Senne, E.L.F.; Olivo, A.A. Um Ambiente Grfico para Resoluo de Problemas de Roteamento. In: 24 Simpsio Brasileiro de Pesquisa Operacional, Salvador, BA, Nov. 1992. Anais, p. 86-90. Slater, P.J. Locating a facility to service areas within a network . Standart Laboratories, Albuquerque, New Mexico, 1979, p. 523-524. Teitz, M.B.; Bart, P. Heuristic methods for estimating the vertex median of a weighted graph. Operations Research, 16: 955-961, 1968. Zocarato, C.A.; Senne, E.L.F. Anlise de Redes Urbanas com Sistema de Informaes Geogrficas. In: 11 Congresso de Iniciao Cientfica da Unesp, Araraquara, SP, Out. 1999. Resumos, p. 132.

54