This dissertation presents a cartographic approach to the dynamic vehicle routing problem with time windows and stochastic customers (DVRPTWSC). The objectives are to minimize the total travel time and maximize the number of new requests served. Addressing the DVRPTWSC requires solving the vehicle routing problem with time windows (VRPTW). A memetic algorithm (MA) for the VRPTW is proposed. The MA prunes the search space using the information gathered by a clustering procedure, which is applied to customers spatial data. The cartographic approach to the DVRPTWSC is incorporated into a multiagent system where a dispatcher agent plans the routes for vehicle agents. Before creating the initial routing plan, a cartographic processing is applied. This procedure uses hierarchical clustering to divide the region where customers are located into a hierarchy of nested regions. The initial routing plan considers known requests and potential requests sampled from known probability distributions. It is created using the search operators of the MA, which in turn use the information obtained from the hierarchical clustering to perform the search. Over the planning horizon, the dispatcher updates the routing plan: Potential requests that were included in the initial routing plan and do not materialize are removed and new requests are processed using the assignation of requests based on nested regions (ARNR). The ARNR procedure is aimed at reducing the number of vehicles considered for serving new requests. It tries to assign the requests among the vehicles that can serve them at low detour costs. The nested regions created in the cartographic processing are used to identify such vehicles. Experimental results show that the proposed MA performs competitively with state-of-the-art heuristics for the VRPTW. The proposed approach to the DVRPTWSC outperforms approaches that do not include potential requests in the initial routing plan. The use of the ARNR procedure significantly reduces the number of vehicles considered for serving new requests, and it yields solutions similar to those obtained when considering all vehicles in operation. The proposed approach performs consistently under three levels of dynamism: low, medium, and high. / Esta dissertação apresenta uma abordagem cartográfica para o problema de roteamento de veículos dinâmico com janelas de tempo e clientes estocásticos (DVRPTWSC, por sua sigla em inglês). Os objetivos considerados são minimizar o tempo total de viagem e maximizar o número de pedidos novos atendidos. Para abordar o DVRPTWSC é necessário resolver o problema de roteamento de veículos com janelas de tempo (VRPTW, por sua sigla em inglês). Assim, para tratar o VRPTW propõe-se um algoritmo memético (MA, por sua sigla em inglês). O MA reduz o espaço de busca usando informação obtida por meio de um procedimento de clusterização, o qual é aplicado aos dados espaciais dos clientes. Para o DVRPTWSC, a abordagem cartográfica é incorporada em um sistema multiagente, no qual um agente roteirizador planeja as rotas para os agentes veículos. O processamento cartográfico é aplicado antes de criar o plano de rotas inicial para o DVRPTWSC. Este procedimento usa clusterização hierárquica para dividir a região onde estão os clientes em uma hierarquia de regiões encaixadas. O plano de rotas inicial considera pedidos conhecidos e pedidos potenciais amostrados de distribuições de probabilidade conhecidas. Para obter o plano de rotas inicial, usam-se os operadores de busca do MA, os quais utilizam a informação obtida da clusterização hierárquica para fazer a busca. Ao longo do horizonte de planejamento, o roteirizador atualiza o plano de rotas: Pedidos potenciais que foram considerados no plano de rotas inicial e que não foram consolidados são removidos e novos pedidos são incluídos usando o procedimento assignation of requests based on nested regions (ARNR). O procedimento ARNR visa reduzir o número de veículos considerados para atender novos pedidos. Para isso, tenta designar os novos pedidos aos veículos disponíveis para o atendimento que possuem os menores custos de desvio da rota pré-determinada. As regiões encaixadas criadas no processamento cartográfico são utilizadas para identificar esses veículos. Para o VRPTW, resultados experimentais mostram que o MA proposto é competitivo com métodos do estado da arte. A abordagem proposta para o DVRPTWSC supera abordagens que não incluem pedidos potenciais no plano de rotas inicial. O uso do procedimento ARNR reduz significativamente o número de veículos considerados para atender novos pedidos, e produz soluções similares às produzidas quando se consideram todos os veículos em operação. A abordagem desenvolvida para o DVRPTWSC tem um desempenho consistente para três níveis de dinamismo: baixo, médio e alto.

