Keywords

Vrptw, limited loading docks, staggered dispatching, prg algorithm

Abstract

The Vehicle Routing Problem with Time Windows (VRPTW) is an important and computationally hard optimization problem frequently encountered in Scheduling and logistics. The Vehicle Routing Problem (VRP) can be described as the problem of designing the most efficient and economical routes from one depot to a set of customers using a limited number of vehicles. This research addresses the VRPTW under the following additional complicating features that are often encountered in practical problems: 1. Customers have strict time windows for receiving a vehicle, i.e., vehicles are not allowed to arrive at the customer’s location earlier than the lower limit of the specified time window, which is relaxed in previous research work. 2. There is a limited number of loading/unloading docks for dispatching/receiving the vehicles at the depot The main goal of this research is to propose a framework for solving the VRPTW with the constraints stated above by generating near-optimal routes for the vehicles so as to minimize the total traveling distance. First, the proposed framework clusters customers into groups based on their proximity to each other. Second, a Probabilistic Route Generation (PRG) algorithm is applied to each cluster to find the best route for visiting customers by each vehicle; multiple routes per vehicle are generated and each route is associated with a set of feasible dispatching times from the depot. Third, an assignment problem formulation determines the best dispatching time and route for each vehicle that minimizes the total traveling distance. iii The proposed algorithm is tested on a set of benchmark problems that were originally developed by Marius M. Solomon and the results indicate that the algorithm works well with about 1.14% average deviation from the best-known solutions. The benchmark problems are then modified by adjusting some of the customer time window limits, and adding the staggered vehicle dispatching constraint. For demonstration purposes, the proposed clustering and PRG algorithms are then applied to the modified benchmark problems.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

2012

Semester

Fall

Advisor

Nazzal, Dima

Degree

Doctor of Philosophy (Ph.D.)

College

College of Engineering and Computer Science

Department

Industrial Engineering and Management Systems

Degree Program

Industrial Engineering

Format

application/pdf

Identifier

CFE0004532

URL

http://purl.fcla.edu/fcla/etd/CFE0004532

Language

English

Release Date

December 2012

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Subjects

Dissertations, Academic -- Engineering and Computer Science, Engineering and Computer Science -- Dissertations, Academic

Download

Share

COinS