A New Heuristic Algorithm for Multi Vehicle Routing Problem with AND/OR-Type Precedence Constraints and Hard Time Windows

Abstract

In this paper the classic known Multi Vehicle Routing Problem (VRP) is studied where classically several vehicles are set in a central depot, depending on the allocation strategy, each vehicle starts traveling to visit a set of nodes one after another to provide a service of gathering or delivering commodities with the aim of minimizing total traveling distances and costs. In the current paper, this classic problem is extended by new approach of AND/OR precedence constraints (PC) which have not been considered so far in the related literature. Traditionally, PC have been considered in VRPs as the 'AND' type, where the immediate successor of a node cannot be visited until its predecessor nodes have reached their end of services. However by additional OR-type precedence constraints, there are some interconnected nodes through the concept of OR, therein no mandatory need to visit all predecessors of a successor node is acquired before it can be met, and only finishing a part of them can let to that particular node to get visited. This fact is widely observed in pickup and routing and distribution real cases where requisites for some specific products can be fulfilled via various potential suppliers. Implementation of this type of PC graph in VRP is considered as the first introduction and application in the category of this problem. So, initially, the problem is mathematically formulated, then, due to problem’s NP-hard complexity and allocation-routing characteristics, a decomposition-based technique is utilized to solve the problem. The procedure is based on recently enhanced Benders’ decomposition approach named as Branch and Search Algorithm, partitioning the original main problem into allocation and routing parts. Unlike the previous version of Benders algorithm, logic based, this newly promoted method acts in a way that at the allocation level, it generates partition of nodes with feasible solutions in lower routing level. The routing part itself has been enhanced by heuristics to cover AND/OR PC graphs. Furthermore, the efficiency of the proposed solution procedure is tested and verified by running on several generated problems in different sizes and in the larger scale it is implemented on the real case of a distribution company in Iran.

Keywords

• Multi Vehicle Routing Problem
• AND/OR precedence constraints
• Hard Time Windows
• Branch and Search Algorithm