A Customized Tabu Search for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery

Abstract

The Vehicle Routing Problem with Simultaneous Pick-up and Delivery (VPSPD) is classified as one of the most complicated and challenging Routing Problems. Having both pick-up and delivery loads at the same customer makes total loads uncertain on the vehicles along all their service routes. This paper presents an implementation of the Savings method for finding initial solutions of 72 benchmark instances. After that, an adaptive metaheuristic, Customized Tabu Search was applied in order to improve those initial solutions. The unique aspects of this search are the acceptance of the move which is tabu with some ‘allowance’ value and the extension of the tabu tenure with some ‘penalty’ charges. The allowance and penalty values used in each problem are varied by the problem’s size. The results indicate a number of new best known solutions found by this proposed method compared with previous research.