Greedy strategy based heuristic for Vehicle Routing Problems with unpaired pickup and delivery

The Vehicle Routing Problem with unpaired Pickup and Delivery Problem is studied in order to schedule vehicle routes with the lowest cost under the mileage and time windows limitations in this paper. It is the extension class of the traditional Vehicle Routing Problem, where a goods transportation consists of several tasks, goods are transported task by task and in each task from one pickup point to many delivery points. A two-stage greedy strategy is put forward: the inner task routing is determined in the first stage and the routings between tasks are established in the second stage. The mathematical formulas for these two stages under the single depot and sole vehicle mode, and with the mileage limit and time window constraints are set up and the two stage greedy algorithms and improved Clarke-Wright saving algorithm are designed. The test cases are implemented and the results show that the two-stage greedy algorithm is feasible and effective, and it can get more reasonable results than the improved Clarke-Wright in mileage and cost saving in enclosed model. The results of the improved Clarke-Wright algorithm are further discussed. The proposal on dividing the whole transportation area into several regions and routing in the separated region is put forward.