Program > By author > Khalil Mohamad

The Pickup and Delivery Problem with Time Windows (PDPTW) is an NP-hard problem since it is a generalization of well-known Vehicle Routing Problem with Time Window (VRPTW). The PDPTW models the situation in which a fleet of vehicles based at a depot must be routed to visit exactly once a set of nodes with known demands. Hence, vehicles have to transport loads from pickup locations to delivery locations while respecting capacity and time constraints. In our studies, we aim to solve the PDPTW with paired demands. To this purpose, a simple MILP mathematical model for the problem is first introduced. Likewise other optimization approaches, the new formulation can efficiently solve case studies involving at most 50 nodes to optimality in a short CPU time.

To overcome this limitation, a preprocessing stage clustering nodes together is initially performed to yield a more compact cluster-based MILP problem formulation. In this stage, two different algorithms were developed: the first one is based on Euclidean distance between different nodes and the other one is a modified version of well-known K-means algorithm. Once we have applied one of those algorithms, a common function must be applied in order to verify that each customer-supplier pair belongs to the same cluster. We tested and compared our proposed approaches on numerous benchmark problems featuring different sizes, clustered/random node locations and time window distributions have been solved in acceptable CPU times.