Le VRP permet de modéliser la problématique du TMV. Pour autant dans sa version la plus simpliste il ne peut convenir aux nouvelles contraintes qui renforcent la complexité de l’environnement urbain tel que la congestion. Raison pour laquelle ce travail se positionne en premier sur un TDVRP (Time-Dependent-Vehicle-Routing-Problem) dans le but de représenter au mieux le contexte urbain actuel. La résolution de ces deux problèmes est efficace, entraînant une réduction du nombre de véhicules supplémentaires nécessaires en raison des retards de congestion peuvent être éliminés. Mais cette solution n’est pas sans conséquence pour les clients finaux puisque son but est d’éviter le passage aux heures de pointes et cela peut engendrer des retards de livraison. Pour cette raison nous voulons proposer une nouvelle solution qui permet de résoudre le problème du chemin le plus court et en intégrant la dépendance au temps (TDVRP). Cette solution se repose sur une meilleure exploitation des véhicules, en premier lieu, pour réduire le nombre de véhicule sur la route. Ce problème s’appelle MT-VRP (Multi-Trip VRP) qui a été évoqué en 2007 par (Azi, et al. 2007). Dans un deuxième temps nous voulons proposer un MT VRP qui utilise différents types de véhicule en termes de capacité de chargement. Dans cette optique vient notre travail qui propose une nouvelle solution de MTTDVRP (TW avec fenêtres de temps) en testant une nouvelle solution en utilisant un véhicule léger de faible capacité de chargement (type tricycle) dans un but de réduire les nuisances liés au TMV. / The VRP makes it possible to model the problem of TMV. However, in its most simplistic version it cannot be adapted to the new constraints which reinforce the complexity of the urban environment such as congestion. This is why this work is placed first on a TDVRP (Time-dependent-Vehicle-Routing-Problem) in order to best represent the current urban context. The resolution of these two problems is effective; resulting in a reduction in the number of additional vehicles needed due to congestion delays can be eliminated. But this solution is not without consequences for end customers since its goal is to avoid the switch to peak hours and this can lead to delivery delays. For this reason we want to propose a new solution that solves the problem of the shortest path and integrating time dependency (TDVRP). This solution relies on better operation of vehicles, in the first place, to reduce the number of vehicles on the road. This problem is called MT-VRP (Multi-Trip VRP) which was raised in 2007 by (Azi, et al. 2007). In a second step we want to propose a MT VRP that uses different types of vehicle in terms of loading capacity. In this perspective comes our work that proposes a new solution of MTTDVRP (TW with time windows) by testing a new solution using a light vehicle of low load capacity (tricycle type) in order to reduce the nuisance associated with TMV.

Hoy en día, de los costos de logística de las empresas, más de la mitad corresponden a costos de transporte, siendo uno de los problemas importantes a resolver el del ruteo de vehículos (VRP), que consiste en determinar las mejores rutas para entregar – desde una bodega - productos o servicios a los clientes quienes están dispersos geográficamente. Existen muchos programas comerciales que lo resuelven, pero son de un alto precio, sobre todo para las pymes. Es así que se hace necesario entregar una solución de bajo costo, por ejemplo a través del reuso de componentes de software. Uno de los enfoques más usados son los frameworks, que son una arquitectura de software incompleta que el desarrollador adapta a las necesidades del problema específico. En este trabajo se desarrolló un framework orientado a objetos para el problema de ruteo de vehículos, a partir de diversos esquemas UML que se implementaron. El mecanismo de desarrollo fue similar al de un software sólo que siempre había que tener en mente que se debía abstraer a un problema VRP lo más genérico posible. En específico se desarrolló un completo diagrama de clases del problema, que comprende los métodos de resolución del problema. En esta tesis se estudiaron en específico las heurísticas que son el enfoque más difundido. También se desarrolló un mecanismo de mapeo entre métodos de solución y problemas, que permite asociar un problema específico con una heurística específica que lo resuelve. Para comprobar el funcionamiento del framework se desarrolló un software que lo instanciara. Con este software se realizaron algunas pruebas con problemas aleatorios e instancias conocidas del VRP, obteniendo buenos resultados. Finalmente se hizo un análisis costo-beneficio que mostró que el reuso de software es una alternativa viable económicamente, en comparación con desarrollar múltiples programas. Como trabajo futuro queda comprobar que otros desarrolladores puedan usar el framework de manera fácil, y para el dominio que aquí se definió. Por otro lado sería interesante desarrollar frameworks para otros problemas de gestión de operaciones como: asignación de tripulación o ubicación de instalaciones.

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.

The Vehicle Routing Problem with Time Windows (VRPTW) is an important and computationally hard optimization problem frequently encountered in Scheduling and logistics. The Vehicle Routing Problem (VRP) can be described as the problem of designing the most efficient and economical routes from one depot to a set of customers using a limited number of vehicles. This research addresses the VRPTW under the following additional complicating features that are often encountered in practical problems: 1. Customers have strict time windows for receiving a vehicle, i.e., vehicles are not allowed to arrive at the customer’s location earlier than the lower limit of the specified time window, which is relaxed in previous research work. 2. There is a limited number of loading/unloading docks for dispatching/receiving the vehicles at the depot The main goal of this research is to propose a framework for solving the VRPTW with the constraints stated above by generating near-optimal routes for the vehicles so as to minimize the total traveling distance. First, the proposed framework clusters customers into groups based on their proximity to each other. Second, a Probabilistic Route Generation (PRG) algorithm is applied to each cluster to find the best route for visiting customers by each vehicle; multiple routes per vehicle are generated and each route is associated with a set of feasible dispatching times from the depot. Third, an assignment problem formulation determines the best dispatching time and route for each vehicle that minimizes the total traveling distance. iii The proposed algorithm is tested on a set of benchmark problems that were originally developed by Marius M. Solomon and the results indicate that the algorithm works well with about 1.14% average deviation from the best-known solutions. The benchmark problems are then modified by adjusting some of the customer time window limits, and adding the staggered vehicle dispatching constraint. For demonstration purposes, the proposed clustering and PRG algorithms are then applied to the modified benchmark problems.