A hybrid ACS-VTM algorithm for the vehicle routing problem with simultaneous delivery & pickup and real-time traffic condition

Abstract The vehicle routing problem with simultaneous delivery & pickup and real-time traffic information (VRPSDPTI) is a dynamic problem of combinatorial network optimisation in logistics and supply chain management. It is also a typical NP-hard problem that has plagued enterprises with reverse logistics operations for many years. The main objective of this research is to determine an optimal vehicle routing plan for the VRPSDPTI problem. To achieve this goal, a mixed integer programming (MIP) model is constructed, with the objective of minimising the total travel cycle for the VRPSDPTI problem. A hybrid algorithm of the ant colony system and virtual transformation method (ACS-VTM) is then designed to explore the vehicle routing plan for the VRPSDPTI problem; it adopts a flexible split of the time period for re-optimisation and an improved partial service policy for customer demand. Based on it, a practical case of the VRPSDPTI problem is used to verify the proposed model and algorithm. One major finding is proposed through the study of the practical case that adopting the hybrid ACS-VTM algorithm can effectively reduce the total travel cycle for the VRPSDPTI problem. The main contributions of this study are that it can provide an efficient decision tool to solve the VRPSDPTI, and can not only reduce the total travel cycle, but also improve the efficiency of vehicle utilisation.