Atenção: esse artigo tem um vídeo complementar. Clique e assista!
Ele descreve uma possível solução para um problema de roteamento através de bancos de dados utilizando stored procedures no SQL Server com a aplicação do algoritmo de Dijkstra.
Para que serve:
Expor ao leitor o problema de roteamento aplicado em banco de dados e através do algoritmo de Dijkstra, calcular de maneira otimizada o caminho de custo mínimo.
Em que situação o tema é útil:
Em todas as situações que envolverem rotas, percursos, caminhos onde cada um desses percursos tem um valor atribuído, e deseja-se saber qual o menor custo de caminhamento entre dois pontos a partir de dados armazenados em bancos de dados.
Um problema muito comum em empresas de diversos ramos de atividade é aquele que diz respeito à logística de entrega de suas mercadorias. Grandes fornecedores precisam distribuir cargas aos seus distribuidores, que por sua vez também precisam fazer entregas a seus clientes diretos. A quantidade de variáveis envolvidas no cálculo do custo da entrega pode dificultar uma análise mais precisa da melhor rota a ser adotada e demandar um trabalho braçal muito grande para chegar a tais resultados. Há, nesse cenário, uma necessidade de automação muito grande. Dentre as várias ferramentas e técnicas disponíveis, esse artigo propõe o uso de procedimentos armazenados em banco de dados.
Os procedimentos armazenados (chamaremos a partir de agora pelo termo mais conhecido em inglês = stored procedures) representam a parte programática de um banco de dados. Em determinadas situações, possuem vantagens sobre a manipulação de bancos de dados em código fonte e constituem-se de uma poderosa ferramenta muitas vezes desconsiderada em casos indicativos de sua utilização.
O banco de dados a ser utilizado neste artigo é o SQL Server da Microsoft, que na verdade é um SGBD (Sistema Gerenciador de Banco de Dados) e é um líder de mercado dentre seus pares. Em seu ambiente é possível construir e depurar stored procedures em uma linguagem padrão ANSI/ISO compatível com muitos outros SGBD’s.
Neste artigo, iremos propor então, a implementação de um algoritmo de roteamento em um cenário de entrega de mercadorias, utilizando-se das stored procedures em SQL Server. Apresentaremos o cenário no qual será aplicado o roteamento, sua modelagem computacional, uma rápida conceituação de um algoritmo de roteamento e stored procedures. Em seguida, esboçamos o algoritmo no SQL Server 2005.
Um cenário de problema de roteamento
O setor de logística de uma empresa normalmente é aquele responsável pela carga e a liberação de veículos para entregas em seus destinos. Esse processo de carregar e liberar o caminhão pode ser muito complexo e envolver muitas variáveis. No momento de decidir o carregamento, é preciso definir quantitativamente e qualitativamente o que vai ser carregado, e em função disso decidir qual o veículo a ser utilizado, tomando-se o cuidado de evitar que veículos trafeguem com um volume muito abaixo de sua capacidade, gerando ociosidade no transporte. Cada veículo tem um custo associado que inclui sua depreciação e consumo de combustível. Cada viagem tem também associado o valor da hora do condutor e suas despesas pessoais como alimentação e transporte. Essas são algumas das variáveis envolvidas em um sistema de logística de transporte.
Trata-se de uma atividade bastante dinâmica na qual a tomada de decisão deve ser muito rápida. O departamento responsável por tal decisão trabalha com muitas variáveis, vindas de vários departamentos da empresa, como finanças, recursos humanos, controle de patrimônio, estoque e faturamento. A saída de um veículo para a entrega é o resultado final de um trabalho intenso de análise de dados. O fluxo diário de veículos de transporte associado a uma demanda normalmente crescente de entregas gera um ambiente no qual a automação das atividades é imprescindível. Várias soluções de automação existentes no mercado disponibilizam funcionalidades muito úteis para a logística.
No entanto, nota-se que o esforço normalmente é dirigido em determinar o custo de uma rota específica. De posse desse valor, cuida-se que esse custo seja repassado ao setor financeiro e comercial que irá incorporá-lo na composição do valor de venda de cada item comercializado.
Outra informação importante muitas vezes não considerada é a comparação de custo entre as rotas existentes. Qual seria a rota com menor custo possível, tendo sido levado em consideração todas as variáveis possíveis? Quando essa comparação é efetuada, uma quantidade mínima de variáveis é considerada, como quilometragem e consumo do veículo, em função da dificuldade de considerar o cenário completo, e muitas vezes também em função da falta de ferramenta computacional com essa funcionalidade.
Responder à pergunta do parágrafo anterior é o que se propõe neste artigo. Trata-se de desenvolver um algoritmo para cálculo do custo mínimo a partir de dados disponíveis no banco de dados de uma empresa. Dados os percursos, cada um com seu custo, qual é a rota com o menor custo possível entre dois pontos?
...
