Vehicle routing problem with heterogeneous vehicles

The thesis presents a novel two-phase approach for heterogeneous fleet in Vehicle Routing Problem (VRP). In view of considerable difficulty to solve the class of VRP problem which is indeed NP-hard, different types of heuristics methodologies have been employed for the purpose of looking for good solutions which are comparable to optimal solution. It is commonly believed that VRP with heterogeneous fleet is even harder to solve than traditional VRP with homogeneous fleet. Therefore, it is necessary to develop methodologies to deal with VRP in heterogeneous case. Decomposition method, Cluster-First Route-Second, serves for this purpose. To this method, two phases are involved. Phase one aims at assigning clusters of customers to vehicles. In this phase, three integer programming models with idea of Continuous Approximation are introduced. Continuous Approximation is about partitioning an area into smaller zones so as to estimate route length. Validation and verification for the approximation are provided and discussed. Also, an idea of using a subset of different types of vehicles is included in the model. A number of computational enhancements applied to mathematical models are discussed and verified with experimental evidences. In phase two, routing or service sequence of customers for each vehicle is concerned. Tabu Search which is a metaheuristic is used to carry out a series of local searches for neighborhood solution to locate a good local optimum until a stopping criterion is reached. Once all routings are constructed, a complete VRP solution for heterogeneous fleet is known