Performance analysis of large neighborhood search algorithm applied on vehicle routing problem with pickup and delivery

Abstract

The Pickup and Drop Problem with Time Window constraint or PDPTW is a hard combinatorial optimization problem. In this problem, requests are generated for goods or load to be carried from their respective pickup point to a designated delivery location. A certain number of vehicles are assigned to serve these pick and drop requests while ensuring the designated time windows at each pick and drop location are not violated and the maximum vehicle capacity, if any, is not breached anywhere in the transportation route. In real-world scenarios the number of vehicles and their corresponding requests are overwhelmingly large and therefore the overall processing time for finding an optimized route for a vehicle must be quicker than the existing best known solutions. The Large Neighborhood Search (LNS) algorithm is implemented to address this problem in PDPTW. The proposed algorithm introduces simplicity in the logic of rearranging requests among a fleet of vehicles to ensure that the overall cost of operation of fleet is reduced to a minimum while respecting the constraints. The algorithm is also used to conduct a comparative analysis between the shared and non-shared modes of transportation of goods using PDPTW benchmark instances to present an empirical conclusion on the preferred mode of transportation.