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.

About Statistics, modelling and operations research seminars

Students, staff and visitors to UQ are welcome to attend our regular seminars.

The events are jointly run by our Operations research and Statistics and probability research groups.

The Statistics, modelling and operations research (SMOR) Seminar series seeks to celebrate and disseminate research and developments across the broad spectrum of quantitative sciences. The SMOR series provides a platform for communication of both theoretical and practical developments, as well as interdisciplinary topics relating to applied mathematics and statistics.


Priestley Building (67)