Multi-Period Pickup and Delivery Problem with Time Windows and Paired Demands

This paper addresses the Multi-Period Pickup and Delivery Problem with Time Windows and Paired Demands (Mu-PDPTWPD). A first strategy consists in dealing with the problem as a whole. A second one is to consider the studied problem as a sequence of mono-period selective PDPTWPDs. The Mu-PDPTWPD is an extension of well-known pick up and delivery problem where vehicles must satisfy a set of transportation requests under many constraints. The Multi-Period aspect is added to the problem to match real-world applications where sites must be visited one time during a set of periods. In this paper, we propose several methods to solve this problem. The efficiency of our approaches is validated by tests on two sets of new generated instances. A comparison between all proposed approaches is done in order to trace the advantages and drawbacks for each of them.