This dissertation presents a cartographic approach to the dynamic vehicle routing problem with time windows and stochastic customers (DVRPTWSC). The objectives are to minimize the total travel time and maximize the number of new requests served. Addressing the DVRPTWSC requires solving the vehicle routing problem with time windows (VRPTW). A memetic algorithm (MA) for the VRPTW is proposed. The MA prunes the search space using the information gathered by a clustering procedure, which is applied to customers spatial data. The cartographic approach to the DVRPTWSC is incorporated into a multiagent system where a dispatcher agent plans the routes for vehicle agents. Before creating the initial routing plan, a cartographic processing is applied. This procedure uses hierarchical clustering to divide the region where customers are located into a hierarchy of nested regions. The initial routing plan considers known requests and potential requests sampled from known probability distributions. It is created using the search operators of the MA, which in turn use the information obtained from the hierarchical clustering to perform the search. Over the planning horizon, the dispatcher updates the routing plan: Potential requests that were included in the initial routing plan and do not materialize are removed and new requests are processed using the assignation of requests based on nested regions (ARNR). The ARNR procedure is aimed at reducing the number of vehicles considered for serving new requests. It tries to assign the requests among the vehicles that can serve them at low detour costs. The nested regions created in the cartographic processing are used to identify such vehicles. Experimental results show that the proposed MA performs competitively with state-of-the-art heuristics for the VRPTW. The proposed approach to the DVRPTWSC outperforms approaches that do not include potential requests in the initial routing plan. The use of the ARNR procedure significantly reduces the number of vehicles considered for serving new requests, and it yields solutions similar to those obtained when considering all vehicles in operation. The proposed approach performs consistently under three levels of dynamism: low, medium, and high. / Esta dissertação apresenta uma abordagem cartográfica para o problema de roteamento de veículos dinâmico com janelas de tempo e clientes estocásticos (DVRPTWSC, por sua sigla em inglês). Os objetivos considerados são minimizar o tempo total de viagem e maximizar o número de pedidos novos atendidos. Para abordar o DVRPTWSC é necessário resolver o problema de roteamento de veículos com janelas de tempo (VRPTW, por sua sigla em inglês). Assim, para tratar o VRPTW propõe-se um algoritmo memético (MA, por sua sigla em inglês). O MA reduz o espaço de busca usando informação obtida por meio de um procedimento de clusterização, o qual é aplicado aos dados espaciais dos clientes. Para o DVRPTWSC, a abordagem cartográfica é incorporada em um sistema multiagente, no qual um agente roteirizador planeja as rotas para os agentes veículos. O processamento cartográfico é aplicado antes de criar o plano de rotas inicial para o DVRPTWSC. Este procedimento usa clusterização hierárquica para dividir a região onde estão os clientes em uma hierarquia de regiões encaixadas. O plano de rotas inicial considera pedidos conhecidos e pedidos potenciais amostrados de distribuições de probabilidade conhecidas. Para obter o plano de rotas inicial, usam-se os operadores de busca do MA, os quais utilizam a informação obtida da clusterização hierárquica para fazer a busca. Ao longo do horizonte de planejamento, o roteirizador atualiza o plano de rotas: Pedidos potenciais que foram considerados no plano de rotas inicial e que não foram consolidados são removidos e novos pedidos são incluídos usando o procedimento assignation of requests based on nested regions (ARNR). O procedimento ARNR visa reduzir o número de veículos considerados para atender novos pedidos. Para isso, tenta designar os novos pedidos aos veículos disponíveis para o atendimento que possuem os menores custos de desvio da rota pré-determinada. As regiões encaixadas criadas no processamento cartográfico são utilizadas para identificar esses veículos. Para o VRPTW, resultados experimentais mostram que o MA proposto é competitivo com métodos do estado da arte. A abordagem proposta para o DVRPTWSC supera abordagens que não incluem pedidos potenciais no plano de rotas inicial. O uso do procedimento ARNR reduz significativamente o número de veículos considerados para atender novos pedidos, e produz soluções similares às produzidas quando se consideram todos os veículos em operação. A abordagem desenvolvida para o DVRPTWSC tem um desempenho consistente para três níveis de dinamismo: baixo, médio e alto.