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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2019
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/78919 |
| _version_ | 1811686950832177152 |
|---|---|
| author | Halder, Shruti |
| author2 | Justin Dauwels |
| author_facet | Justin Dauwels Halder, Shruti |
| author_sort | Halder, Shruti |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T05:08:34Z |
| format | Thesis |
| id | ntu-10356/78919 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:08:34Z |
| publishDate | 2019 |
| record_format | dspace |
| spelling | ntu-10356/789192023-07-04T16:10:01Z Performance analysis of large neighborhood search algorithm applied on vehicle routing problem with pickup and delivery Halder, Shruti Justin Dauwels School of Electrical and Electronic Engineering Engineering::Electrical and electronic engineering 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. Master of Science (Computer Control and Automation) 2019-10-23T02:50:21Z 2019-10-23T02:50:21Z 2019 Thesis http://hdl.handle.net/10356/78919 en 79 p. application/pdf |
| spellingShingle | Engineering::Electrical and electronic engineering Halder, Shruti Performance analysis of large neighborhood search algorithm applied on vehicle routing problem with pickup and delivery |
| title | Performance analysis of large neighborhood search algorithm applied on vehicle routing problem with pickup and delivery |
| title_full | Performance analysis of large neighborhood search algorithm applied on vehicle routing problem with pickup and delivery |
| title_fullStr | Performance analysis of large neighborhood search algorithm applied on vehicle routing problem with pickup and delivery |
| title_full_unstemmed | Performance analysis of large neighborhood search algorithm applied on vehicle routing problem with pickup and delivery |
| title_short | Performance analysis of large neighborhood search algorithm applied on vehicle routing problem with pickup and delivery |
| title_sort | performance analysis of large neighborhood search algorithm applied on vehicle routing problem with pickup and delivery |
| topic | Engineering::Electrical and electronic engineering |
| url | http://hdl.handle.net/10356/78919 |
| work_keys_str_mv | AT haldershruti performanceanalysisoflargeneighborhoodsearchalgorithmappliedonvehicleroutingproblemwithpickupanddelivery |