Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up

Recently, the increasing focus on environmental protection has led to significant changes in logistics processes. In addition to the distribution process to the customers, re-usable packaging and goods to be recycled or remanufactured have to be transported in the reverse direction. If both tasks have to be performed simultaneously at the customers' locations which are serviced by a fleet of vehicles stationed in a depot or distribution/redistribution center, the vehicle routing problem with simultaneous delivery and pick-up arises. In this paper, the relation between this problem and other vehicle routing problems is investigated. A heuristic construction procedure is suggested. The proposed algorithm is successfully applied to a real-life problem as well as test instances introduced in the literature earlier. In addition, randomly generated instances are tackled in order to try to determine favorable settings for the parameters used in the solution approach.