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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Efficient Heuristic to Solve the Multi-pickup and Delivery Problem with Time Windows

  • Salma Bouhlla,
  • Rym Guibadj,
  • Aziz Moukrim

摘要

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.