You are here

Multi-Vehicle Dispatching and Routing with Time Window Constraints and Limited Dock Capacity

Download pdf | Full Screen View

Date Issued:
2012
Abstract/Description:
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 depotThe 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.iiiThe 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.
Title: Multi-Vehicle Dispatching and Routing with Time Window Constraints and Limited Dock Capacity.
0 views
0 downloads
Name(s): El-Nashar, Ahmed, Author
Nazzal, Dima, Committee Chair
Sepulveda, Jose, Committee Member
Geiger, Christopher, Committee Member
Hosni, Yasser, Committee Member
University of Central Florida, Degree Grantor
Type of Resource: text
Date Issued: 2012
Publisher: University of Central Florida
Language(s): English
Abstract/Description: 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 depotThe 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.iiiThe 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.
Identifier: CFE0004532 (IID), ucf:49233 (fedora)
Note(s): 2012-12-01
Ph.D.
Engineering and Computer Science, Industrial Engineering and Management Systems
Doctoral
This record was generated from author submitted information.
Subject(s): VRPTW -- Limited Loading Docks -- Staggered Dispatching -- PRG Algorithm
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFE0004532
Restrictions on Access: public 2012-12-15
Host Institution: UCF

In Collections