Constructing initial solutions for the multiple vehicle pickup and delivery problem with time windows

The Multiple Vehicle Pickup and Delivery Problem with Time Windows (MV-PDPTWs) is an important problem in logistics and transportation. However, this problem is characterized by having a large number of constraints that are difficult to deal with in a solution algorithm. Indeed, merely constructing a feasible solution to this hard problem is a challenge in itself. In this research, we compare several construction algorithms that generate initial feasible solutions to the problem. The suggested algorithms all utilize a simple routing heuristic to create individual vehicle routes. The algorithms differ, though, in whether routes are generated sequentially or in parallel. They also have different criteria for selecting requests and the routes in which they will be inserted. Inserting a request in a route is either based on a first acceptance criterion, in which a request is inserted in the first route where a feasible insertion is found, or a best acceptance criterion, in which a request is inserted in the estimated best route for insertion. Experimental results on several benchmark problem instances indicate that the sequential construction heuristic may be the most suitable construction algorithm for this problem, in terms of simplicity of coding, solution quality as well as processing speed.1This paper is part of the PhD thesis of the first author (Hosny, 2010), and it is an expanded version of the MIC2009 conference paper (Hosny and Mumford, 2009).