A Matheuristic Approach to the Pickup and Delivery Problem with Time Windows

摘要

In this work, the Pickup and Delivery Problem with Time Windows is studied. It is a combinatorial optimization problem, in which the objective is to construct the best set of vehicle routes while respecting side constraints, such as precedence between locations to be visited; and the time to service them. To tackle this problem, a matheuristic based on Iterated Local Search method is proposed, with an embedded Set Partitioning Problem that is iteratively solved to recombine routes of previously found solutions. Results indicate the approach works well for a standard benchmark set of instances from the literature. A number of new best-known solutions has been found.