A Modified Savings Algorithm Based Approach for Vehicle Routing Problem with Simultaneous Pick-up and Delivery

Abstract — A key element of many distribution systems is the routing and scheduling of vehicles through a set of nodes requiring service. The Vehicle Routing Problem (VRP) can be defined as a problem of finding the optimal routes of delivery or collection from one or several depots to a number of cities or customers, while satisfying some constraints. In many practical situations, however, the vehicle is often required to simultaneously drop off and pick up goods at the same stop. Vehicle routing problem with simultaneous pick-up and delivery (VRPSPD) is a variation of VRP in which customers require both pick-up and delivery simultaneously. The importance of reverse logistics increased the importance of VRPSPD. The present study focuses on VRPSPD. Savings Algorithm is a heuristic algorithm developed by Clarke and Wright to solve VRP. A new algorithm is developed by modifying savings algorithm to solve the problem. The developed algorithm is tested using problem instances from VRP library. Keywords—Vehicle routing problem, Reverse logistics, Vehicle routing problem with simultaneous pick – up and delivery, Savings Algorithm. I