Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

MasterThe vehicle routing problem with simultaneous pickup and delivery (VRPSPD) is a variation of the capacitated vehicle routing problem, in which both pickup and delivery tasks occur at customer locations simultaneously. The objective is to design a set of minimum distance routes for the vehicle routing assignment. This paper presents a heuristic algorithm consisting of the route construction procedure and the route improvement procedure. There are two main contributions. First, a new sweep based route construction method generates better initial solutions. Our proposed method focuses on the construction of initial solution, while most previous researches for VRPSPD focus on the improvement of initial solution. Second, when each improvement try, potential region method is applied for more effeicient improvement. Computational experiments on various benchmark instances are performed to evaluate our algorithm against the previously proposed approaches