Influence of Customer Locations on Heuristics and Solutions for the Vehicle Routing Problem

Simple item page
dc.contributor.authorTilashalski, Melissa Christineen
dc.contributor.committeechairEllis, Kimberly P.en
dc.contributor.committeememberHouse, Leanna L.en
dc.contributor.committeememberTaylor, Gaylon Donen
dc.contributor.committeememberBish, Douglas R.en
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.date.accessioned2023-07-08T08:00:25Zen
dc.date.available2023-07-08T08:00:25Zen
dc.date.issued2023-07-07en
dc.description.abstractThe vehicle routing problem (VRP) determines preferred vehicle routes to visit multiple customer locations from a depot location based on a defined objective function. The VRP is an NP-hard network optimization problem that is challenging to solve to optimality. Over the past 60 years, multitudes of heuristics and metaheuristics have been developed in order to minimize the computational burden of solving the VRP. In order to compare the performance of VRP heuristics, researchers have developed bench-marking datasets. These datasets, however, lack properties found in industry datasets. In this dissertation, we explore how properties of industry datasets influence VRP heuristics and objective functions. In Chapter 2, we quantify and compare features of bench-marking and industry datasets. In order to determine if these features influence heuristic performance, we conduct extensive computational runs on three heuristics, Tabu Search, Genetic Algorithm, and Clarke-Wright Savings Procedure, on standard and industry datasets. In Chapter 3, we derive worst-case analysis on how VRP objective functions and metrics relate to one another. These bounds depend on properties of customer locations. These bounds illustrate how customer locations can influence how different routes behave for different routing metrics. Finally, in Chapter 4, we improve two VRP heuristics, Clarke-Wright Saving Procedure and Hybrid Genetic Search Algorithm, by developing new enhancements to the algorithms. These enhancements rely on certain properties of the datasets in order to perform well. Thus, these heuristics perform better on specific VRP dataset types.en
dc.description.abstractgeneralThe vehicle routing problem (VRP) creates vehicle routes that have the shortest travel distance. The routes determine how vehicles should visit multipl customer locations, to deliver or pickup goods, and return to a depot location. While explaining what the VRP entails is simple, the VRP is actually very difficult for even the most sophisticated algorithms on the best computers to solve. Over the past 60 years, many algorithms have been developed in order to more easily and quickly solve the VRP. In order to compare the performance of VRP algorithms, researchers have developed bench-marking datasets. However, these datasets lack properties of datasets found in industry. In this dissertation, we look to connect the disconnect between industry and bench-marking datasets by 1) comparing feature differences between these two types of datasets, 2) determining if differences in datasets imply differences in algorithm performance, 3) proving how problem differences influence VRP routes, and 4) enhancing existing VRP algorithms to perform better on specific VRP dataset types.en
dc.description.degreeDoctor of Philosophyen
dc.format.mediumETDen
dc.identifier.othervt_gsexam:37810en
dc.identifier.urihttp://hdl.handle.net/10919/115682en
dc.language.isoenen
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectVehicle Routing Problemen
dc.subjectTabu Searchen
dc.subjectGenetic Algorithmen
dc.subjectWorst-Case Analysisen
dc.subjectIndustry Dataen
dc.titleInfluence of Customer Locations on Heuristics and Solutions for the Vehicle Routing Problemen
dc.typeDissertationen
thesis.degree.disciplineIndustrial and Systems Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.nameDoctor of Philosophyen

Files

Original bundle
Now showing 1 - 1 of 1
Name:
Tilashalski_MC_D_2023.pdf
Size:
3.1 MB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations