EURO 2025 Leeds
Abstract Submission

782. Effective compact formulation for the Pickup-and-Delivery Problem with Time Windows and Transshipment

Invited abstract in session TA-17: Modeling and competitive analysis in routing and covering problems, stream Combinatorial Optimization.

Tuesday, 8:30-10:00
Room: Esther Simpson 2.08

Authors (first author is the speaker)

1. Luis Rocha
University of Passau
2. Alena Otto
Technical University of Munich

Abstract

The pickup-and-delivery problem with time windows (PDPTW) and transshipments (PDPT) is a generalization of the vehicle routing problem (VRP). Unlike VRP, where deliveries are made to a central depot, PDPTW treats the delivery address of a customer request as an input, allowing it to be any node in the network. Applications include ridesharing, where passenger requests with predefined pickup and drop-off points are assigned to shared vehicles and same-day deliveries, such as food or retail item deliveries from specific restaurants or shops. In all these applications, each request is associated with a time window. To meet time constraints and reduce costs, logistics companies increasingly consider transshipments as in the PDPT, where a request can be transferred between vehicles.
We design a compact mixed-integer linear program (MILP) for PDPT. A compact formulation removes the vehicle index to eliminate much of the inherent model symmetry. Compact formulations are valuable due to their ease of implementation in off-the-shelf solvers, and adaptability to problem extensions. We build on existing compact formulations for related problem classes and develop novel strengthened inequalities.
Our model significantly outperforms state-of-the-art model formulations, solving 89% of benchmark instances. It achieves a 90% and 52% reduction in run time for instances with up to 15 and 30 requests, respectively. Our model also significantly outperforms existing MILPs for the PDPTW.

Keywords

Status: accepted

Back to the list of papers