  The multi Vehicle Routing Problem with Pickup and Delivery with Time Windows
is a challenging version of the Vehicle Routing Problem. In this paper, by
embedding many complex assignment routing constraints through constructing a
multi dimensional network, we intend to reach optimality for local clusters
derived from a reasonably large set of passengers on real world transportation
networks. More specifically, we introduce a multi vehicle state space time
network representation in which only the non dominated assignment based hyper
paths are examined. In addition, by the aid of passengers cumulative service
patterns defined in this paper, our solution approach is able to take control
of symmetry issue, a common issue in the combinatorial problems. At the end,
extensive computational results over the instances proposed by Ropke and
Cordeau 2009 and a randomly generated data sets from the Phoenix subarea, City
of Tempe, show the computational efficiency and solution optimality of our
developed algorithm.
