Exact Algorithms for the Vehicle Routing Problems with Pickups and Deliveries

Transportation plays a major role in economic growth by linking people to resources. It has a direct impact on business activity such as productivity, employment and accessing to new markets. People are either customers seeking quality transportation services or providing transportation services for profit. Operations Research (OR) has been extensively used to enhance the performances of transportation applications via varieties of optimization techniques. Typically, the aims are to reduce the operation time and cost and to minimize the negative effects of the transportation on the ecosystem. Computational experiments showed that significant savings on times and costs of the transportation operations can be achieved using computerized solution techniques based on mathematical models.

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 developed novel exact algorithms for solving some complicated PDPTW variants. Computational experiments show that our algorithms significantly outperform the current state-of-the-art methods.

The talk will focus on two important PDPTW variants namely the PDPTW with last-in-first-out (LIFO) loading (PDPTWL) and the PDPTW with multi-stack (PDPTWMS). Applications of these variants can be found in the transportation of pallets, animals, heavyweight goods and hazardous materials, where unloading vehicles requires more time and special handling. Examples include carrying livestock, cars and chemical containers.

Short Bio:

Ali Alyasiry is a PhD student doing research in the field of Operations Research at the School of Mathematics and Physics. He has BSc. in Statistics and M.Sc. in Operations Research. The main subject of his research is the Vehicle Routing Problem. The project is supervised by Dr. Michael Forbes and Dr. Michael Bulmer.