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

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...

Full description

Saved in:
Bibliographic Details
Main Author: Halder, Shruti
Other Authors: Justin Dauwels
Format: Theses and Dissertations
Language:English
Published: 2019
Subjects:
Online Access:http://hdl.handle.net/10356/78919
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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.