A heuristic algorithm for the multi-period vehicle routing problem with simultaneous pickup and delivery service

Many companies have a central depot to store raw materials and finished products. There are many factories located around the central depot. Each factory has a demand of pickup for the finished products and a demand of delivery for raw materials. During each day within the planning period, a fleet of capacitated vehicles traveling along routes which begin and end at the central depot are needed to transport the raw materials and the finished products between them. A special constraint of this problem is that the pickup demand has to be satisfied exactly on the date of appointment, but delivery demand can be satisfied on or before the date of appointment. Thus we propose a multi-period vehicle routing problem with simultaneous pickup and delivery service (MPVRPSPD) model for this problem. A heuristic algorithm, based on tabu search, is presented and computational results are given as well