Document Type

Dissertation

Date of Award

2017

Keywords

Applied sciences, Insertion algorithm, Robust optimization, Scoring tabu search with variable neighborhood, Tabu search, Vehicle routing problems

Degree Name

Doctor of Philosophy (PhD)

Department

Systems Science and Industrial Engineering

First Advisor

Sung Hoon Chung

Subject Heading(s)

Applied sciences; Insertion algorithm; Robust optimization; Scoring tabu search with variable neighborhood; Tabu search; Vehicle routing problems; Engineering; Industrial Engineering

Abstract

In this dissertation, the variants of vehicle routing problems (VRPs) are specifically considered in two applications: disaster relief routing and ride-sharing. In disaster relief operations, VRPs are important, especially in the immediate response phase, as vehicles are an essential part of the supply chain for delivering critical supplies. This dissertation addresses the capacitated vehicle routing problem (CVRP) and the split delivery vehicle routing problem (SDVRP) with uncertain travel times and demands when planning vehicle routes for delivering critical supplies to the affected population in need after a disaster. A robust optimization approach is used for the CVRP and the SDVRP considering the five objective functions: minimization of the total number of vehicles deployed (minV), the total travel time/travel cost (minT), the summation of arrival times (minS), the summation of demand-weighted arrival times (minD), and the latest arrival time (minL), out of which we claim that minS, minD, and minL are critical for deliveries to be fast and fair for relief efforts, while minV and minT are common cost-based objective functions in the traditional VRP. In ride-sharing problem, the participants' information is provided in a short notice, for which driver-rider matching and associated routes need to be decided quickly. The uncertain travel time is considered explicitly when matching and route decisions are made, and a robust optimization approach is proposed to handle it properly. To achieve computational tractability, a new two-stage heuristic method that combines the extended insertion algorithm and tabu search (TS) is proposed to solve the models for large-scale problems. In addition, a new hybrid algorithm named scoring tabu search with variable neighborhood (STSVN) is proposed to solve the models and compared with TS. The solutions of the CVRP and the SDVRP are compared for different examples using five different metrics in which the results show that the latter is not only capable of accommodating the demand greater than the vehicle capacity but also is quite effective to mitigate demand and travel time uncertainty, thereby outperforms CVRP in the disaster relief routing perspective. The results of ride-sharing problem show the influence of parameters and uncertain travel time on the solutions. The performance of TS and STSVN are compared in terms of solving the models for disaster relief routing and ride-sharing problems and the results show that STSVN outperforms TS in searching the near-optimal/optimal solutions within the same CPU time.

Download

Share

COinS