An integrated and intelligent metaheuristic for constrained vehicle routing

Abstract

South African metropolitan areas are experiencing rapid growth and require an increase in network infrastructure. Increased congestion negatively impacts both public and freight transport costs. The concept of City Logistics is concerned with the mobility of cities, and entails the process of optimizing urban logistics activities by concerning the social, environmental, economic, financial, and energy impacts of urban freight movement. In a costcompetitive environment, freight transporters often use sophisticated vehicle routing and scheduling applications to improve fleet utilization and reduce the cost of meeting customer demands. In this thesis, the candidate builds on the observation that vehicle routing and scheduling algorithms are inherent problem specific, with no single algorithm providing a dominant solution to all problem environments. Commercial applications mostly deploy a single algorithm in a multitude of environments which would often be better serviced by various different algorithms. This thesis algorithmically implements the ability of human decision makers to choose an appropriate solution algorithm when solving scheduling problems. The intent of the routing agent is to classify the problem as representative of a traditional problem set, based on its characteristics, and then to solve the problem with the most appropriate solution algorithm known for the traditional problem set. A not-so-artificially-intelligent-vehicle-routing-agent™ is proposed and developed in this thesis. To be considered intelligent, an agent is firstly required to be able to recognize its environment. Fuzzy c-means clustering is employed to analyze the geographic dispersion of the customers (nodes) from an unknown routing problem to determine to which traditional problem set it relates best. Cluster validation is used to classify the routing problem into a traditional problem set. Once the routing environment is classified, the agent selects an appropriate metaheuristic to solve the complex variant of the Vehicle Routing Problem. Multiple soft time windows, a heterogeneous fleet, and multiple scheduling are addressed in the presence of time-dependent travel times. A new initial solution heuristic is proposed that exploits the inherent configuration of customer service times through a concept referred to as time window compatibility. A high-quality initial solution is subsequently improved by the Tabu Search metaheuristic through both an adaptive memory, and a self-selection structure. As an alternative to Tabu Search, a Genetic Algorithm is developed in this thesis. Two new crossover mechanisms are proposed that outperform a number of existing crossover mechanisms. The first proposed mechanism successfully uses the concept of time window compatibility, while the second builds on an idea used from a different sweeping-arc heuristic. A neural network is employed to assist the intelligent routing agent to choose, based on its knowledge base, between the two metaheuristic algorithms available to solve the unknown problem at hand. The routing agent then not only solves the complex variant of the problem, but adapts to the problem environment by evaluating its decisions, and updating, or reaffirming its knowledge base to ensure improved decisions are made in future.