A mixed constrained (identical) vehicle routing problem for time minimisation

This paper considers a version of the Vehicle Routing Problem (VRP) for time minimisation with mixed constraints (Precedence and Fixed Position). With ‘precedence’ constraints, the cities are visited in such a way that a particular city is preceded by another city (the precedence relation need not be immediate) and with ‘Fixed Position’ constraints, the positions of some cities are fixed at certain steps to be visited by a particular vehicle. Here all the vehicles are identical and have the same capacity. The constraints are assumed to be consistent so that feasible solutions exist. Except for assuring consistency, the two sets of constraints are independent of each other. The Lexicographic Search Approach has been employed here to solve a general VRP problem. A useful and effective lower bound is utilised for quick convergence to the optimum solution.