Models And Algorithms Of Heterogeneous Multi-type Fleet Vehicle Routing Problems With Time Windows And An Incompatible Loading Constraint

As a branch of combinational optimization and operational research, vehicle routing problem has been widely researched since first proposed based on its economic and academic value. Vehicle routing problem tries to reduce the transporting cost by scheduling routes under the customer and vehicle constraints. Because of the complexity of real logistic, vehicle routing problem, as a subject, has developed a lot of variants.With the rising demand for cold chain, multi-temperature logistic has been paid more and more attention. There is such class of vehicle routing problem in real:The depot stores two types of vehicles, refrigerated and non-refrigerated vehicles, and three types of goods that must be transported by refrigerated vehicles, non-refrigerated vehicles, and both the two types of vehicles, respectively; meanwhile, the service time for each customer must be within the predefined time window. We call it as heterogeneous multi-type fleet vehicle routing problems with time windows and an incompatible loading constraint (HVRPTW-ILC).Considering the both constraints of time windows and loading constraints, it is quite difficult to optimize routes with the objective of reducing the total cost of routing time and vehicle fix costs.In this paper, we represent the mathematic model of HVRPTW-ILC and analysis of experimental results. The main research works are as follows:The mathematic model of HVRPTW-ILC has been presented. We compare HVRPTW-ILC with some existing VRP problems and introduce widely used heuristics of relating problems.Based on the particularity of HVRPTW-ILC, a modified CW is presented to generate an initial solution satisfying all constrains. Two comparable heuristics, a Ruin-Recreate heuristic and the Threshold Tabu search, are designed to further optimize solutions.We generate instances from the classical Solomon instance which is designed for VRPTW by adding particular constrains of HVRPTW-ILC. Two heuristics are tested on the instances and the efficiency and qualify are analyzed through the computational results.