Graduate Thesis Or Dissertation
 

A genetic algorithm for the vehicle routing problem with heterogeneous vehicles from multiple depots, allowing multiple visits

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/dj52w9336

Descriptions

Attribute NameValues
Creator
Abstract
  • In the thesis, an application of a genetic algorithm (GA) is considered to solve the vehicle routing problem (VRP) which involves heterogeneous vehicles to serve known customer demands from multiple depots achieving the minimum delivery cost, where each customer must be satisfied by one or more visit(s), and each vehicle must make at most one visit to any particular customer. Vehicles can be unused. The problem involves optimizing the routes for all vehicles which are to serve a certain number of customers from multiple depots, allowing multiple visits. These conditions are generalized from the classical VRPs, which only involve one depot and one visit to each customer. The VRP is one of combinatorial optimization problems which are difficult to obtain an optimal solution through the classical optimization methods owing to the high computational complexity. The GA is a randomized global search algorithm to solve problems by imitating processes observed during natural evolution. It has been a widespread application to various combinatorial optimization problems such as traveling salesman problem, scheduling problem and VRP. The performance of GA is subject to the process parameters such as population size, crossover rate, termination condition, and mutation policy. For the generalized VRP under considerations, the influences of the process parameters in the proposed GA are examined by Taguchi method which is known as a robust design tool for optimizing the process parameters. The proposed GA is the first effort to solve the generalized VRP, which allows the multiple depots, multiple visits and heterogeneous vehicles. A real-life example problem of 35 US cities and 3 depots has been proposed to measure the performance of the proposed GA. In addition, 4 benchmark problems from the prior works only allowing one depot, one visit and homogeneous vehicles has been tested. The proposed GA outperforms the prior works by generating the equal to or the better solutions than the best known solutions. The computational results obtained from the performance comparisons show that the proposed GA is an effective and feasible method for solving the VRP with heterogeneous vehicles from multiple depots, allowing multiple visits to customers.
License
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
File Format
File Extent
  • 1480946 bytes
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details Thesis_GAforVRP_Hyunpae_Aug22_2007.pdf 2017-10-21 Public Download