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...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
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 |
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. |
---|