Vehicle Routing with Site-Vehicle Dependency Constraints

In the Vehicle Routing Problem (VRP), when the vehicles are of several types and capacities, and some of the customer sites are compatible with only some vehicle types, the VRP is said to have site-vehicle dependency constraints. The importance of the problem solution in the logistics industry has led to extensive research in academics and industry, resulting in the development of several heuristic solution techniques, none of which have addressed site-vehicle dependencies, which is the topic of this work. The VEHTYPE heuristic is a sequential procedure that works on one vehicle type at a time, using special decision rules for effectiveness and balanced utilization. More advanced heuristics are presented using Generalized Assignment, called GAP I, II, and III. GAP I and II depend on VEHTYPE for vehicle assignment. GAP III works directly from the input data. The results are validated on routes made by hand for problems of different sizes and levels of site dependencies. This is a new development in routing and scheduling, and work is of interest to all involved in routing and scheduling, as practitioners in industry, as research scientists, or as students.