Efficient Heuristic to Solve the Multi-pickup and Delivery Problem with Time Windows
摘要
This paper addresses the Multi-Pickup and Delivery Problem with Time Windows (MPDPTW), an extension of the well-known Pickup and Delivery Problem (PDP). Unlike the PDP, where each request involves one pickup and one delivery, the MPDPTW involves multiple pickups from different locations for a single delivery point. The objective is to minimize logistics costs while respecting time constraints. In this paper, we propose an efficient heuristic that relies on an advanced construction operator that explicitly states precedence constraints to construct high-quality solutions. Experimental results on the MPDPTW benchmark demonstrate that our approach matches all the best-known results from the existing literature and achieves a strict improvement in the relative gap for several instances, with an average enhancement of 0.2%. These results establish our method as the new state-of-the-art for solving the MPDPTW.