An exact algorithm for the Pickup and Delivery Problem with Time Windows and LIFO Loading

Speaker: Dr Ali Al-Yasiry (The University of Queensland)

Research on exact methods to solve the pickup and delivery problem with time windows (PDPTW) and its variants has mainly focused on branch and price and cut algorithms. We propose a novel exact approach based on fragments - a series of pickup and delivery requests starting and ending with an empty vehicle. Using fragments, we formulate an optimistic network flow model with side constraints and use lazy constraints to cut off any illegal solutions generated while solving the resultant integer program.

We first reduce the number of variables by generating fragments and connecting these fragments through a network flow formulation. Every chain of fragments is a valid vehicle route. If not, we add a lazy constraint to cut off the combination of variables corresponding to the smallest portion of the chain that is illegal.

The talk will focus on the last-in-first-out (LIFO) loading constraints variant (PDPTWL). Applications of the PDPTWL can be found in the transportation of animals, heavyweight goods and hazardous materials, where unloading vehicles requires more time and special handling. Examples include carrying livestock, cars and chemical containers. Computational experiments show that the proposed algorithm significantly outperforms the only other exact method for the PDPTWL.