A genetic algorithm for the minimum latency pickup and delivery problem

The pickup and delivery problem combines vehicle routing and objects distribution to cope with logistic problems. While most research on PDP aims to minimize the transportation cost for the sake of service providers, this study proposes the minimum latency pickup and delivery problem (MLPDP) that seeks a low-latency route to transport commodities among nodes, where latency represents the sum of transportation time between demanders and the corresponding suppliers. The MLPDP is pertinent to time-sensitive services and logistics focusing on customer satisfaction. This study defines the latency of a customer as the average time elapsed aboard of goods received. The last-in-first-out loading method is employed to simulate real-world rear-loaded vehicles. This study further designs a genetic algorithm (GA) to resolve the MLPDP. In particular, we propose the edge aggregate crossover (EAC) and the reversely weighting technique to improve the performance of GA on the MLPDP. Experimental results show the effectiveness of the proposed GA. The results further indicate that EAC leads to significantly better performance than conventional crossover operators in solution quality and convergence speed on the MLPDP.