Meta-heuristic Solution Methods for Rich Vehicle Routing Problems

For more than half of century, since the paper of Dantzig and Ramser (1959)  was introduced, the Vehicle Routing Problem (VRP) has been one of the most extensively studied problems in operations research due to its methodological interest and practical relevance in many fields such as transportation, logistics, telecommunications, and production. The general goal of the VRP is to optimize the use of transportation resources to service customers with respect to side-constraints deriving from real-world applications.  The practical applications of the VRP may have a variety of constraints, and obviously, the larger the set of constraints that need to be considered, i.e., corresponding to `richer' VRPs, the more difficult the task of problem solving. The needs to study closer representations of actual applications and methodologies producing high-quality solutions quickly to larger-sized application problems have increased steadily, providing significant challenges for the VRP research community. This dissertation explores these extensional issues of the VRP.  The first part of the dissertation addresses the Periodic Vehicle Routing Problem with Time Windows (PVRPTW) which generalizes the classical Vehicle Routing Problem with Time Windows (VRPTW) by extending the planning horizon to several days where customers generally do not require delivery on every day, but rather according to one of a limited number of possible combinations of visit days. This generalization extends the scope of applications to many commercial distribution activities such as waste collection, street sweeping, grocery distribution, mail delivery, etc. The major contribution of this part is the development of a population-based hybrid meta-heuristic in which a set of local search procedures and neighborhood-based meta-heuristics cooperate with the genetic algorithm population evolution mechanism to enhance the solution quality as well as to promote diversity of the genetic algorithm population. The results show that the proposed methodology is highly competitive, providing new best solutions in some large instances.  The second part of the dissertation aims to present, model and solve two rich vehicle routing problems which further extend the VRPTW with time-dependent demands of pickup and delivery, and hard time synchronization restrictions. They are called Time-dependent Multi-zone Multi-Trip Vehicle Routing Problem with Time Windows (TMZT-VRPTW), and Multi-zone Mult-Trip Pickup and Delivery Problem with Time Windows and Synchronization (MZT-PDTWS), respectively. These two problems originate from planning the operations of two-tiered City Logistics systems. The difficulty of these problems lies in handling two intertwined sets of decisions: the routing component which aims to determine the sequences of customers visited by each vehicle, and the scheduling component which consists in planning arrivals of vehicles at facilities within hard time synchronization restrictions. Previously, these issues have been addressed separately. Combining these decisions into one formulation and solution method should yield better results. In this dissertation we propose meta-heuristics that address the two decisions simultaneously, in a comprehensive and efficient way. Experiments confirm the good performance of the proposed methodology compared to the literature, providing system managers with solution requiring less vehicles and travel costs to perform efficiently the same amount of work. In the context of City Logistics systems, our results indicate a reduction in the presence of vehicles on the streets of the city and, thus, in their negative impact on congestion and environment.

Keyphrases: Vehicle routing problem, Pickup and delivery, Time-dependent demand, Synchronization, Meta-heuristic, Hybrid generational genetic algorithm, Tabu search